Podobno kot sklad je čakalna vrsta linearna podatkovna struktura, ki shranjuje elemente v prvi v prvi ven ( FIFO ) način. Pri čakalni vrsti se najprej odstrani nazadnje dodan element. Dober primer čakalne vrste je katera koli čakalna vrsta porabnikov za vir, kjer je porabnik, ki je bil prvi, postrežen prvi.

Operacije, povezane s čakalno vrsto, so:

ni vhodnega signala

• V čakalno vrsto: Doda element v čakalno vrsto. Če je čakalna vrsta polna, se reče, da gre za stanje prelivanja – Časovna zapletenost: O(1)
• V skladu s tem: Odstrani element iz čakalne vrste. Predmeti se prikažejo v istem vrstnem redu, kot so potisnjeni. Če je čakalna vrsta prazna, se reče, da gre za pogoj premajhnega toka – Časovna kompleksnost: O(1)
• Spredaj: Pridobite prvi element iz čakalne vrste – Časovna zapletenost: O(1)
• Zadaj: Pridobite zadnji element iz čakalne vrste – Časovna zahtevnost: O(1)

Implementirajte čakalno vrsto v Pythonu

Obstaja več načinov za implementacijo čakalne vrste Python. Ta članek pokriva implementacijo čakalne vrste z uporabo podatkovnih struktur in modulov iz knjižnice Python. Python Queue je mogoče implementirati na naslednje načine:

• seznam
• zbirke.deque
• rep.rep

Izvedba z uporabo seznama

Seznam je Pythonova vgrajena podatkovna struktura, ki se lahko uporablja kot čakalna vrsta. Namesto enqueue() in temu primerno () , pripni() in pop() se uporablja funkcija. Vendar so seznami za ta namen precej počasni, ker vstavljanje ali brisanje elementa na začetku zahteva premik vseh drugih elementov za enega, kar zahteva O(n) časa.
Koda simulira čakalno vrsto z uporabo seznama Python. Dodaja elemente 'a' , 'b' , in 'c' v čakalno vrsto in jih nato odstrani iz vrste, kar povzroči prazno čakalno vrsto na koncu. Izhod prikazuje začetno čakalno vrsto, elemente, izključene iz čakalne vrste ( 'a' , 'b' , 'c' ) in stanje prazne čakalne vrste.

Python3

>

>

Izhod:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements []>

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list>

Izvedba z uporabo collections.deque

Čakalno vrsto v Pythonu je mogoče implementirati z uporabo razreda deque iz modula zbirk. Deque ima prednost pred seznamom v primerih, ko potrebujemo hitrejše operacije dodajanja in izpiranja z obeh koncev vsebnika, saj deque zagotavlja O(1) časovno kompleksnost za operacije dodajanja in izpiranja v primerjavi s seznamom, ki zagotavlja O(n) časovno kompleksnost . Namesto enqueue in deque se uporabljata funkciji append() in popleft().
Koda uporablja adeque>Izcollections>modul za predstavitev čakalne vrste. Prilaga se 'a' , 'b' , in 'c' v čakalno vrsto in jih izključi z q.popleft()> , zaradi česar je čakalna vrsta prazna. Razkomentiranje q.popleft()> ko je čakalna vrsta prazna, bi dvignilIndexError>. Koda prikazuje operacije v čakalni vrsti in obravnava scenarij prazne čakalne vrste.

Python3

>

>

Izhod:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])>

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque>

Implementacija z uporabo queue.Queue

Queue je vgrajeni modul Pythona, ki se uporablja za implementacijo čakalne vrste. queue.Queue(maxsize) inicializira spremenljivko na največjo velikost maxsize. Največja velikost nič '0' pomeni neskončno čakalno vrsto. Ta čakalna vrsta sledi pravilu FIFO.
V tem modulu so na voljo različne funkcije:

• maxsize – Število elementov, dovoljenih v čakalni vrsti.
• prazno() – Vrni True, če je čakalna vrsta prazna, v nasprotnem primeru False.
• poln() – Vrni True, če so v čakalni vrsti elementi največje velikosti. Če je bila čakalna vrsta inicializirana z maxsize=0 (privzeto), potem full() nikoli ne vrne True.
• dobiti () – Odstranite in vrnite element iz čakalne vrste. Če je čakalna vrsta prazna, počakajte, da bo element na voljo.
• get_nowait() – Vrni element, če je takoj na voljo, sicer dvigni QueueEmpty.
• postaviti (predmet) – Postavite predmet v čakalno vrsto. Če je čakalna vrsta polna, počakajte, da bo na voljo prosto mesto, preden dodate element.
• put_nowait(element) – Postavite element v čakalno vrsto brez blokiranja. Če ni takoj na voljo nobene proste reže, dvignite QueueFull.
• qsize() – Vrni število elementov v čakalni vrsti.

primer: Ta koda uporabljaQueue>razreda izqueue>modul. Začne se s prazno čakalno vrsto in jo napolni z ' a', 'b' , in 'c' . Po odstranitvi iz vrste postane čakalna vrsta prazna in doda se '1'. Čeprav je bil prej prazen, ostaja poln, saj je največja velikost nastavljena na 3. Koda prikazuje operacije v čakalni vrsti, vključno s preverjanjem polnosti in praznosti.

Python3

ki je naredil šolo

>

>

Izhod:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False>