Datastrukturer är grundläggande inom programmering. De ger oss verktyg för att organisera information på ett effektivt sätt. En av de mest grundläggande datastrukturerna är kön.
Denna artikel utforskar konceptet köer och hur man implementerar dem i Python.
Vad är en Kö?
En kö är en linjär datastruktur som följer principen Först In, Först Ut (FIFO – First In, First Out). Det är den motsatta principen till en stack.
Ett bra exempel på en kö är kön i en biograf. Låt oss visualisera en kö:
I biografkön kan en person bara gå fram till kassan när personen framför är klar. Den som kom först, blir först betjänad. Vi ser liknande köer i vardagliga situationer.
En ködatastruktur fungerar på samma sätt. Nu när du förstår grundprincipen för en kö, låt oss gå igenom de operationer man kan utföra på den.
Operationer i en Kö
Precis som i stackar, finns det två huvudsakliga operationer som används på en kö.
enqueue(data)
Lägger till ny data i slutet av kön. Detta kallas för könens ”bakre” del.
dequeue()
Tar bort data från början av kön. Denna plats kallas könens ”främre” del.
Låt oss illustrera operationerna för att göra det tydligare. En bild säger ofta mer än tusen ord.
Vi kan lägga till några hjälpfunktioner för att få mer information om kön. Det finns ingen gräns för antalet hjälpfunktioner, men vi fokuserar på de viktigaste.
bakre()
Returnerar det sista elementet i kön.
främre()
Returnerar det första elementet i kön.
är_tom()
Returnerar sant om kön är tom och falskt annars.
Jag vet att koncepten kan kännas lite tråkiga, men det är nödvändigt att förstå dem innan vi börjar implementera. Nu är det dags att koda!
Jag förutsätter att du har Python installerat. Om inte, kan du använda en onlinekompilator.
Kö Implementering
Att implementera en kö tar inte lång tid för en programmerare. När du väl har lärt dig det kommer du nog att tycka det är enkelt. Kanske kan du implementera det på bara några minuter efter den här genomgången.
Det finns flera sätt att implementera köer i Python. Låt oss gå igenom några metoder steg för steg.
#1. Lista
Listor är en inbyggd datatyp i Python. Vi kommer att använda listor för att implementera en kö i en klass. Vi kommer att gå igenom varje steg för att implementera en ködatastruktur från grunden, utan att använda några extra moduler. Låt oss börja.
Steg 1:
Skapa en klass som heter `Queue`.
class Queue: pass
Steg 2:
Vi behöver en variabel för att lagra data i kön. Vi kallar den `elements` och det kommer att vara en lista.
class Queue: def __init__(self): self.elements = []
Steg 3:
För att lägga till data i kön behöver vi en metod i klassen. Denna metod kallas `enqueue`, vilket vi diskuterade tidigare.
Metoden tar emot data och lägger till den i kön (listan `elements`). Vi kan använda `append`-metoden för listor 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 behöver ha en utgång, och det gör vi med metoden `dequeue`. Vi använder `pop`-metoden för listor, och du kanske redan hade gissat det.
`pop`-metoden tar bort ett element från listan på ett specifikt index. Om inget index anges tar den bort det sista elementet i listan.
Här behöver vi ta bort det första elementet i listan. Så vi måste skicka index 0 till `pop`-metoden.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Det är tillräckligt för en grundläggande kö. Men vi behöver hjälpfunktioner för att testa om operationerna fungerar korrekt. Låt oss implementera dem också.
Steg 5:
Metoden `rear()` används för att hämta det sista elementet i kön. Negativ indexering i listor hjälper oss att få det sista elementet.
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 använda indexering i listan för att få det första elementet.
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 listans längd.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Puh! Vi har slutfört implementeringen av köstrukturen. Nu behöver vi skapa ett objekt av klassen `Queue` för att kunna använda den.
Det gör vi nu:
class Queue: # ... if __name__ == '__main__': queue = Queue()
Nu har vi ett `Queue`-objekt. Låt oss testa det med några operationer.
- Kontrollera om kön är tom med metoden `is_empty`. Den borde returnera `True`.
- Lägg till siffrorna 1, 2, 3, 4, 5 i kön med `enqueue`-metoden.
- Metoden `is_empty` borde nu returnera `False`. Kontrollera det.
- Skriv ut det främre och bakre elementen med `front()` och `rear()`.
- Ta bort elementet från kön med `dequeue()`.
- Kontrollera det främre elementet. Det borde nu vara 2.
- Ta bort alla element från kön.
- `is_empty()` ska nu returnera `True`. Kontrollera igen.
Jag tror att det här räcker för att testa vår köimplementation. Testa med koden för stegen ovan.
Har du skrivit koden?
Oroa dig inte om du inte har gjort det.
Här är koden:
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())
Om du kör programmet ovan får du en utskrift som liknar följande resultat.
True False 1 5 2 5 True
Vi kan använda listor direkt som en kö. Den här implementeringen hjälper dig att förstå hur köer implementeras i andra programmeringsspråk.
Du kan också använda den här klassen i andra projekt. Det är bara att skapa ett objekt av den som vi gjorde tidigare.
Vi har implementerat en kö från grunden med hjälp av en lista. Finns det några inbyggda moduler för köer? Ja, det finns! Låt oss ta en titt på dem.
#2. deque från `collections`
Denna implementeras som en dubbelkö. Eftersom man kan lägga till och ta bort element från båda ändar kan vi använda den som både stack och kö. Låt oss se hur vi implementerar en kö med `deque`.
Den implementeras med hjälp av en dubbellänkad lista. Det ger konsekvent prestanda för infogning och borttagning av element. Att komma åt element i mitten av den länkade listan tar O(n) tid, men eftersom det inte behövs i en kö, är det inget problem.
Låt oss se några av de metoder som `deque` erbjuder oss.
- `append(data)` – lägger till data i kön.
- `popleft()` – tar bort det första elementet från kön.
Det finns inga direkta motsvarigheter till metoderna för ”främre”, ”bakre” eller ”är_tom”. Istället för de två första kan vi skriva ut hela kön. Och istället för `is_empty()` kan vi använda metoden `len()`.
Vi testade vår första kö genom att följa en rad steg. Låt oss göra samma sak här:
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)
Utskriften ser ut ungefär så här:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Queue från `queue`
Python har en inbyggd modul som heter `queue` som innehåller en klass som heter `Queue` för implementering av köer. Det liknar den vi skapade tidigare.
Låt oss först gå igenom de olika metoderna som klassen `Queue` erbjuder.
- `put(data)` – lägger till data i kön.
- `get()` – tar bort det första elementet i kön och returnerar det.
- `empty()` – returnerar sant om kön är tom och falskt annars.
- `qsize()` – returnerar storleken på kön.
Låt oss implementera en kö med dessa 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 utskriften:
True False 1 2 3 Size 2 4 5 True
Det finns fler metoder i klassen `Queue`. Du kan utforska dem med hjälp av den inbyggda funktionen `dir()`.
Slutsats
Jag hoppas att du nu har en bättre förståelse för ködatastrukturer och hur man implementerar dem. Det var allt om köer. Du kan använda köer när du behöver bearbeta data i FIFO-ordning. Använd köer när du har ett problem som passar dess struktur.
Är du intresserad av att bli en mästare på Python? Kolla in de här resurserna: Lär dig Python
Lycka till med kodningen! 🙂 👨💻