Python Fronta: FIFO, LIFO Příklad

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

Nejčastější dotazy