Introducere

Structurile de date organizează stocarea în calculatoare astfel încât să putem accesa și modifica eficient datele. Stivele și cozile sunt unele dintre cele mai vechi structuri de date definite în informatică.

Simplu de învățat și ușor de implementat, utilizările lor sunt comune și cel mai probabil vă veți trezi încorporându-le în software-ul dvs. pentru diverse sarcini.

Este obișnuit ca Stivele și cozile să fie implementate cu un Array sau Linked List. Ne vom baza pe structura de date List pentru a găzdui atât stive cât și cozi.

Cum funcționează?

Stack

Stack-urile, așa cum sugerează și numele, urmează principiul LIFO (Last-in-First-Out). Ca și cum am stivui monedele una peste alta, ultima monedă pe care o punem în vârf este cea care este prima care va fi scoasă din stivă mai târziu.

Pentru a implementa o stivă, prin urmare, avem nevoie de două operații simple:

• push – adaugă un element în partea de sus a stivei:

• pop – elimină elementul din vârful stivei:

Coadă

Coadele, așa cum sugerează și numele, urmează principiul First-in-First-Out (FIFO). Ca și cum ai aștepta la coadă pentru bilete la film, primul care stă la coadă este primul care cumpără un bilet și se bucură de film.

Pentru a implementa o coadă, prin urmare, avem nevoie de două operații simple:

• enqueue – adaugă un element la sfârșitul cozii:

• dequeue – elimină elementul de la începutul cozii:



Stacks and Queues using Lists

Structura de date încorporată în ListPython vine la pachet cu metode pentru a simula atât operațiile cu stive cât și cu cozi.

Să luăm în considerare o stivă de litere:

Putem folosi aceleași funcții pentru a implementa o coadă. Funcția pop primește opțional ca argument indicele elementului pe care dorim să-l recuperăm.

Așa că putem folosi pop cu primul indice al listei, adică 0, pentru a obține un comportament asemănător cu cel al unei cozi.

Considerați o „coadă” de fructe:

Din nou, aici folosim operațiile append și pop ale listei pentru a simula operațiile de bază ale unei cozi.

Stacks and Queues with the Deque Library

Python are o bibliotecă deque (pronunțat ‘deck’) care oferă o secvență cu metode eficiente pentru a lucra ca o stivă sau o coadă.

deque este prescurtarea de la Double Ended Queue – o coadă generalizată care poate obține primul sau ultimul element care este stocat:

Dacă doriți să aflați mai multe despre biblioteca deque și alte tipuri de colecții pe care le oferă Python, puteți citi articolul nostru Introducere în modulul Colecții din Python.

Impletări de stricate în Python

Dacă codul dumneavoastră are nevoie de o stivă și furnizați o List, nimic nu împiedică un programator să apeleze insert, remove sau alte funcții de listă care vor afecta ordinea din stivă! Acest lucru distruge în mod fundamental rostul definirii unei stive, deoarece aceasta nu mai funcționează așa cum ar trebui.

Există momente în care am dori să ne asigurăm că numai operațiile valide pot fi efectuate asupra datelor noastre.

Pot fi create clase care expun numai metodele necesare pentru fiecare structură de date.

Pentru a face acest lucru, să creăm un nou fișier numit stack_queue.py și să definim două clase:

Programatorii care folosesc clasele noastre Stack și Queue sunt acum încurajați să folosească în schimb metodele furnizate pentru a manipula datele.

Exemple

Imaginați-vă că sunteți un programator care lucrează la un procesor de texte nou-nouț. Aveți sarcina de a crea o funcție de anulare – care să le permită utilizatorilor să revină asupra acțiunilor lor până la începutul sesiunii.

O stivă este ideală pentru acest scenariu. Putem înregistra fiecare acțiune pe care o face utilizatorul împingând-o în stivă. Când utilizatorul dorește să anuleze o acțiune, o va scoate din stivă. Putem simula rapid funcția astfel:

Cozilele au utilizări larg răspândite și în programare. Gândiți-vă la jocuri precum Street Fighter sau Super Smash Brothers. Jucătorii din aceste jocuri pot efectua mișcări speciale prin apăsarea unei combinații de butoane. Aceste combinații de butoane pot fi stocate într-o coadă.

Imaginați-vă acum că sunteți un dezvoltator care lucrează la un nou joc de lupte. În jocul dumneavoastră, de fiecare dată când este apăsat un buton, se declanșează un eveniment de intrare. Un tester a observat că, dacă butoanele sunt apăsate prea repede, jocul îl procesează doar pe primul și mișcările speciale nu vor funcționa!

Puteți rezolva acest lucru cu o coadă. Putem pune la coadă toate evenimentele de intrare pe măsură ce vin. În acest fel, nu contează dacă evenimentele de intrare vin cu puțin timp între ele, toate vor fi stocate și disponibile pentru procesare. Când procesăm mișcările, le putem scoate din coadă. O mutare specială poate fi elaborată astfel:

Concluzie

Stackurile și cozile de așteptare sunt structuri de date simple care ne permit să stocăm și să recuperăm date în mod secvențial. Într-o stivă, ultimul element pe care îl introducem este primul care iese. Într-o coadă de așteptare, primul element pe care îl introducem este primul care iese.

Potem adăuga elemente la o stivă folosind operația push și recupera elemente folosind operația pop. Cu cozile de așteptare, adăugăm elemente folosind operația enqueue și recuperăm elemente folosind operația dequeue.

În Python, putem implementa stive și cozi de așteptare doar folosind structura de date încorporată List. Python dispune, de asemenea, de biblioteca deque care poate oferi în mod eficient operații de tip stivă și coadă într-un singur obiect. În cele din urmă, am realizat clasele noastre de stive și cozi pentru un control mai strict al datelor noastre.

Există multe cazuri de utilizare în lumea reală pentru stive și cozi, înțelegerea lor ne permite să rezolvăm multe probleme de stocare a datelor într-un mod simplu și eficient.

.