Fronta Pythonu: Príklad FIFO, LIFO

Obsah:

Anonim

Čo je to Python Queue?

Fronta je kontajner, ktorý obsahuje údaje. Údaje, ktoré sa zadajú ako prvé, sa najskôr odstránia, a preto sa poradie nazýva aj „Prvý do prvého von“ (FIFO). Poradie má dva konce vpredu a vzadu. Položky sa zadávajú zozadu a vyberajú sa z prednej strany.

V tomto výučbe pre Python sa dozviete:

  • Čo je to Python Queue?
  • Ako funguje Python Queue?
  • Typy front v Pythone
  • Inštalácia frontu Python
  • Metódy dostupné v triedach Queue a LifoQueue
  • Príklad prvého do prvého frontu
  • Príklad frontu Last In First Out
  • Pridajte do frontu viac ako 1 položku
  • Triediaci rad
  • Reverzný rad

Ako funguje Python Queue?

Poradie možno ľahko porovnať s príkladom v reálnom svete - radom ľudí čakajúcich v rade pri pulte lístka, najskôr dostane lístok ten, kto stojí ako prvý, potom ďalší a podobne. Rovnaká logika platí aj pre dátovú štruktúru frontu.

Tu je schematické znázornenie poradia:

Zadné predstavuje miesto, kde sú predmety vložené vnútri frontu. V tomto príklade je za to hodnota 7.

Predné predstavuje miesto, kde budú odstránené položky z frontu. Ak odstránite položku z poradia, prvý prvok, ktorý získate, je 1, ako je to znázornené na obrázku.

Položka 1 bola prvá, ktorá bola vložená do poradia, a pri odstraňovaní je prvá, ktorá vyšla. Preto sa front nazýva FIRST IN FIRST OUT (FIFO).

Vo fronte sú položky odstránené v poradí a nemôžu byť odstránené medzi nimi. Položku 5 jednoducho nemôžete náhodne odstrániť z frontu, aby ste tak mohli urobiť, budete musieť odstrániť všetky položky pred 5. Položky vo fronte sa odstránia v poradí, v akom sú vložené.

Typy front v Pythone

V Pythone sú hlavne dva typy frontov:

  • Prvý do prvého frontu: Z tohto dôvodu bude prvkom, ktorý vyjde ako prvý, prvok, ktorý ide ako prvý.

    Aby ste mohli pracovať s FIFO, musíte volať triedu Queue () z modulu fronty.

  • Last in First out Queue: Tu bude prvok, ktorý sa zadá posledný, vyjde ako prvý.

    Ak chcete pracovať s programom LIFO, musíte z modulu fronty zavolať triedu LifoQueue () .

Inštalácia frontu Python

S frontom v Pythone sa pracuje veľmi ľahko. Tu sú kroky, ktoré musíte dodržať, aby ste vo svojom kóde mohli použiť rad.

Krok 1) Musíte len naimportovať modul frontu, ako je uvedené nižšie:

import queue

Modul je v predvolenom nastavení k dispozícii v jazyku python a na začatie práce s radom nepotrebujete žiadnu ďalšiu inštaláciu. Existujú 2 typy radov FIFO (prvý do prvého von) a LIFO (posledný do prvého von).

Krok 2) Ak chcete pracovať s frontom FIFO, zavolajte triedu front pomocou importovaného modulu front, ako je uvedené nižšie: 

import queueq1 = queue.Queue()

Krok 3) Ak chcete pracovať s frontom LIFO, zavolajte triedu LifoQueue (), ako je uvedené nižšie: 

import queueq1 = queue.LifoQueue()

Metódy dostupné v triedach Queue a LifoQueue

Nasledujú dôležité metódy dostupné v triedach Queue a LifoQueue:

  • put (item): Týmto sa položka umiestni do fronty.
  • get (): Týmto sa vráti položka z frontu.
  • empty (): Vráti hodnotu true, ak je rad prázdny, a hodnotu false, ak sú prítomné položky.
  • qsize (): vráti veľkosť frontu.
  • full (): vráti true, ak je front plný, inak false.

Príklad prvého do prvého frontu

V prípade first in first out bude prvkom, ktorý vyjde ako prvý.

Pridajte a položku do fronty

Poďme pracovať na príklade pridania položky do poradia. Ak chcete začať pracovať s frontom, najskôr importujte front modulov, ako je to znázornené v príklade nižšie.

Ak chcete pridať položku, môžete použiť metódu put (), ako je uvedené v príklade:

import queueq1 = queue.Queue()q1.put(10) #this will additem 10 to the queue.

Predvolene je veľkosť frontu nekonečná a môžete do nej pridať ľubovoľný počet položiek. V prípade, že chcete definovať veľkosť frontu, je možné postupovať nasledovne

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ýkon:

True

Teraz je veľkosť frontu 5 a nebude trvať viac ako 5 položiek a metóda q1.full () vráti hodnotu true. Pridaním ďalších položiek sa kód už nespustí.

Odstrániť položku z frontu

Na odstránenie položky z frontu môžete použiť metódu nazvanú get (). Táto metóda umožňuje volanie položiek z frontu.

Nasledujúci príklad ukazuje, ako odstrániť položku z frontu.

import queueq1 = queue.Queue()q1.put(10)item1 = q1.get()print('The item removed from the queue is ', item1)

Výkon:

The item removed from the queue is 10

Príklad frontu Last In First Out

V prípade posledného v poradí na umiestnenie ako prvý vyjde ako prvý prvok zadaný ako posledný.

Aby sme mohli pracovať s programom LIFO, tj. Byť poslední v rade z prvého výstupu, musíme importovať modul frontu a využiť metódu LifoQueue ().

Pridajte a položku do fronty

Tu pochopíme, ako pridať položku do frontu LIFO.

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

Na LifoQueue musíte použiť metódu put (), ako je to znázornené vo vyššie uvedenom príklade.

Odstrániť položku z frontu

Na odstránenie položky z LIFOqueue môžete využiť metódu get ().

import queueq1 = queue.LifoQueue()q1.put(10)item1 = q1.get()print('The item removed from the LIFO queue is ', item1)

Výkon:

The item removed from the LIFO queue is 10

Pridajte do frontu viac ako 1 položku

Vo vyššie uvedených príkladoch sme videli, ako pridať jednu položku a odstrániť ju pre FIFO a LIFOqueue. Teraz uvidíme, ako pridať viac ako jednu položku a tiež ju odstrániť.

Pridajte položky do FIFOqueue

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

Odstráňte 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ýkon:

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

Pridajte a pridajte položku do LIFOqueue

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

Odstráňte 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ýkon:

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

Triediaci rad

Nasledujúci príklad ukazuje radenie v poradí. Algoritmom používaným na triedenie je triedenie podľa bublín.

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ýkon:

3 4 5 10 11 21

Reverzný rad

Ak chcete obrátiť poradie, môžete použiť iný rad a rekurziu.

Nasledujúci príklad ukazuje, ako dostať poradie späť.

Prí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ýkon:

10 3 21 4 5 11

Zhrnutie:

  • Fronta je kontajner, ktorý obsahuje údaje. Existujú dva typy frontov, FIFO a LIFO.
  • Pre FIFO (prvý do prvého z frontu) bude prvkom, ktorý vyjde ako prvý.
  • Pre LIFO (Last in First out Queue) bude prvkom, ktorý bude zadaný ako posledný, prvý, ktorý vyjde.
  • Položka vo fronte sa pridáva metódou put (item).
  • Na odstránenie položky sa používa metóda get ().