Som en stabel er køen en lineær datastruktur som lagrer elementer i en først inn først ut ( FIFO ) måte. Med en kø fjernes det elementet som sist ble lagt til først. Et godt eksempel på en kø er en hvilken som helst kø av forbrukere for en ressurs der forbrukeren som kom først blir servert først.

Operasjoner knyttet til køen er:

• Kø: Legger til et element i køen. Hvis køen er full, sies det å være en overløpstilstand – Tidskompleksitet: O(1)
• Tilsvarende: Fjerner et element fra køen. Elementene er poppet i samme rekkefølge som de skyves. Hvis køen er tom, sies det å være en underflyttilstand – Tidskompleksitet: O(1)
• Front: Få det fremre elementet fra køen – Tidskompleksitet: O(1)
• Bak: Få det siste elementet fra køen – Tidskompleksitet: O(1)

Implementer en kø i Python

Det er ulike måter å implementere en kø på Python. Denne artikkelen dekker implementering av kø ved hjelp av datastrukturer og moduler fra Python-biblioteket. Python Queue kan implementeres på følgende måter:

• liste
• samlinger.deque
• hale.hale

Implementering ved hjelp av liste

List er en Pythons innebygde datastruktur som kan brukes som en kø. I stedet for enqueue() og tilsvarende () , legge til() og pop() funksjonen brukes. Imidlertid er lister ganske trege for dette formålet fordi innsetting eller sletting av et element i begynnelsen krever å flytte alle de andre elementene med ett, noe som krever O(n) tid.
Koden simulerer en kø ved hjelp av en Python-liste. Det legger til elementer 'en' , 'b' , og 'c' til køen og deretter dekøer dem, noe som resulterer i en tom kø på slutten. Utdataene viser startkøen, elementer som er satt ut av kø ( 'en' , 'b' , 'c' ), og køens tomme tilstand.

Python3

Produksjon:

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 

Implementering ved hjelp av collections.deque

Kø i Python kan implementeres ved å bruke deque class fra samlingsmodulen. Deque foretrekkes fremfor liste i tilfeller der vi trenger raskere append- og pop-operasjoner fra begge ender av beholderen, siden deque gir en O(1)-tidskompleksitet for append- og pop-operasjoner sammenlignet med liste som gir O(n)-tidskompleksitet . I stedet for enqueue og deque, brukes append() og popleft() funksjoner.
Koden bruker en deque> fra collections> modul for å representere en kø. Det legger til 'en' , 'b' , og 'c' til køen og dekøer dem med q.popleft()> , noe som resulterer i en tom kø. Ikke kommenterer q.popleft()> etter at køen er tom ville heve en IndexError> . Koden demonstrerer køoperasjoner og håndterer et tomt køscenario.

Python3

Produksjon:

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 

Implementering ved hjelp av queue.Queue

Queue er en innebygd modul i Python som brukes til å implementere en kø. queue.Queue(maxsize) initialiserer en variabel til en maksimal størrelse på maxsize. En maksimal størrelse på null '0' betyr en uendelig kø. Denne køen følger FIFO-regelen.
Det er ulike funksjoner tilgjengelig i denne modulen:

• maxsize – Antall varer tillatt i køen.
• tømme() – Returner True hvis køen er tom, False ellers.
• full() – Returner True hvis det er maxsize elementer i køen. Hvis køen ble initialisert med maxsize=0 (standard), returnerer aldri full() True.
• få() – Fjern og returner en vare fra køen. Hvis køen er tom, vent til en vare er tilgjengelig.
• get_nowait() – Returner en vare hvis en er umiddelbart tilgjengelig, ellers hev QueueEmpty.
• put(item) – Sett en vare i køen. Hvis køen er full, vent til en ledig plass er tilgjengelig før du legger til varen.
• put_nowait(item) – Sett en vare i køen uten å blokkere. Hvis ingen gratis spilleautomat er tilgjengelig umiddelbart, hev QueueFull.
• qsize() – Returner antall varer i køen.

Eksempel: Denne koden bruker Queue> klasse fra queue> modul. Den starter med en tom kø og fyller den med ' en', 'b' , og 'c' . Etter fjerning av køen blir køen tom, og '1' legges til. Til tross for at den er tom tidligere, forblir den full, ettersom den maksimale størrelsen er satt til 3. Koden demonstrerer køoperasjoner, inkludert sjekking for fullhet og tomhet.

Python3

Produksjon:

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