...
Structuri de date

Stiva și coada: ce sunt și prin ce diferă

Pe scurt

Stiva și coada sunt două structuri de date în care adaugi și scoți elemente pe rând. Diferența e ordinea: în stivă iese primul ultimul element pus (LIFO, ca o stivă de farfurii), iar în coadă iese primul cel venit primul (FIFO, ca la casa de marcat). Ambele fac operațiile de bază în O(1) și stau în spatele butonului Înapoi din browser, al lui Undo și al parcurgerii BFS.

  • LIFOstiva: ultimul intrat, primul ieșit
  • FIFOcoada: primul venit, primul servit
  • O(1)adăugare și scoatere
  • 2lecții gratuite, fără card
STIVĂ ȘI COADĂ 123 push / pop ↕ 749 ← iese primul intră ← append / popleft O(1) LIFO · FIFO

Stiva și coada, în acțiune

Apasă pe butoane și urmărește linia de Python de sub fiecare structură. Ai alături și un hash map, a treia structură folosită peste tot.

Stiva

ultimul intrat, primul ieșit
stiva = [] Lecția despre stivă →

Coada

primul venit, primul servit
coada = deque() Lecția despre coadă →

Hash map

găsești o cheie dintr-un salt
varste = {} Lecția despre hash map →

Operațiile stivei și ale cozii

OperațiaStivăCoadăCost
adaugăpush: pune deasupraenqueue: pune la capătul coziiO(1)
scoatepop: ia de deasupradequeue: ia din fațăO(1)
priveștetop / peek: elementul de deasuprafront / peek: primul din coadăO(1)
e goală?emptyemptyO(1)

Nu poți lua direct un element din mijloc: asta e regula care le face utile. Dacă ai nevoie de acces la orice poziție, folosești un tablou (listă), iar dacă vrei să adaugi și să scoți la ambele capete, un deque (coadă cu două capete).

Stiva și coada în C++, Python și Java

În C++ ai stack și queue din STL, în Python listă și deque, în Java ArrayDeque. Plus problema clasică a parantezelor.

from collections import deque

stiva = []
stiva.append(1)          # push
stiva.append(2)
print(stiva[-1])         # 2: vârful stivei
print(stiva.pop())       # 2: ultimul intrat iese primul

coada = deque()
coada.append(1)          # intră la coadă
coada.append(2)
print(coada[0])          # 1: primul din coadă
print(coada.popleft())   # 1: primul venit iese primul

Încearcă: paranteze valide cu o stivă

Problema din lecția 52 a cursului de algoritmi. Scrii codul Python în editor și primești verificarea pe loc.

Exercițiu din lecția 52 · cursul de algoritmi

Paranteze valide

Scrie funcția paranteze_valide(text) care returnează True dacă parantezele din text sunt valide și False altfel, folosind o stivă. Testele sunt deja scrise.

  1. Creează dicționarul cu perechile și o listă goală stiva.
  2. Pentru o paranteză deschisă: append. Pentru una închisă: verifică vârful și fă pop.
  3. La final, returnează dacă stiva este goală. Trebuie să apară: True, False, True, False, True, False.
Indiciu: Textul gol '' este valid: bucla nu se execută, stiva rămâne goală, deci rezultatul este True.
def paranteze_valide(text):
    pereche = {')': '(', ']': '[', '}': '{'}
    stiva = []
    for c in text:
        if c in pereche:
            if not stiva or stiva[-1] != pereche[c]:
                return False
            stiva.pop()
        else:
            stiva.append(c)
    return len(stiva) == 0


print(paranteze_valide('()[]{}'))
print(paranteze_valide('([)]'))
print(paranteze_valide('{[]}'))
print(paranteze_valide('(('))
print(paranteze_valide(''))
print(paranteze_valide(')('))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Unde se folosesc stiva și coada

  • Stiva: Undo în editoare, butonul Înapoi din browser, verificarea parantezelor, evaluarea expresiilor, apelurile de funcții (stiva de apeluri din recursivitate), parcurgerea DFS și backtracking-ul.
  • Coada: cozi de printare, cereri către un server, mesaje între aplicații, parcurgerea BFS și drumul minim într-un graf fără costuri.

La interviuri apar des: paranteze valide, stiva care știe minimul în O(1), coadă făcută din două stive și „câte zile până la o zi mai caldă” (stiva monotonă). Toate sunt lecții în cursul de algoritmi.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Am terminat cursul de C# incepatori si ma declar foarte multumita de acesta. Trainerul, Gabriel, a fost super ok si ne-a ajutat sa intelegem atunci cand aveam intrebari. Materia a fost foarte bine prezentata si parcursa foarte mult prin exercitii practice. Clar voi reveni si pentru cursul de intermediari!

Fotografia lui Mihaela Dumitru, cursant al Academiei ProgramatorilorMihaela DumitruRecenzie pe Google

La cursul de Java am avut placerea sa acumulez o multitudine de informatii foarte utile pentru a imi incepe drumul de programator de la trainerul Gabriel, un trainer vizibil foarte pasionat de ceea ce face, rabdator cu elevii sai si dornic sa ne dezvolte pe partea profesionala. Astept cu nerabdare urmatorul curs!!

Fotografia lui Bea Danciu, cursant al Academiei ProgramatorilorBea DanciuRecenzie pe Google

Recomand cursul online de programare, foarte bine structurat, explicatiile sunt usor de inteles si contine foarte multe exercitii practice.

Fotografia lui Ioana Dumitrache, cursant al Academiei ProgramatorilorIoana DumitracheRecenzie pe Google

Întrebări frecvente

Ce este o stivă?

O stivă este o structură de date în care elementele se adaugă și se scot doar de la un capăt, numit vârf. Ultimul element adăugat este primul scos (LIFO: last in, first out), ca într-o stivă de farfurii.

Ce este o coadă?

O coadă este o structură de date în care elementele se adaugă la un capăt și se scot de la celălalt. Primul element adăugat este primul scos (FIFO: first in, first out), ca într-un rând la casă.

Care e diferența dintre stivă și coadă?

Ordinea în care ies elementele: stiva scoate ultimul element adăugat (LIFO), coada pe primul (FIFO). Ambele adaugă și scot în O(1).

Cum fac o stivă în Python?

Folosești o listă: append() adaugă în vârf, pop() scoate din vârf, iar lista[-1] îți arată vârful. Pentru coadă folosești collections.deque, cu append() și popleft(), pentru că pop(0) pe o listă e O(n).

Ce este un deque?

Un deque (double-ended queue) este o coadă cu două capete: poți adăuga și scoate în O(1) atât la început, cât și la sfârșit. Poate fi folosit și ca stivă, și ca coadă.

Unde exersez stive și cozi?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai 8 lecții despre stive și cozi, cu probleme rezolvate în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.