Structurile de date joacă un rol cheie în lumea programării. Ele ne ajută să ne organizăm datele într-un mod care poate fi utilizat eficient. Coada este una dintre cele mai simple structuri de date disponibile.
În acest articol, vom afla despre Queue și implementarea sa în Python.
Cuprins
Ce este o coadă?
O coadă este o structură de date liniară care urmează principiul First In/First Out (FIFO). Este opus structurii de date Stack.
Putem compara coada cu o coadă reală la ghișeul de bilete de cinema. Să vedem ilustrația unei cozi, după cum urmează.
Dacă observați coada la ghișeu, a doua persoană poate merge la ghișeu numai după ce prima persoană își încheie munca. Aici vine prima persoană la ghișeu și apoi a doua persoană. Deci, aici oamenii urmează principiul FIFO (primul intrat/primul ieșit). Oricine vine primul, el/ea va termina primul lucrarea. Putem vedea un tip similar de cozi în viața noastră de zi cu zi.
Structura de date Queue urmează, de asemenea, același principiu. Acum, știți ce sunt cozile și principiul lor. Să vedem operațiunile care pot fi efectuate pe o structură de date de coadă.
Operații în coadă
Similar cu stiva, vom găsi două operații principale într-o structură de date de coadă.
coadă (date)
Adaugă date noi la coadă la sfârșit. Partea laterală se numește spate.
scoate la coada()
Elimină datele din partea din față a cozii. Partea laterală se numește față.
Să vedem ilustrațiile operațiilor de coadă pentru o mai bună înțelegere. O imagine spune cât o mie de cuvinte.
Putem scrie câteva funcții de ajutor pentru a obține mai multe informații despre coadă. Nu există limită pentru numărul de funcții de ajutor pe care le veți avea. Să rămânem la cele mai importante odată menționate mai jos deocamdată.
spate()
Returnează primul element de la sfârșitul cozii.
față()
Returnează primul element de la începutul cozii.
este gol()
Returnează dacă coada este goală sau nu.
Nu este plictisitor pentru tine? Mă refer la subiectele conceptuale.
Pentru mine da!
Dar, nu putem face nimic fără să cunoaștem conceptele. Trebuie să-l cunoaștem înainte de implementare. Nu vă faceți griji, este timpul să ne murdărim mâinile cu niște coduri.
Presupun că aveți python instalat pe computer, dacă nu, puteți încerca și compilatorul online.
Implementarea cozii
Implementarea unei cozi nu va dura mai mult de 15 minute pentru un programator. Odată ce ai învățat, o vei spune. Poate îl puteți implementa în câteva minute după acest tutorial.
Există mai multe moduri de a implementa coada în Python. Să vedem diferite implementări de coadă pas cu pas.
#1. Listă
Lista este un tip de date încorporat în Python. Vom folosi tipul de date listă pentru a implementa o coadă într-o clasă. Vă vom ghida prin diferiți pași pentru a implementa structura de date a cozii de la zero, fără module. Să sărim în ea.
Pasul 1:
Scrieți o clasă numită Coadă.
class Queue: pass
Pasul 2:
Trebuie să existe o variabilă pentru a stoca datele cozii în clasă. Să-i denumim elemente. Și este o listă, desigur.
class Queue: def __init__(self): self.elements = []
Pasul 3:
Pentru a introduce date în coadă, avem nevoie de o metodă în clasă. Metoda se numește enqueue, așa cum am discutat deja în secțiunea anterioară a tutorialului.
Metoda preia unele date și le adaugă la coadă (elemente). Putem folosi metoda append a tipului de date listă pentru a adăuga date la sfârșitul cozii.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Pasul 4:
Coada trebuie să aibă o ieșire. Și asta se numește decodare. Cred că ați ghicit deja că vom folosi metoda pop a tipului de date listă. Dacă ai ghicit sau nu, noroc!
Metoda pop a tipului de date listă șterge un element din lista indexului dat. Dacă nu am dat niciun index, atunci acesta șterge ultimul element al listei.
Aici, trebuie să ștergem primul element al listei. Deci, trebuie să trecem indicele 0 la metoda pop.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Este suficient pentru o coadă. Dar, avem nevoie de funcțiile de ajutor pentru a testa dacă operațiunile din coadă funcționează corect sau nu. Să scriem și funcțiile helper.
Pasul 5:
Metoda rear() este folosită pentru a obține ultimul element al cozii. Indexarea negativă în tipul de date listă ne ajută să obținem ultimul element al cozii.
class Queue: # ... def rear(self): return self.elements[-1]
Pasul 6:
Metoda front() este folosită pentru a obține primul element al cozii. Putem obține primul element al cozii folosind indexul listei.
class Queue: # ... def front(self): return self.elements[0]
Pasul 7:
Metoda is_empty() este folosită pentru a verifica dacă coada este goală sau nu. Putem verifica lungimea listei.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Pf! a finalizat partea de implementare a structurii de date a cozii. Trebuie să creăm un obiect pe care să îl utilizăm clasa Queue.
Hai să o facem.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Acum, avem un obiect Queue. Să-l testăm cu o serie de operații.
- Verificați dacă coada este goală sau nu folosind metoda is_empty. Ar trebui să returneze True.
- Adăugați numerele 1, 2, 3, 4, 5 la coadă utilizând metoda coadă.
- Metoda is_empty ar trebui să returneze False. Verifică.
- Imprimați elementele din față și din spate folosind metodele față și, respectiv, din spate.
- Scoateți elementul din coadă folosind metoda de scoatere din coadă.
- Verificați elementul frontal. Ar trebui să returneze elementul 2.
- Acum, eliminați toate elementele din coadă.
- Metoda is_empty ar trebui să returneze True. Verifică.
Cred că este suficient pentru a testa implementarea cozii. Scrieți codul pentru fiecare pas menționat mai sus pentru a testa coada.
Tu ai scris codul?
Nu, nu-ți face griji.
Verificați codul de mai jos.
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())
Cred că rulezi programul de mai sus. Puteți obține o ieșire similară cu următorul rezultat.
True False 1 5 2 5 True
Putem folosi direct tipul de date listă ca structură de date de coadă. Implementarea de mai sus a cozii vă ajută să înțelegeți mai bine implementarea cozii în alte limbaje de programare.
De asemenea, puteți utiliza implementarea clasei de mai sus a unei cozi într-un program diferit al unui proiect prin simpla creare a obiectului așa cum am făcut mai devreme.
Am implementat coada de la zero folosind tipul de date listă. Există module încorporate pentru coadă? Da! avem implementări încorporate de coadă. Să-i vedem.
#2. deque din colectii
Este implementat ca o coadă dublă. Deoarece acceptă adăugarea și eliminarea elementelor de la ambele capete, îl putem folosi ca stivă și coadă. Să vedem implementarea cozii folosind decoda.
Este implementat folosind alte structuri de date numite listă dublu legată. Deci performanța de inserare și ștergere a elementelor este consistentă. Accesarea elementelor din lista de legătură din mijloc a durat O(n) timp. Îl putem folosi ca coadă, deoarece nu este nevoie să accesăm elementele din mijloc din coadă.
Să verificăm diferitele metode pe care ni le oferă coada.
- append(data) – folosit pentru a adăuga datele la coadă
- popleft() – folosit pentru a elimina primul element din coadă
Nu există metode alternative pentru față, spate și is_empty. Putem imprima întreaga coadă în locul metodelor din față și din spate. Apoi, putem folosi metoda len pentru a verifica dacă coada este goală sau nu.
Am urmat o serie de pași pentru a testa implementarea cozii în precedentul. Să urmăm și aici aceeași serie de pași.
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)
Veți obține un rezultat similar cu următorul rezultat.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Coadă de la coadă
Python are un modul încorporat numit coadă care servește o clasă numită Queue pentru implementarea cozii. Este similar cu cel pe care l-am implementat înainte.
Mai întâi, să verificăm diferite metode ale clasei Queue.
- put(data) – adaugă sau împinge datele în coadă
- get() – elimină primul element din coadă și îl returnează
- empty() – returnează dacă stiva este goală sau nu
- qsize() – returnează lungimea cozii.
Să implementăm coada cu metodele de mai sus.
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())
Verificați rezultatul codului de mai sus.
True False 1 2 3 Size 2 4 5 True
Există și alte metode în clasa Queue. Le puteți explora folosind funcția încorporată dir.
Concluzie
Sper că ați învățat despre structura datelor cozii și implementarea acesteia. Asta e pentru coadă. Puteți utiliza coada în diferite locuri unde trebuie procesată în ordinea FIFO (primul intrat/primul ieșit). Utilizați coada în rezolvarea problemelor ori de câte ori primiți cazul să-l folosească.
Te interesează să stăpânești Python? Consultați aceste resurse de învățare.
Codare fericită 🙂 👨💻