Python Fronta: FIFO, LIFO Příklad
Logan Young
Co je to Python Fronta?
Fronta je kontejner, který obsahuje data. Data, která zadáte jako první, budou odstraněna jako první, a proto se fronta také nazývá „First in First Out“ (FIFO). Fronta má dva konce vpředu a vzadu. Položky se zadávají zezadu a vyjímají z přední strany.
Jak se dělá Python Práce ve frontě?
Frontu lze snadno porovnat s reálným příkladem fronty lidí čekajících ve frontě u pokladní přepážky, první dostane lístek ten, kdo stojí jako první, následuje další a tak dále. Stejná logika platí i pro datovou strukturu fronty.
Zde je schématické znázornění fronty:
Jedno Zadní představuje bod, kde jsou položky vloženy do fronty. V tomto příkladu je pro to hodnota 7.
Jedno Přední představuje bod, kde budou položky z fronty odstraněny. Pokud odeberete položku z fronty, první prvek, který získáte, je 1, jak je znázorněno na obrázku.
Položka 1 byla první, která byla vložena do fronty, a při odstraňování je první, která vyšla. Proto se fronta nazývá FIRST IN FIRST OUT (FIFO)
Ve frontě jsou položky odebírány v pořadí a nelze je odstraňovat mezitím. Položku 5 prostě nemůžete odstranit náhodně z fronty, k tomu budete muset odstranit všechny položky před 5. Položky ve frontě budou odstraněny v pořadí, v jakém byly vloženy.
Typy fronty v Python
Existují hlavně dva typy fronty Python:
- First in First out Queue: Za tímto účelem prvek, který jde jako první, vyjde jako první. Chcete-li pracovat s FIFO, musíte zavolat Fronta() třídy z modulu fronty.
- Last in First Out Queue: Zde prvek, který je zadán jako poslední, vyjde jako první. Chcete-li pracovat s LIFO, musíte zavolat LifoQueue() třídy z modulu fronty.
Python instalace fronty
V pythonu je velmi snadné pracovat s frontou. Zde jsou kroky, které je třeba dodržet, abyste mohli ve svém kódu použít frontu.
Krok 1) Stačí importovat modul fronty, jak je znázorněno níže:
import queue
Modul je standardně dostupný s pythonem a nepotřebujete žádnou další instalaci, abyste mohli začít pracovat s frontou. Existují 2 typy fronty FIFO (první dovnitř první ven) a LIFO (poslední dovnitř první ven).
Krok 2) Chcete-li pracovat s FIFO queue , zavolejte třídu Queue pomocí modulu fronty importovaného, jak je uvedeno níže:
import queue q1 = queue.Queue()
Krok 3) Chcete-li pracovat s frontou LIFO, zavolejte třídu LifoQueue(), jak je uvedeno níže:
import queue q1 = queue.LifoQueue()
Metody dostupné ve třídě Queue a LifoQueue
Níže jsou uvedeny důležité metody dostupné ve třídě Queue a LifoQueue:
- vložit (položka): Tím se položka zařadí do fronty.
- dostat(): Tím se vám vrátí položka z fronty.
- prázdný(): Vrátí true, pokud je fronta prázdná, a false, pokud jsou přítomny položky.
- qsize(): vrátí velikost fronty.
- plný(): vrátí true, je-li fronta plná, jinak false.
První do první z fronty Příklad
V případě první dovnitř, první ven, prvek, který jde jako první, vyjde jako první.
Přidat a položku ve frontě
Pojďme pracovat na příkladu přidání položky do fronty. Chcete-li začít pracovat s frontou, nejprve importujte frontu modulů, jak je znázorněno v příkladu níže.
Chcete-li přidat položku, můžete použít metodu put(), jak je znázorněno v příkladu:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Ve výchozím nastavení je velikost fronty nekonečná a můžete do ní přidat libovolný počet položek. V případě, že chcete definovat velikost fronty, totéž lze provést následovně
import queue q1 = queue.Queue(5) #The max size is 5. q1.put(1) q1.put(2) q1.put(3) q1.put(4) q1.put(5) print(q1.full()) # will return true.
Výstup:
True
Nyní je velikost fronty 5 a nezabere více než 5 položek a metoda q1.full() vrátí hodnotu true. Přidáním dalších položek se kód dále nespustí.
Odebrat položku z fronty
Chcete-li odstranit položku z fronty, můžete použít metodu nazvanou get(). Tato metoda umožňuje při volání položky z fronty.
Následující příklad ukazuje, jak odebrat položku z fronty.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Výstup:
The item removed from the queue is 10
Příklad fronty Last In First Out
V případě posledního ve frontě první, prvek, který je zadán jako poslední, vyjde jako první.
Abychom mohli pracovat s LIFO, tj. jako poslední v první výstupní frontě, musíme importovat modul fronty a použít metodu LifoQueue().
Přidat a položku ve frontě
Zde pochopíme, jak přidat položku do fronty LIFO.
import queue q1 = queue.LifoQueue() q1.put(10)
Na LifoQueue musíte použít metodu put(), jak je ukázáno ve výše uvedeném příkladu.
Odebrat položku z fronty
Chcete-li odstranit položku z fronty LIFO, můžete použít metodu get() .
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Výstup:
The item removed from the LIFO queue is 10
Přidejte více než 1 položku do fronty
Ve výše uvedených příkladech jsme viděli, jak přidat jednu položku a odebrat položku pro FIFO a LIFOqueue. Nyní uvidíme, jak přidat více než jednu položku a také ji odebrat.
Přidat a položku ve frontě FIFO
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Odeberte položku z fronty FIFO
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Výstup:
The value is 0 The value is 1 The value is 2 The value is 3 The value is 4 The value is 5 The value is 6 The value is 7 The value is 8 The value is 9 The value is 10 The value is 11 The value is 12 The value is 13 The value is 14 The value is 15 The value is 16 The value is 17 The value is 18 The value is 19
Přidat a položku ve frontě LIFO
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Odeberte položku z fronty LIFO
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Výstup:
The value is 19 The value is 18 The value is 17 The value is 16 The value is 15 The value is 14 The value is 13 The value is 12 The value is 11 The value is 10 The value is 9 The value is 8 The value is 7 The value is 6 The value is 5 The value is 4 The value is 3 The value is 2 The value is 1 The value is 0
Fronta řazení
Následující příklad ukazuje řazení ve frontě. Algoritmus používaný pro řazení je bublinové řazení.
import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
#using bubble sort on the queue
n = q1.qsize()
for i in range(n):
x = q1.get() # the element is removed
for j in range(n-1):
y = q1.get() # the element is removed
if x > y :
q1.put(y) #the smaller one is put at the start of the queue
else:
q1.put(x) # the smaller one is put at the start of the queue
x = y # the greater one is replaced with x and compared again with nextelement
q1.put(x)
while (q1.empty() == False):
print(q1.queue[0], end = " ")
q1.get()
Výstup:
3 4 5 10 11 21
Reversing Queue
Chcete-li frontu obrátit, můžete použít jinou frontu a rekurzi.
Následující příklad ukazuje, jak dosáhnout obrácení fronty.
Příklad:
import queue
q1 = queue.Queue()
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
def reverseQueue (q1src, q2dest) :
buffer = q1src.get()
if (q1src.empty() == False) :
reverseQueue(q1src, q2dest) #using recursion
q2dest.put(buffer)
return q2dest
q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)
while (qReversed.empty() == False):
print(qReversed.queue[0], end = " ")
qReversed.get()
Výstup:
10 3 21 4 5 11
Shrnutí
- Fronta je kontejner, který obsahuje data. Existují dva typy fronty, FIFO a LIFO.
- V případě FIFO (First in First Out Queue) prvek, který jde jako první, vyjde jako první.
- U LIFO (Last in First Out Queue) prvek, který je zadán jako poslední, vyjde jako první.
- Položka ve frontě je přidána pomocí metody put(item).
- K odstranění položky se používá metoda get().
