Datastrukturer spelar en nyckelroll i programmeringsvärlden. De hjälper oss att organisera vår data på ett sätt som kan användas effektivt. Kön är en av de enklaste datastrukturerna som finns tillgängliga.
I den här artikeln kommer vi att lära oss om kön och dess implementering i Python.
Innehållsförteckning
Vad är en kö?
En kö är en linjär datastruktur som följer principen First In/First Out (FIFO). Det är motsatsen till stackdatastrukturen.
Vi kan jämföra kön med en verklig kö vid biobiljettdisken. Låt oss se illustrationen av en kö enligt följande.
Om du observerar kön vid disken, kan den andra personen gå till disken först efter att den första personen slutfört sitt arbete. Här kommer första personen till disken och sedan andra personen. Så här följer folk FIFO (First In/First Out)-principen. Den som kommer först, han/hon kommer att slutföra arbetet först. Vi kan se en liknande typ av köer i vårt dagliga liv.
Ködatastrukturen följer också samma princip. Nu vet du vad köer är och dess princip. Låt oss se de operationer som kan utföras på en ködatastruktur.
Verksamhet i kö
I likhet med stack kommer vi att hitta två huvudoperationer i en ködatastruktur.
enqueue(data)
Lägger till ny data i kön i slutet. Sidan kallas baksidan.
dequeue()
Tar bort data från framsidan av kön. Sidan kallas framsidan.
Låt oss se illustrationerna för ködrift för bättre förståelse. En bild säger mer än tusen ord.
Vi kan skriva några hjälpfunktioner för att få mer info om kön. Det finns ingen begränsning på antalet hjälpfunktioner du kommer att ha. Låt oss hålla oss till det viktigaste som en gång nämnts nedan för nu.
bak()
Returnerar det första elementet från slutet av kön.
främre()
Returnerar det första elementet från början av kön.
är tom()
Returnerar om kön är tom eller inte.
Är det inte tråkigt för dig? Jag menar de konceptuella ämnena.
För mig Ja!
Men vi kan inte göra någonting utan att känna till begreppen. Vi måste veta det innan implementeringen. Oroa dig inte, det är dags att göra våra händer smutsiga med lite kod.
Jag antar att du har python installerat på din PC om inte kan du också prova onlinekompilatorn.
Köimplementering
Att implementera en kö tar inte mer än 15 minuter för en programmerare. När du väl lärt dig kommer du att säga det. Kanske kan du implementera det inom några minuter efter denna handledning.
Det finns flera sätt att implementera kön i Python. Låt oss se olika köimplementeringar steg för steg.
#1. Lista
Listan är en inbyggd datatyp i Python. Vi kommer att använda listdatatypen för att implementera en kö i en klass. Vi kommer att leda dig genom olika steg för att implementera ködatastrukturen från början utan några moduler. Låt oss hoppa in i det.
Steg 1:
Skriv en klass som heter Kö.
class Queue: pass
Steg 2:
Det måste finnas någon variabel för att lagra data i kön i klassen. Låt oss döpa det till element. Och det är en lista förstås.
class Queue: def __init__(self): self.elements = []
Steg 3:
För att infoga data i kön behöver vi en metod i klassen. Metoden kallas enqueue som vi redan diskuterat i föregående avsnitt av handledningen.
Metoden tar en del data och lägger till den i kön (element). Vi kan använda tilläggsmetoden för listdatatypen för att lägga till data i slutet av kön.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Steg 4:
Kön måste ha en utgång. Och det kallas dequeue. Jag tror att du redan gissat att vi kommer att använda popmetoden för listdatatypen. Om du gissade eller inte, heja!
Popmetoden för listdatatypen tar bort ett element från listan över det givna indexet. Om vi inte gav något index, raderar det det sista elementet i listan.
Här måste vi ta bort det första elementet i listan. Så vi måste skicka index 0 till popmetoden.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Det räcker för en kö. Men vi behöver hjälpfunktionerna för att testa om köoperationerna fungerar korrekt eller inte. Låt oss också skriva hjälpfunktionerna.
Steg 5:
Metoden rear() används för att hämta det sista elementet i kön. Negativ indexering i listdatatyp hjälper oss att få det sista elementet i kön.
class Queue: # ... def rear(self): return self.elements[-1]
Steg 6:
Metoden front() används för att hämta det första elementet i kön. Vi kan få det första elementet i kön med hjälp av listindex.
class Queue: # ... def front(self): return self.elements[0]
Steg 7:
Metoden is_empty() används för att kontrollera om kön är tom eller inte. Vi kan kontrollera längden på listan.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Puh! slutfört implementeringsdelen av ködatastrukturen. Vi måste skapa ett objekt för klassen Queue att använda.
Vi gör det.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Nu har vi ett Queue-objekt. Låt oss testa det med en serie operationer.
- Kontrollera om kön är tom eller inte med metoden is_empty. Det bör returnera True.
- Lägg till siffrorna 1, 2, 3, 4, 5 till kön med hjälp av enqueue-metoden.
- Metoden is_empty bör returnera False. Kolla upp det.
- Skriv ut de främre och bakre elementen med hjälp av de främre och bakre metoderna.
- Ta bort elementet från kön med hjälp av dequeue-metoden.
- Kontrollera frontelementet. Det bör returnera element 2.
- Ta nu bort alla element från kön.
- Metoden is_empty bör returnera True. Kolla upp det.
Jag tror att det räcker för att testa vår köimplementering. Skriv koden för varje steg som nämns ovan för att testa kön.
Har du skrivit koden?
Nej, oroa dig inte.
Kontrollera koden nedan.
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())
Jag tror att du kör programmet ovan. Du kan få en utdata som liknar följande resultat.
True False 1 5 2 5 True
Vi kan direkt använda listdatatypen som en ködatastruktur. Ovanstående implementering av kön hjälper dig att bättre förstå köimplementeringen i andra programmeringsspråk.
Du kan också använda ovanstående klassimplementering av en kö i ett annat program i ett projekt genom att helt enkelt skapa objektet som vi gjorde tidigare.
Vi har implementerat kön från början med hjälp av listdatatypen. Finns det några inbyggda moduler för kön? Ja! vi har inbyggda köimplementeringar. Låt oss se dem.
#2. deque från samlingar
Den är implementerad som en dubbelkö. Eftersom det stöder tillägg och borttagning av element från båda ändar, kan vi använda det som en stack och kö. Låt oss se köimplementeringen med hjälp av dequeue.
Den implementeras med hjälp av andra datastrukturer som kallas den dubbellänkade listan. Så prestandan för infogning och borttagning av element är konsekvent. Att komma åt element från den mittersta länkade listan tog O(n) tid. Vi kan använda det som en kö eftersom det inte finns något behov av att komma åt mittelementen från kön.
Låt oss kolla de olika metoderna som dequeue erbjuder oss.
- append(data) – används för att lägga till data i kön
- popleft() – används för att ta bort det första elementet från kön
Det finns inga alternativa metoder för fram, bak och is_empty. Vi kan skriva ut hela kön istället för fram- och bakmetoder. Därefter kan vi använda len-metoden för att kontrollera om kön är tom eller inte.
Vi har följt en rad steg för att testa köimplementeringen i det föregående. Låt oss följa samma serie av steg här också.
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 kommer att få ett resultat som liknar följande utdata.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Kö från kö
Python har en inbyggd modul som heter queue som betjänar en klass som heter Queue för köimplementeringen. Det liknar det vi har implementerat tidigare.
Låt oss först kolla in olika metoder i klassen Queue.
- put(data) – lägger till eller skickar data till kön
- get() – tar bort det första elementet från kön och returnerar det
- empty() – returnerar om stacken är tom eller inte
- qsize() – returnerar längden på kön.
Låt oss implementera kön med ovanstå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())
Kontrollera utmatningen av ovanstående kod.
True False 1 2 3 Size 2 4 5 True
Det finns några andra metoder i klassen Queue. Du kan utforska dem med den inbyggda dir-funktionen.
Slutsats
Jag hoppas att du har lärt dig om ködatastrukturen och dess implementering. Det var allt för kön. Du kan använda kön på olika ställen där det behöver bearbetas i FIFO(First In/First Out) ordning. Använd kö vid problemlösning närhelst du får väskan att använda den.
Intresserad av att bemästra Python? Kolla in dessa lärresurser.
Glad kodning 🙂 👨💻