Datastrukturer spiller en nøglerolle i programmeringsverdenen. De hjælper os med at organisere vores data på en måde, der kan bruges effektivt. Køen er en af de enkleste datastrukturer, der findes.
I denne artikel lærer vi om køen og dens implementering i Python.
Indholdsfortegnelse
Hvad er en kø?
En kø er en lineær datastruktur, der følger First In/First Out (FIFO) princippet. Det er modsat stak-datastrukturen.
Vi kan sammenligne køen med en virkelig kø ved biografbilletskranken. Lad os se illustrationen af en kø som følger.
Hvis du observerer køen ved skranken, kan den anden person først gå hen til skranken, efter at den første person har afsluttet sit arbejde. Her kommer den første til disken og derefter den anden. Så her følger folk FIFO (First In/First Out) princippet. Den, der kommer først, færdiggør arbejdet først. Vi kan se en lignende form for køer i vores daglige liv.
Kødatastrukturen følger også samme princip. Nu ved du, hvad køer er og dets princip. Lad os se de operationer, der kan udføres på en kødatastruktur.
Operationer i kø
I lighed med stack finder vi to hovedoperationer i en kødatastruktur.
kø (data)
Tilføjer nye data til køen i slutningen. Siden kaldes bagsiden.
dequeue()
Fjerner data fra forsiden af køen. Siden kaldes forsiden.
Lad os se kødriftsillustrationerne for bedre forståelse. Et billede siger mere end tusind ord.
Vi kan skrive nogle hjælpefunktioner for at få mere info om køen. Der er ingen begrænsning på antallet af hjælpefunktioner, du vil have. Lad os holde os til det vigtigste, der én gang er nævnt nedenfor.
bag()
Returnerer det første element fra slutningen af køen.
foran()
Returnerer det første element fra starten af køen.
er tom()
Returnerer om køen er tom eller ej.
Er det ikke kedeligt for dig? Jeg mener de konceptuelle emner.
For mig Ja!
Men vi kan ikke gøre noget uden at kende begreberne. Vi skal fuldstændig vide det før implementeringen. Bare rolig, det er på tide at gøre vores hænder beskidte med noget kode.
Jeg antager, at du har python installeret på din pc, hvis ikke, kan du også prøve online-kompileren.
Implementering af kø
Implementering af en kø vil ikke tage mere end 15 minutter for en programmør. Når du har lært, vil du sige det. Måske kan du implementere det inden for få minutter efter denne vejledning.
Der er flere måder at implementere køen i Python. Lad os se forskellige køimplementeringer trin for trin.
#1. Liste
Listen er en indbygget datatype i Python. Vi skal bruge listedatatypen til at implementere en kø i en klasse. Vi vil lede dig gennem forskellige trin for at implementere kødatastrukturen fra bunden uden nogen moduler. Lad os springe ud i det.
Trin 1:
Skriv en klasse, der hedder Kø.
class Queue: pass
Trin 2:
Der skal være en eller anden variabel for at gemme dataene i køen i klassen. Lad os navngive det elementer. Og det er selvfølgelig en liste.
class Queue: def __init__(self): self.elements = []
Trin 3:
For at indsætte data i køen skal vi bruge en metode i klassen. Metoden kaldes enqueue, som vi allerede har diskuteret i det forrige afsnit af selvstudiet.
Metoden tager nogle data og tilføjer dem til køen (elementer). Vi kan bruge tilføjningsmetoden for listedatatypen til at tilføje data i slutningen af køen.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Trin 4:
Køen skal have en udgang. Og det kaldes dekø. Jeg tror, du allerede har gættet, at vi kommer til at bruge pop-metoden for listedatatypen. Hvis du gættede eller ej, skål!
Pop-metoden for listedatatypen sletter et element fra listen over det givne indeks. Hvis vi ikke gav noget indeks, så sletter det det sidste element på listen.
Her skal vi slette det første element på listen. Så vi er nødt til at overføre indekset 0 til pop-metoden.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Det er nok til en kø. Men vi har brug for hjælpefunktionerne for at teste, om køoperationerne fungerer korrekt eller ej. Lad os også skrive hjælpefunktionerne.
Trin 5:
Metoden rear() bruges til at få det sidste element i køen. Negativ indeksering i listedatatype hjælper os med at få det sidste element i køen.
class Queue: # ... def rear(self): return self.elements[-1]
Trin 6:
Metoden front() bruges til at få det første element i køen. Vi kan få det første element i køen ved hjælp af listeindekset.
class Queue: # ... def front(self): return self.elements[0]
Trin 7:
Metoden is_empty() bruges til at kontrollere, om køen er tom eller ej. Vi kan tjekke listens længde.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Pyha! gennemført implementeringsdelen af kødatastrukturen. Vi skal oprette et objekt, som Queue-klassen kan bruge.
Lad os gøre det.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Nu har vi et køobjekt. Lad os teste det med en række operationer.
- Kontroller, om køen er tom eller ej ved at bruge metoden is_empty. Det burde returnere True.
- Tilføj tallene 1, 2, 3, 4, 5 til køen ved hjælp af enqueue-metoden.
- Metoden is_empty skulle returnere False. Tjekke det.
- Udskriv for- og bagelementerne ved hjælp af henholdsvis for- og bagmetoden.
- Fjern elementet fra køen ved hjælp af dequeue-metoden.
- Tjek frontelementet. Det skal returnere element 2.
- Fjern nu alle elementer fra køen.
- Metoden is_empty skulle returnere True. Tjekke det.
Jeg tror, det er nok til at teste vores køimplementering. Skriv koden for hvert trin nævnt ovenfor for at teste køen.
Har du skrevet koden?
Nej, bare rolig.
Tjek koden nedenfor.
class Queue: def __init__(self): self.elements = [] def enqueue(self, data): self.elements.append(data) return data def dequeue(self): return self.elements.pop(0) def rear(self): return self.elements[-1] def front(self): return self.elements[0] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': queue = Queue() ## checking is_empty method -> True print(queue.is_empty()) ## adding the elements queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.enqueue(4) queue.enqueue(5) ## again checking is_empty method -> False print(queue.is_empty()) ## printing the front and rear elements using front and rear methods respectively -> 1, 5 print(queue.front(), end=' ') print(queue.rear()) ## removing the element -> 1 queue.dequeue() ## checking the front and rear elements using front and rear methods respectively -> 2 5 print(queue.front(), end=' ') print(queue.rear()) ## removing all the elements queue.dequeue() queue.dequeue() queue.dequeue() queue.dequeue() ## checking the is_empty method for the last time -> True print(queue.is_empty())
Jeg tror, du kører ovenstående program. Du kan få et output svarende til det følgende resultat.
True False 1 5 2 5 True
Vi kan direkte bruge listedatatypen som en kødatastruktur. Ovenstående implementering af køen hjælper dig med bedre at forstå køimplementeringen i andre programmeringssprog.
Du kan også bruge ovenstående klasseimplementering af en kø i et andet program i et projekt ved blot at oprette objektet, som vi gjorde tidligere.
Vi har implementeret køen fra bunden ved hjælp af listedatatypen. Er der indbyggede moduler til køen? Ja! vi har indbyggede køimplementeringer. Lad os se dem.
#2. deque fra samlinger
Det er implementeret som en dobbeltkø. Da det understøtter tilføjelse og fjernelse af elementer fra begge ender, kan vi bruge det som en stak og kø. Lad os se køimplementeringen ved hjælp af dequeue.
Den implementeres ved hjælp af andre datastrukturer kaldet den dobbeltforbundne liste. Så udførelsen af indsættelse og sletning af elementer er konsekvent. Adgang til elementer fra den midterste linkede liste tog O(n) tid. Vi kan bruge det som en kø, da der ikke er behov for at få adgang til de midterste elementer fra køen.
Lad os tjekke de forskellige metoder, som dekøen tilbyder os.
- append(data) – bruges til at tilføje data til køen
- popleft() – bruges til at fjerne det første element fra køen
Der er ingen alternative metoder til front, bag og is_empty. Vi kan printe hele køen i stedet for for- og bagmetoder. Dernæst kan vi bruge len-metoden til at kontrollere, om køen er tom eller ej.
Vi har fulgt en række trin for at teste køimplementeringen i det foregående. Lad os også følge den samme serie af trin her.
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
Du vil få et resultat svarende til følgende output.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Kø fra kø
Python har et indbygget modul kaldet kø, der betjener en klasse kaldet Queue til køimplementeringen. Det ligner det, vi har implementeret før.
Lad os først tjekke forskellige metoder i kø-klassen.
- put(data) – tilføjer eller skubber data til køen
- get() – fjerner det første element fra køen og returnerer det
- empty() – returnerer om stakken er tom eller ej
- qsize() – returnerer længden af køen.
Lad os implementere køen med ovenstående metoder.
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
Tjek outputtet af ovenstående kode.
True False 1 2 3 Size 2 4 5 True
Der er nogle andre metoder i Queue-klassen. Du kan udforske dem ved hjælp af den indbyggede dir-funktion.
Konklusion
Jeg håber, du har lært om kødatastrukturen og dens implementering. Det er det for køen. Du kan bruge køen forskellige steder, hvor der skal behandles i FIFO(First In/First Out) rækkefølge. Brug kø i problemløsning, når du får sagen til at bruge den.
Interesseret i at mestre Python? Tjek disse læringsressourcer.
God kodning 🙂 👨💻