Fronta Pythonu: Příklad FIFO, LIFO

Obsah:

Anonim

Co je to Python Queue?

Fronta je kontejner, který obsahuje data. Data, která se zadají jako první, budou nejprve odstraněna, a proto se fronta bude také nazývat „First in First Out“ (FIFO). Fronta má dva konce vpředu a vzadu. Položky se zadávají zezadu a odstraňují se z přední strany.

V tomto výukovém programu pro Python se naučíte:

  • Co je to Python Queue?
  • Jak funguje fronta Pythonu?
  • Typy front v Pythonu
  • Instalace fronty Pythonu
  • Metody dostupné uvnitř třídy Queue a LifoQueue
  • Příklad první fronty první fronty
  • Příklad fronty Last In First Out
  • Přidejte do fronty více než 1 položku
  • Fronta třídění
  • Reverzní fronta

Jak funguje fronta Pythonu?

Frontu lze snadno porovnat s reálným příkladem řady lidí čekajících ve frontě u přepážky lístků, osoba stojící jako první získá lístek jako první, následuje další osoba atd. Stejná logika platí i pro datovou strukturu fronty.

Zde je schematické znázornění fronty:

Zadní představuje místo, kde jsou předměty vloženy uvnitř fronty. V tomto příkladu je pro to hodnota 7.

Přední představuje místo, kde budou odstraněny položky z fronty. 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 odebrání je první, která vyšla. Fronta se proto nazývá FIRST IN FIRST OUT (FIFO)

Ve frontě jsou položky odebrány v pořadí a nelze je odebrat mezi nimi. Prostě nemůžete náhodně odebrat položku 5 z fronty. K tomu budete muset odstranit všechny položky před 5. Položky ve frontě budou odebrány v pořadí, v jakém jsou vloženy.

Typy front v Pythonu

V Pythonu existují hlavně dva typy front:

  • First in First out Queue: Za tímto účelem bude prvkem, který vyjde jako první, prvek, který jde jako první.

    Abyste mohli pracovat s FIFO, musíte z modulu fronty zavolat třídu Queue () .

  • Last in First out Queue: Tady bude prvek, který je zadán jako poslední, vyjde jako první.

    Abyste mohli s LIFO pracovat, musíte z modulu fronty zavolat třídu LifoQueue () .

Instalace fronty Pythonu

Práce s frontou v pythonu je velmi snadná. Tady jsou kroky, které je třeba dodržet, abyste ve svém kódu mohli použít frontu.

Krok 1) Musíte pouze importovat modul fronty, jak je znázorněno níže:

import queue

Modul je ve výchozím nastavení k dispozici v pythonu a pro zahájení práce s frontou nepotřebujete žádnou další instalaci. Existují 2 typy front FIFO (první dovnitř první ven) a LIFO (poslední dovnitř první ven).

Krok 2) Chcete-li pracovat s frontou FIFO, zavolejte třídu Queue pomocí importovaného modulu fronty, jak je znázorněno níže: 

import queueq1 = queue.Queue()

Krok 3) Chcete-li pracovat s frontou LIFO, zavolejte třídu LifoQueue (), jak je uvedeno níže: 

import queueq1 = queue.LifoQueue()

Metody dostupné uvnitř třídy Queue a LifoQueue

Níže jsou uvedeny důležité metody dostupné ve třídě Queue a LifoQueue:

  • put (item): Tím se položka umístí do fronty.
  • get (): Tím se vrátí položka z fronty.
  • empty (): Vrátí hodnotu true, pokud je fronta prázdná, a hodnotu false, pokud jsou k dispozici položky.
  • qsize (): vrací velikost fronty.
  • full (): vrací true, pokud je fronta plná, jinak false.

Příklad první fronty první fronty

V případě first in first out bude prvkem, který 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 následujícím příkladu.

Chcete-li přidat položku, můžete použít metodu put (), jak je znázorněno v příkladu:

import queueq1 = 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, lze postupovat následovně

import queueq1 = 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 nebude trvat 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í.

Odeberte položku z fronty

Chcete-li odebrat položku z fronty, můžete použít metodu nazvanou get (). Tato metoda umožňuje položky z fronty při volání.

Následující příklad ukazuje, jak odebrat položku z fronty.

import queueq1 = 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ě last in the first out queue, the element that is entered last will be the first to come out.

Abychom mohli pracovat s LIFO, tj. Jako poslední v první frontě, musíme importovat modul fronty a využít metodu LifoQueue ().

Přidat a položku ve frontě

Zde pochopíme, jak přidat položku do fronty LIFO.

import queueq1 = queue.LifoQueue()q1.put(10)

Na LifoQueue musíte použít metodu put (), jak ukazuje výše uvedený příklad.

Odeberte položku z fronty

Chcete-li odebrat položku z LIFOqueue, můžete použít metodu get ().

import queueq1 = 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 do fronty více než 1 položku

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řidejte a přidejte položku do FIFOqueue

import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queue

Odeberte položku z FIFOqueue

import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.

Výstup:

The value is 0The value is 1The value is 2The value is 3The value is 4The value is 5The value is 6The value is 7The value is 8The value is 9The value is 10The value is 11The value is 12The value is 13The value is 14The value is 15The value is 16The value is 17The value is 18The value is 19

Přidat a položku v LIFOqueue

import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queue

Odeberte položku z LIFOqueue

import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.

Výstup:

The value is 19The value is 18The value is 17The value is 16The value is 15The value is 14The value is 13The value is 12The value is 11The value is 10The value is 9The value is 8The value is 7The value is 6The value is 5The value is 4The value is 3The value is 2The value is 1The value is 0

Fronta třídění

Následující příklad ukazuje řazení fronty. Algoritmus použitý pro třídění je třídění podle bublin.

import queueq1 = queue.Queue()#Addingitems to the queueq1.put(11)q1.put(5)q1.put(4)q1.put(21)q1.put(3)q1.put(10)#using bubble sort on the queuen = q1.qsize()for i in range(n):x = q1.get() # the element is removedfor j in range(n-1):y = q1.get() # the element is removedif x> y :q1.put(y) #the smaller one is put at the start of the queueelse:q1.put(x) # the smaller one is put at the start of the queuex = y # the greater one is replaced with x and compared again with nextelementq1.put(x)while (q1.empty() == False):print(q1.queue[0], end = " ")q1.get()

Výstup:

3 4 5 10 11 21

Reverzní fronta

Chcete-li obrátit frontu, můžete využít jinou frontu a rekurzi.

Následující příklad ukazuje, jak získat frontu obrácenou.

Příklad:

import queueq1 = 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 recursionq2dest.put(buffer)return q2destq2dest = 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

Souhrn:

  • Fronta je kontejner, který obsahuje data. Existují dva typy front, FIFO a LIFO.
  • U FIFO (First in First out Queue) bude prvkem, který vyjde jako první.
  • U LIFO (Last in First out Queue) bude prvek, který je zadán jako poslední, vydán jako první.
  • Položka ve frontě je přidána pomocí metody put (item).
  • K odebrání položky se používá metoda get ().