Structuri de date: Stive și cozi de așteptare – Designveloper

De ce stive și cozi de așteptare?

Spre deosebire de o matrice, în stive și cozi de așteptare, în stive și cozi de așteptare, nu există o operație de acces aleatoriu (nu putem accesa un element direct cu un „index”). De obicei, avem mai puține metode/acțiuni pe care le putem efectua, cum ar fi push(), pop(), peek(), enqueue(), dequeue(), toate acestea se ocupă exclusiv de elementul de la începutul sau sfârșitul structurii de date.

Dar…

Întrebare: Acest lucru pare atât de limitativ, deoarece putem accesa doar primul sau ultimul element din structura de date. De ce am dori vreodată să folosim așa ceva? De ce nu folosim pur și simplu array-uri pentru mai multă flexibilitate?

Răspuns: Stivele și cozile de așteptare sunt de obicei „structuri de date de nivel superior” construite deasupra celor de nivel inferior (array sau listă legată) pentru a limita operațiile pe care le putem face asupra lor. Acesta este un avantaj dacă dorim un acces constrâns.

Având această capacitate limitată pe o structură de date este un avantaj, deoarece putem controla pe cel care utilizează această structură de date care efectuează doar operațiile corecte care sunt eficiente. De exemplu, nu va trebui să ne întrebăm dacă cineva a inserat la întâmplare un element în mijlocul listei noastre, încurcând unele invariante. Acest lucru ne-a salvat de o mulțime de probleme. Să le analizăm mai îndeaproape.

Ce este o stivă?

O stivă este o structură de date liniară cu un singur capăt care modelează o stivă din lumea reală prin faptul că are două operații primare, și anume, push și pop.

În această imagine de mai jos, am putut vedea că un membru de date este scos din vârful stivei și un altul este adăugat la el. Există un pointer de sus care indică blocul din partea de sus a stivei. Acest lucru se datorează faptului că elementele dintr-o stivă sunt întotdeauna eliminate și adăugate în partea de sus a grămezii. Acest comportament este cunoscut în mod obișnuit sub numele de LIFO (Last In First Out).

Operații pe stivă

Cele care urmează sunt cele 2 operații de bază care pot fi efectuate pe o stivă.

• Funcția Push: Adaugă un element în partea de sus a stivei
• Funcția Pop: Remove the top element (and might return it)

Vizualizare a operațiilor de bază ale stivei

În plus, următoarele funcții suplimentare sunt furnizate pentru o stivă, pentru a verifica starea acesteia.

• Funcția Peek: Returnează elementul superior al stivei fără a-l îndepărta sau șterge
• funcția isEmpty: Verifică dacă stiva este goală sau nu
• funcția isFull: Verifică dacă stiva este plină sau nu

Totul operează în partea de sus a stivei. Nu avem acces la nimic altceva decât la partea de sus. Acest lucru este esențial pentru a înțelege cum funcționează.

Analiză de complexitate

Următorul tabel de complexitate presupune că ați implementat o stivă folosind o listă legată

Aplicații ale stivei

Când și unde se folosește o stivă? folosim foarte mult Stack-ul în programare fără să ne dăm seama, iată câteva exemple:

• Poate fi folosit pentru evaluarea expresiilor (de exemplu: un algoritm shunting-yard pentru analizarea și evaluarea expresiilor matematice).
• Poate fi folosit pentru a implementa apeluri de funcții în programarea prin recursivitate.

• Utilizat prin mecanismele de anulare din editorii de text pentru a anula textul pe care l-am scris (Cmd + Z pe Mac OS și Ctrl + Z pe Windows)
• Utilizat în Browser pentru a naviga înapoi și înainte
• Poate fi folosit pentru a face o căutare în profunzime (Depth First Search – DFS) pe un grafic
• Utilizat în spatele scenei pentru a susține recursivitatea prin urmărirea apelurilor anterioare ale funcțiilor

Ce este o coadă de așteptare?

O coadă de așteptare este, de asemenea, o structură de date liniară care modelează cozile de așteptare din lumea reală prin faptul că are două operații principale, și anume enqueue (ne putem gândi la aceasta ca la „a intra în coadă”) și dequeue (ne putem gândi, de asemenea, la aceasta ca la „a șterge din coadă”). Această structură se numește „coadă” datorită faptului că seamănă cu o coadă din lumea reală – (în care oamenii așteaptă la coadă).

Care coadă are un capăt față și un capăt spate (uneori numit „spate”). Inserăm elemente prin spate și le eliminăm prin față.

O coadă este o structură FIFO (First In First Out – elementul plasat primul poate fi accesat primul) care poate fi întâlnită în mod obișnuit în multe limbaje de programare.

Operații cu coada de așteptare

Următoarele sunt cele 3 operații de bază care pot fi efectuate pe o coadă de așteptare.

• Funcția Enqueue: Adaugă un element la sfârșitul cozii
• Funcția Dequeue: Remove the element from the beginning of the queue
• Funcția Peeking: Privește valoarea de la începutul cozii fără să o elimine

Analiză de complexitate

După cum se poate observa în imagine, operațiile de enqueuing și dequeuing durează un timp constant O(1). Cu toate acestea, verificarea dacă un element este conținut în coada de așteptare are un timp liniar O(n), deoarece ar fi potențial necesar să parcurgem toate elementele.

Există, de asemenea, eliminarea elementelor (nu scoaterea din coadă) pe plan intern. Aceasta necesită timp liniar, deoarece trebuie să parcurgem toate elementele în cel mai rău caz.

Aplicații ale cozilor

• Utilizate pentru a gestiona firele de execuție în multithreading.
• Pot fi utilizate pentru a ține evidența în mod eficient a celor x elemente adăugate cel mai recent
• Gestionarea cererilor de pe serverele web unde dorim ca primul venit să fie primul servit. De exemplu: La un moment dat, serverul nostru web nu poate servi decât maximum 50 de persoane simultan.

Dacă vin 70 de cereri într-o perioadă scurtă de timp, atunci nu vom putea să le procesăm pe toate. Așa că webserverul scoate doar 50 de cereri din coadă și le pune pe celelalte 20 în așteptare. Când webserverul termină de procesat o cerere, o scoate din coadă pe următoarea cerere pentru a o servi și continuă să facă acest lucru până când coada este goală.

• Breadth-first search (BFS) graph traversal
• Utilizat pentru a implementa sisteme de coadă (de exemplu: cozi de prioritate)
• Utilizat în imprimantele de rețea: Imprimanta poate servi doar o singură cerere la un moment dat. Astfel, dacă alte cereri vin atunci când imprimanta este ocupată, programul care gestionează imprimanta nu va respinge aceste cereri, ci le va pune într-o coadă de așteptare pentru execuție. Prima cerere va fi servită prima (FIFO).

Sperăm că acest articol v-a oferit o imagine de ansamblu a stivei și cozilor de așteptare. Nu uitați să vă abonați la blogul nostru și să urmăriți Designveloper’s pe Facebook, Twitter și LinkedIn.

Și acestea sunt alte articole care v-ar putea plăcea:

• Ce este arhitectura aplicațiilor web?
• Structuri de date și aplicațiile lor
• Ce este notația Big O?

.