Introducere
structurile de date organizează stocarea în computere, 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 găsi încorporându-le în software-ul dvs. pentru diverse sarcini.
este obișnuit ca stivele și cozile să fie implementate cu o matrice sau o listă legată. Ne vom baza pe List structura de date pentru a se potrivi atât stive și cozi.
cum funcționează?
stiva
stivele, așa cum sugerează și numele, urmează principiul Last-in-First-Out (LIFO). Ca și cum ar fi stivuit monedele una peste alta, ultima monedă pe care am pus-o pe partea de sus 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 partea de sus a stivei:
cozile, așa cum sugerează și numele, urmează principiul first-in-first-out (FIFO). Ca și cum ar aștepta într-o coadă pentru biletele de 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:
stive și cozi folosind liste
Python built-in Liststructura de date vine la pachet cu metode pentru a simula atât stivă și operațiunile de coadă.
să luăm în considerare un teanc de Litere:
putem folosi aceleași funcții pentru a implementa o coadă. Funcția pop ia opțional indexul elementului pe care dorim să îl recuperăm ca argument.
deci, putem folosipop cu primul index al listei, adică0, pentru a obține un comportament asemănător cozii.
luați în considerare o „coadă” de fructe:
Din nou, aici folosimappend șipop operațiunile listei pentru a simula operațiunile de bază ale unei cozi.
stive și cozi cu Biblioteca Deque
Python are undeque (pronunțat „deck”) bibliotecă 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 stocat:
Dacă doriți să aflați mai multe despre bibliotecadeque și alte tipuri de colecții pe care le oferă Python, puteți citi articolul nostru Introduction to Python ‘ s Collections Module.
implementări mai stricte în Python
dacă codul dvs. avea nevoie de o stivă și furnizați un List, nimic nu împiedică un programator să apeleze insertremove sau alte funcții de listă care vor afecta ordinea stivei! Acest lucru ruinează fundamental punctul de definire a unei stive, deoarece nu mai funcționează așa cum ar trebui.
există momente în care dorim să ne asigurăm că numai operațiunile valide pot fi efectuate pe datele noastre.
putem crea clase care expune doar Metodele necesare pentru fiecare structură de date.
pentru a face acest lucru, să creăm un nou fișier numitstack_queue.py și să definim două clase:
programatorii care folosescStack șiQueue sunt acum încurajați să utilizeze metodele furnizate pentru a manipula datele.
Exemple
Imaginați-vă că sunteți un dezvoltator care lucrează la un procesor de text nou. Sunteți însărcinat cu crearea unei funcții de anulare-permițând utilizatorilor să-și retragă acțiunile până la începutul sesiunii.
o stivă este o potrivire ideală pentru acest scenariu. Putem înregistra fiecare acțiune pe care utilizatorul o face împingând-o în stivă. Când utilizatorul dorește să anuleze o acțiune, o va scoate din stivă. Putem simula rapid caracteristica astfel:
cozile au utilizări pe scară largă ș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 apăsând o combinație de butoane. Aceste combinații de butoane pot fi stocate într-o coadă.
acum imaginați-vă că sunteți un dezvoltator de lucru pe un nou joc de lupte. În joc, de fiecare dată când este apăsat un buton, un eveniment de intrare este concediat. Un tester a observat că, dacă butoanele sunt apăsate prea repede, jocul procesează doar primul și mișcările speciale nu vor funcționa!
puteți rezolva asta cu o coadă. Putem întreba 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 dequeue. O mișcare specială poate fi elaborată astfel:
concluzie
stivele și cozile sunt structuri simple de date care ne permit să stocăm și să recuperăm datele secvențial. Într-o stivă, ultimul element pe care îl introducem este primul care iese. Într-o coadă, primul element pe care îl introducem este primul ieșit.
putem adăuga elemente într-o stivă folosind operațiapush și putem prelua elemente folosind operațiapop. Cu cozile, adăugăm elemente folosindenqueue și preluăm elemente folosinddequeue operație.
în Python, putem implementa stive și cozi doar folosind structura de date List încorporată. Python are, de asemenea,deque bibliotecă care poate oferi în mod eficient stivă și operațiunile de coadă într-un singur obiect. În cele din urmă, am făcut clasele noastre de stivă și coadă pentru un control mai strict al datelor noastre.
există multe cazuri de utilizare din lumea reală pentru stive și cozi, înțelegerea acestora ne permite să rezolvăm multe probleme de stocare a datelor într-un mod ușor și eficient.