Datastrukturer er avgjørende i programmering. De gir oss verktøyene for å organisere data på en effektiv måte. En av de enkleste datastrukturene er køen.
I denne artikkelen skal vi utforske køer og hvordan de implementeres i Python.
Hva er en kø?
En kø er en lineær datastruktur som opererer etter First In/First Out (FIFO)-prinsippet. Dette står i motsetning til stakk-datastrukturen.
Vi kan tenke på en kø som en reell kø ved en billettluke. La oss se på en illustrasjon.
I en billettluke betjenes den andre personen først etter at den første er ferdig. Den første personen ankommer først, deretter den andre. Dette følger FIFO-prinsippet: den som ankommer først, blir betjent først. Vi ser liknende køer i hverdagen.
Kødatastrukturer fungerer på samme måte. Nå som du vet hva en kø er og dens prinsipper, la oss se på operasjonene som kan utføres på en kø.
Operasjoner i en kø
I likhet med en stakk har en kødatastruktur to hovedoperasjoner.
enqueue(data)
Legger til nye data bakerst i køen.
dequeue()
Fjerner data fra fronten av køen.
La oss se illustrasjoner av køoperasjoner for å forstå bedre. Et bilde sier mer enn tusen ord.
Vi kan definere noen hjelpefunksjoner for å hente ut mer informasjon om køen. Det er ingen begrensning for hvor mange hjelpefunksjoner vi kan ha, men la oss fokusere på de viktigste for nå.
bak ()
Returnerer det siste elementet i køen.
front()
Returnerer det første elementet i køen.
er_tom()
Returnerer true hvis køen er tom, ellers false.
Er du ikke lei av de teoretiske temaene?
Det er jeg!
Men vi må forstå konseptene før vi kan gå videre med implementasjonen. Men ikke bekymre deg, nå er det på tide å kode.
Jeg antar at du har Python installert. Hvis ikke, kan du bruke en online kompilator.
Implementering av en kø
En køimplementasjon burde ikke ta mer enn 15 minutter for en programmerer. Når du har forstått det, vil du sannsynligvis kunne implementere det på få minutter.
Det er flere måter å implementere en kø i Python. La oss se på ulike metoder steg for steg.
#1. Liste
Lister er en innebygd datatype i Python. Vi skal bruke lister til å implementere en kø i en klasse. Vi skal gå gjennom stegene for å implementere kødatastrukturen fra bunnen av uten å bruke moduler. La oss begynne.
Steg 1:
Lag en klasse som heter Kø.
class Queue: pass
Steg 2:
Vi trenger en variabel for å lagre dataene i køen. La oss kalle den `elementer`. Dette blir en liste.
class Queue: def __init__(self): self.elements = []
Steg 3:
For å sette inn data i køen, trenger vi en metode. Metoden heter `enqueue`, som vi har diskutert tidligere.
Metoden tar inn data og legger dem til i køen (`elementer`). Vi kan bruke `append`-metoden for å legge til data på slutten.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Steg 4:
Køen må ha en utgangsmetode, `dequeue`. Vi kommer til å bruke `pop`-metoden. Hvis du gjettet det, gratulerer!
Pop-metoden sletter et element fra listen med den gitte indeksen. Hvis ingen indeks er gitt, slettes det siste elementet. Vi må slette det første elementet, så vi sender inn indeks 0.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Dette er nok for køen, men vi trenger hjelpefunksjoner for å sjekke at operasjonene fungerer. La oss skrive disse også.
Steg 5:
Metoden `rear()` returnerer det siste elementet i køen. Negativ indeksering i lister gjør det enkelt å hente det siste elementet.
class Queue: # ... def rear(self): return self.elements[-1]
Steg 6:
Metoden `front()` returnerer det første elementet i køen. Vi kan hente det første elementet ved å bruke listeindeks.
class Queue: # ... def front(self): return self.elements[0]
Steg 7:
Metoden `is_empty()` sjekker om køen er tom. Vi kan sjekke dette ved å se på lengden til listen.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Puh! Implementeringen av køen er ferdig. Nå trenger vi å lage et objekt av `Queue`-klassen.
La oss gjøre det:
class Queue: # ... if __name__ == '__main__': queue = Queue()
Nå har vi et `Queue`-objekt. La oss teste det med noen operasjoner:
- Sjekk om køen er tom med `is_empty()`-metoden. Den skal returnere `True`.
- Legg til tallene 1, 2, 3, 4 og 5 med `enqueue`-metoden.
- Metoden `is_empty()` skal nå returnere `False`. Sjekk dette.
- Skriv ut første og siste element ved å bruke henholdsvis `front()` og `rear()`.
- Fjern et element fra køen med `dequeue()`.
- Sjekk første element. Den skal returnere 2.
- Fjern alle elementene fra køen.
- Metoden `is_empty()` skal nå returnere `True`. Sjekk det.
Dette burde være nok til å teste vår køimplementasjon. Skriv koden for hvert trinn for å teste køen.
Har du skrevet koden?
Ikke bekymre deg om du ikke har det.
Sjekk 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())
Du kan få et resultat som ligner på dette:
True False 1 5 2 5 True
Vi kan bruke lister direkte som en kødatastruktur. Implementasjonen over hjelper deg å forstå hvordan køer fungerer i andre språk.
Du kan også bruke denne klasseimplementasjonen i et annet program ved å lage et objekt som tidligere.
Vi har implementert en kø fra bunnen ved hjelp av lister. Finnes det innebygde moduler for køer? Ja! La oss se på dem.
#2. `deque` fra `collections`
Denne er implementert som en dobbel-ended kø. Fordi den støtter legging til og fjerning av elementer fra begge sider, kan den brukes som både en stakk og en kø. La oss se på en køimplementasjon med `deque`.
Den er implementert ved hjelp av en dobbeltlenket liste. Dette gir konsekvent ytelse for innsetting og fjerning av elementer. Tilgang til elementer midt i den lenkede listen tar O(n) tid, men vi bruker ikke tilgang til midten i en kø.
La oss se på metodene `deque` tilbyr oss:
- `append(data)` – legger dataene bakerst i køen.
- `popleft()` – fjerner det første elementet fra køen.
Det finnes ingen metoder for `front`, `rear` og `is_empty`. Vi kan skrive ut hele køen i stedet for `front` og `rear`. Og vi kan bruke `len`-metoden for å sjekke om den er tom.
Vi fulgte en rekke trinn for å teste køimplementasjonen tidligere. La oss gjøre det samme 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)
Dette vil produsere:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Kø fra `queue`
Python har en innebygd modul `queue` som tilbyr en `Queue`-klasse for køimplementasjoner. Denne ligner på den vi implementerte tidligere.
La oss se på de ulike metodene `Queue`-klassen tilbyr:
- `put(data)` – legger til data i køen.
- `get()` – fjerner og returnerer det første elementet i køen.
- `empty()` – returnerer `True` hvis køen er tom, ellers `False`.
- `qsize()` – returnerer lengden på køen.
La oss implementere en kø med disse metodene:
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())
Dette gir følgende resultat:
True False 1 2 3 Size 2 4 5 True
Det finnes andre metoder i `Queue`-klassen. Du kan utforske dem med den innebygde `dir`-funksjonen.
Konklusjon
Jeg håper du har lært om kødatastrukturen og dens implementasjon. Det var alt om køer for denne gang. Du kan bruke køer i ulike situasjoner der data skal behandles i FIFO-rekkefølge. Bruk køer når det passer i problemløsningen din.
Interessert i å mestre Python? Sjekk ut disse læringsressursene.
Lykke til med koding! 🙂 👨💻