Ce vei învăța astăzi?
După această lecție vei înțelege cum funcționează stiva și coada, care sunt principiile LIFO și FIFO și cum le simulăm în Python.
Stiva - principiul LIFO
Definiție: Stiva este o structură de date care respectă principiul LIFO (Last In, First Out), adică ultimul element introdus este primul scos.
Gândește-te la o stivă de farfurii: o pui pe cea mai nouă deasupra și o iei tot pe cea mai nouă, adică pe cea din vârf.
Exemple de stive în viața reală
- Farfuriile stivuite: ultima așezată este prima luată
- Anularea ultimei acțiuni (Ctrl+Z): se anulează mai întâi ultima modificare
- Istoricul browserului: butonul „înapoi" merge la pagina vizitată cel mai recent
- Hainele în valiză: ultima haină împachetată este prima scoasă
Simularea unei stive în Python
Pentru a adăuga un element folosim append(), iar pentru a scoate ultimul element folosim pop() (fără argument).
stiva = []
stiva.append(10)
stiva.append(20)
stiva.append(30)
print(stiva)
x = stiva.pop()
print("Scos:", x)
print(stiva)
Observă: se scoate 30, adică elementul adăugat cel mai recent, nu 10 care a fost primul adăugat.
Coada - principiul FIFO
Definiție: Coada este o structură de date care respectă principiul FIFO (First In, First Out), adică primul element introdus este primul scos.
Gândește-te la un rând la ghișeu: cel care a stat la rând primul este servit primul.
Exemple de cozi în viața reală
- Rândul la cinema: primul care a ajuns intră primul
- Rândul la ghișeu: oamenii sunt serviți în ordinea sosirii
- Mesajele de la cofetărie: comenzile se pregătesc în ordinea primirii
- Imprimanta de la școală: documentele sunt tipărite în ordinea trimiterii
Simularea unei cozi în Python
Pentru a adăuga un element la coadă folosim append(), iar pentru a scoate primul element folosim pop(0).
coada = []
coada.append("Andrei")
coada.append("Maria")
coada.append("Ion")
print(coada)
x = coada.pop(0)
print("Scos:", x)
print(coada)
Observă: se scoate Andrei, adică elementul adăugat primul. Cozile păstrează ordinea sosirii!
Comparație: stivă, coadă, listă
Toate trei sunt modele liniare de organizare a datelor, dar se deosebesc prin felul în care adăugăm și scoatem elemente.
| Structură | Unde adăugăm? | De unde scoatem? | Principiu |
|---|---|---|---|
| Stiva | La final (vârf) | Din final (vârf) | LIFO |
| Coada | La final | Din început | FIFO |
| Lista | Unde dorim | De unde dorim | Acces direct |
Când folosim fiecare?
- Stiva: când trebuie să păstrăm „ultima acțiune" (anulare, istoric)
- Coada: când trebuie să respectăm ordinea sosirii (rânduri, mesaje)
- Lista: când avem nevoie de acces direct la orice element
Exercițiu de completare
Completează enunțul despre stivă și coadă cu cuvintele potrivite:
O ______ respectă principiul ______: ultimul element introdus este primul scos. O ______ respectă principiul ______: primul element introdus este primul scos.
Bancă de cuvinte:
Test de înțelegere
Test rapid - stivă și coadă:
1. Structura în care ultimul element introdus este primul scos se numește:
2. Structura în care primul element introdus este primul scos se numește:
3. LIFO este prescurtarea pentru:
pop() (ultimul introdus), iar la coadă cu pop(0) (primul introdus). Dacă folosești pop() în loc de pop(0), coada se transformă în stivă și ordinea datelor se inversează.Aprofundare
Stiva în funcțiile programului. Chiar dacă nu o scrii explicit, orice program folosește o stivă: atunci când o funcție o apelează pe alta, adresele de revenire se pun pe stiva de apeluri (call stack) și se scot în ordine inversă. De aceea, atunci când înveți LIFO, înțelegi de fapt un mecanism folosit de procesor la fiecare apel de funcție.
Coada în sisteme reale. Imprimantele, serverele de mesaje și sistemul de operare folosesc cozi pentru a servi cererile în ordinea sosirii. Un document trimis mai devreme trebuie tipărit mai întâi, altfel ar apărea haos. Coada garantează corectitudinea în astfel de situații.
Eficiența operațiilor. La o stivă, append() și pop() lucrează pe ultimul element, deci se execută foarte repede. La o coadă simulată cu listă, pop(0) scoate primul element și trebuie să mute toate elementele rămase cu o poziție la stânga, ceea ce poate fi lent pentru cozi foarte lungi. Pentru cozi eficiente se poate folosi structura deque din modulul collections, care scoate rapid din ambele capete.
Interzicerea accesului la mijloc. Prin definiție, o stivă sau o coadă nu permite accesul direct la un element din mijloc. Dacă ai nevoie de acces direct la orice poziție, folosește o listă obișnuită; stiva și coada se aleg când ordinea de procesare este importantă.
Cazuri particulare. pop() pe o listă goală produce IndexError, deci înainte de a scoate verificăm cu if stiva: sau cu while stiva:. La coadă, pop(0) pe o coadă goală produce aceeași eroare.
Quiz de consolidare
Quiz de consolidare - stivă și coadă:
1. Pentru a adăuga un element la o stivă în Python folosim:
2. Pentru a scoate ultimul element introdus (LIFO) folosim:
3. Pentru a scoate primul element introdus (FIFO) folosim:
PbInfo - Inversarea unei liste
Enunț:
Cerință: Se citește o listă de numere. Să se afișeze elementele listei în ordine inversă, folosind o stivă (cu append() și pop()).
Date de intrare:
Programul citește de la tastatură numerele, separate prin spații.
Date de ieșire:
Programul va afișa numerele în ordine inversă, separate prin spații.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele listei sunt numere întregi.
Exemplu:
Intrare:
1 2 3 4 5
Ieșire:
5 4 3 2 1
Cum gândim soluția:
- Citim numerele în lista v
- Cat timp lista nu e goală, scoatem ultimul element cu
pop()și îl adăugăm în lista r cuappend() - Afișăm lista r, care conține elementele în ordine inversă
Scrie soluția în Python:
Soluție corectă:
v = list(map(int, input().split()))
r = []
while v:
r.append(v.pop())
print(*r)
Ce învățăm: pop() scoate mereu ultimul element, deci o stivă ne ajută să inversăm ordinea unei liste.
PbInfo - Eliminarea primului element
Enunț:
Cerință: Se citește numărul natural n, apoi n numere întregi, ce reprezintă o coadă. Să se elimine primul element al cozii, cu pop(0), și să se afișeze elementele rămase.
Date de intrare:
Programul citește de la tastatură numărul n, apoi pe linia următoare cele n numere, separate prin spații.
Date de ieșire:
Programul va afișa elementele rămase în coadă după eliminarea primului element.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele listei sunt numere întregi.
Exemplu:
Intrare:
4 10 20 30 40
Ieșire:
20 30 40
Cum gândim soluția:
- Citim n și numerele în lista v
- Eliminăm primul element cu
v.pop(0) - Afișăm lista rămasă
Scrie soluția în Python:
Soluție corectă:
n = int(input()) v = list(map(int, input().split())) v.pop(0) print(*v)
Ce învățăm: pop(0) scoate primul element al listei, ca la o coadă: primul introdus este primul scos.
Exercițiul Practic: Stiva și coada în viața reală
Sarcini de lucru
Completează următoarele sarcini pentru a înțelege când folosim stiva și când folosim coada
Sarcina 1: Situații reale de stivă și coadă
Cerință: Descrie, în cuvinte proprii, o situație reală care funcționează ca o stivă (LIFO) și una care funcționează ca o coadă (FIFO).
Soluție pentru Sarcina 1:
Exemplu de răspuns corect:
Stivă (LIFO): o grămadă de farfurii în bucătărie. Ultima farfurie așezată deasupra este prima care se ia. Coadă (FIFO): rândul elevilor la cantină. Primul elev care a ajuns la rând este servit primul.
Verifică: la stivă contează „ultimul intrat, primul ieșit", iar la coadă „primul intrat, primul ieșit".
Sarcina 2: Coada de clienți
Cerință: Scrie un program care simulează o coadă cu 3 clienți: adaugă-i pe rând cu append(), apoi scoate-i unul câte unul cu pop(0), afișând de fiecare dată clientul servit.
Soluție pentru Sarcina 2:
coada = []
coada.append("Client 1")
coada.append("Client 2")
coada.append("Client 3")
while coada:
print("Servit:", coada.pop(0))
Verifică: clienții sunt serviți în ordinea în care au intrat în coadă, respectând principiul FIFO.