Ligesom en stak er køen en lineær datastruktur, der gemmer elementer i en First In First Out ( FIFO ) måde. Med en kø fjernes det mindst nyligt tilføjede element først. Et godt eksempel på en kø er enhver kø af forbrugere til en ressource, hvor den forbruger, der kom først, bliver serveret først.

Operationer forbundet med kø er:

• Kø: Tilføjer et element til køen. Hvis køen er fuld, siges det at være en overløbstilstand – Tidskompleksitet: O(1)
• Derfor: Fjerner en vare fra køen. Elementerne poppes i samme rækkefølge, som de skubbes. Hvis køen er tom, siges det at være en underløbstilstand – Tidskompleksitet: O(1)
• Foran: Få det forreste element fra køen – Tidskompleksitet: O(1)
• Bag: Hent den sidste vare fra køen – Tidskompleksitet: O(1)

Implementer en kø i Python

Der er forskellige måder at implementere en kø på Python. Denne artikel dækker implementeringen af ​​kø ved hjælp af datastrukturer og moduler fra Python-biblioteket. Python Queue kan implementeres på følgende måder:

• liste
• samlinger.deque
• hale.hale

Implementering ved hjælp af liste

List er en Pythons indbyggede datastruktur, der kan bruges som en kø. I stedet for enqueue() og derfor () , Tilføj() og pop() funktion bruges. Lister er dog ret langsomme til dette formål, fordi indsættelse eller sletning af et element i begyndelsen kræver, at alle de andre elementer flyttes med ét, hvilket kræver O(n) tid.
Koden simulerer en kø ved hjælp af en Python-liste. Det tilføjer elementer 'en' , 'b' , og 'c' til køen og sætter dem derefter ud af køen, hvilket resulterer i en tom kø i slutningen. Outputtet viser den indledende kø, elementer ude af kø ( 'en' , 'b' , 'c' ), og køens tomme tilstand.

Python3

Produktion:

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 hjælp af collections.deque

Kø i Python kan implementeres ved hjælp af deque class fra samlingsmodulet. Deque foretrækkes frem for liste i de tilfælde, hvor vi har brug for hurtigere tilføjelses- og pop-operationer fra begge ender af containeren, da deque giver en O(1)-tidskompleksitet for tilføjelses- og pop-handlinger sammenlignet med liste, der giver O(n)-tidskompleksitet . I stedet for enqueue og deque bruges funktionerne append() og popleft().
Koden bruger en deque> fra collections> modul til at repræsentere en kø. Det tilføjer 'en' , 'b' , og 'c' til køen og dekøer dem med q.popleft()> , hvilket resulterer i en tom kø. Ikke kommenterer q.popleft()> efter at køen er tom ville rejse en IndexError> . Koden demonstrerer køoperationer og håndterer et tomt køscenarie.

Python3

Produktion:

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 hjælp af kø.Kø

Queue er et indbygget modul i Python, som bruges til at implementere en kø. queue.Queue(maxsize) initialiserer en variabel til en maksimal størrelse på maxsize. En maxstørrelse på nul '0' betyder en uendelig kø. Denne kø følger FIFO-reglen.
Der er forskellige funktioner tilgængelige i dette modul:

• maxsize – Antal tilladte varer i køen.
• tom() – Returner True, hvis køen er tom, ellers False.
• fuld() – Returner True, hvis der er varer i maxsize i køen. Hvis køen blev initialiseret med maxsize=0 (standard), returnerer full() aldrig True.
• få() – Fjern og returner en vare fra køen. Hvis køen er tom, skal du vente, indtil en vare er tilgængelig.
• get_nuwait() – Returner en vare, hvis en er tilgængelig med det samme, ellers hæv QueueEmpty.
• put(item) – Sæt en vare i køen. Hvis køen er fuld, skal du vente, indtil en ledig plads er tilgængelig, før du tilføjer varen.
• put_nuwait(vare) – Sæt en vare i køen uden at blokere. Hvis der ikke umiddelbart er nogen ledig plads, hæv QueueFull.
• qsize() – Returner antallet af varer i køen.

Eksempel: Denne kode bruger Queue> klasse fra queue> modul. Den starter med en tom kø og fylder den med ' en', 'b' , og 'c' . Efter dekø bliver køen tom, og '1' tilføjes. På trods af at den har været tom tidligere, forbliver den fuld, da den maksimale størrelse er sat til 3. Koden demonstrerer køhandlinger, herunder kontrol for fylde og tomhed.

Python3

Produktion:

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