În universul programării, structurile de date sunt fundamentale. Ele ne oferă modalități eficiente de a organiza și gestiona informațiile. Dintre aceste structuri, coada (Queue) se distinge prin simplitatea sa.
Acest articol își propune să exploreze conceptul de coadă și să demonstreze implementarea sa în limbajul Python.
Ce reprezintă o coadă?
Coada este o structură de date de tip liniar, care funcționează pe baza principiului „Primul Intrat, Primul Ieșit” (FIFO – First In, First Out). Ea se opune structurii de date de tip stivă (Stack).
Pentru a înțelege mai bine, putem compara coada cu o coadă fizică la un ghișeu de bilete. Să analizăm o ilustrație a unei cozi:
Într-o coadă la ghișeu, o persoană va fi servită abia după ce persoana din fața sa își termină treaba. Ordinea este clară: primul venit este primul servit. Acest mod de operare, FIFO, este esențial în funcționarea cozilor. Vedem astfel de cozi în diverse situații din viața de zi cu zi.
Structura de date coadă respectă același principiu. Acum, că am înțeles conceptul, să vedem ce operații sunt posibile pe o coadă.
Operații specifice cozii
Similar stivei, în coadă vom găsi două operații principale:
Încadrare (enqueue)
Această operație adaugă date noi la capătul cozii, denumit și „spate”.
Extragere (dequeue)
Această operație elimină datele de la începutul cozii, denumit și „față”.
Pentru a înțelege mai bine, să analizăm ilustrații ale acestor operații. O imagine poate valora cât o mie de cuvinte.
Pentru a ne oferi mai multe informații despre coadă, putem scrie câteva funcții auxiliare. Nu există o limită la numărul de funcții auxiliare, dar ne vom concentra pe cele esențiale, menționate mai jos:
Spate (rear)
Această funcție returnează ultimul element din coadă.
Față (front)
Această funcție returnează primul element din coadă.
Este goală (is empty)
Această funcție verifică dacă coada este goală și returnează o valoare booleană (adevărat sau fals).
Nu vi se pare că discutăm prea mult despre concepte? Pentru mine, da!
Dar, nu putem trece la implementare fără să cunoaștem teoria. Este timpul să trecem la codificare. Presupun că aveți Python instalat, dar puteți folosi și un compilator online.
Implementarea cozii în Python
Odată ce înțelegeți logica, implementarea cozii nu va dura mai mult de câteva minute. Există mai multe moduri de a implementa o coadă în Python, pe care le vom analiza pas cu pas:
#1. Folosind o Listă
Lista este un tip de date încorporat în Python. O vom folosi pentru a crea o coadă într-o clasă, fără a apela la module externe. Iată pașii:
Pasul 1:
Definim o clasă numită „Coada”.
class Queue: pass
Pasul 2:
Avem nevoie de o variabilă pentru a stoca datele cozii. O vom numi „elemente” și va fi o listă.
class Queue: def __init__(self): self.elements = []
Pasul 3:
Pentru a adăuga date în coadă, definim metoda „enqueue”. Aceasta va primi date și le va adăuga la coadă folosind metoda „append” a listei.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Pasul 4:
Pentru a elimina date din coadă, definim metoda „dequeue”. Vom folosi metoda „pop” a listei, specificând indexul 0 pentru a elimina primul element.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Acesta este miezul cozii. Dar avem nevoie de funcții auxiliare pentru testare.
Pasul 5:
Metoda „rear” returnează ultimul element al cozii, folosind indexarea negativă a listei.
class Queue: # ... def rear(self): return self.elements[-1]
Pasul 6:
Metoda „front” returnează primul element al cozii folosind indexul 0 al listei.
class Queue: # ... def front(self): return self.elements[0]
Pasul 7:
Metoda „is_empty” verifică dacă coada este goală, analizând lungimea listei.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Gata cu implementarea! Acum, să creăm un obiect al clasei „Coada” și să-l testăm.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Avem un obiect „queue”. Să-l testăm:
- Verificăm dacă coada este goală folosind metoda „is_empty” (ar trebui să returneze True).
- Adăugăm numerele 1, 2, 3, 4 și 5 folosind metoda „enqueue”.
- Metoda „is_empty” ar trebui să returneze False.
- Afișăm elementele din față și din spate folosind metodele „front” și „rear”.
- Eliminăm un element folosind metoda „dequeue”.
- Verificăm din nou elementul din față (ar trebui să fie 2).
- Eliminăm toate elementele din coadă.
- Metoda „is_empty” ar trebui să returneze True.
Acesta este un test bun pentru coadă. Puteți scrie codul pentru fiecare pas.
Ați scris codul?
Nu? Atunci 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())
Dacă rulați codul, veți obține rezultatul:
True False 1 5 2 5 True
Putem folosi lista direct ca o coadă. Această implementare a cozii vă ajută să înțelegeți mai bine implementarea în alte limbaje. Puteți folosi această clasă într-un proiect, creând un obiect.
Am implementat coada de la zero. Dar există module încorporate pentru coadă. Să le analizăm.
#2. deque din „collections”
Deque (dublă coadă) este o structură care permite adăugarea și eliminarea de elemente de la ambele capete, putând fi folosită atât ca stivă, cât și ca coadă. Ea este implementată folosind liste dublu înlănțuite, ceea ce asigură o performanță constantă la inserare și ștergere. Deoarece nu este nevoie să accesăm elementele din mijlocul unei cozi, performanța rămâne bună.
Să vedem metodele puse la dispoziție de deque:
- append(data) – adaugă date la coadă.
- popleft() – elimină primul element din coadă.
Nu există metode separate pentru față, spate și is_empty. Putem afișa întreaga coadă și utiliza „len” pentru a verifica dacă coada este goală.
Urmăm aceeași serie de pași pentru testare:
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)
Rezultatul va fi similar cu:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Coadă din modulul „queue”
Python include un modul numit „queue”, care conține clasa „Queue”. Aceasta este similară cu implementarea noastră inițială.
Să vedem metodele clasei „Queue”:
- put(data) – adaugă date în coadă.
- get() – elimină primul element din coadă și îl returnează.
- empty() – returnează True dacă coada este goală.
- qsize() – returnează lungimea cozii.
Să implementăm coada folosind aceste metode:
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())
Rezultatul va fi:
True False 1 2 3 Size 2 4 5 True
Clasa Queue are mai multe metode, pe care le puteți explora cu funcția „dir”.
Concluzie
Sper că ați înțeles structura de date coadă și implementarea sa. Coada este utilă în situații unde procesarea se face în ordinea FIFO. Folosiți această structură când se prezintă oportunitatea. Dacă doriți să învățați mai mult despre Python, puteți consulta resursele disponibile online.
Spor la codare! 👨💻