7.3. Stiva și coada

Stiva este o structură liniară în care ultimul element introdus este primul eliminat: LIFO (Last In, First Out). Eliminarea se face din vârf.

Coada este o structură liniară în care primul element introdus este primul eliminat: FIFO (First In, First Out). Adăugarea se face la sfârșit, iar eliminarea la început.

Modelele sunt utile deoarece regula de acces este diferită. Operația Undo este naturală pentru o stivă, iar o coadă de așteptare este naturală pentru o coadă.

Operațiile conceptuale

Într-o stivă avem adăugare în vârf și eliminare din vârf. Într-o coadă avem adăugare la sfârșit și eliminare de la început.

Un teanc de farfurii ilustrează LIFO: ultima farfurie pusă este prima luată. O coadă la ghișeu ilustrează FIFO: primul sosit este primul servit.

Stivă

stiva = []

stiva.append(10)
stiva.append(20)
stiva.append(30)

print(stiva.pop())
print(stiva)

Valoarea 30 este eliminată prima. În această lecție, append() și pop() sunt folosite pentru a ilustra modelul; operațiile clasei list vor fi studiate sistematic în Capitolul 8.

Coadă — simulare simplă

coada = [10, 20, 30]

primul = coada[0]
coada = coada[1:]

print(primul)
print(coada)

Valoarea 10 este eliminată prima, respectând regula FIFO.

ALGORITM Stiva
    stiva ← goală
    pentru fiecare operație execută
        dacă este adăugare atunci
            adaugă în vârf
        dacă este eliminare și stiva nu este goală atunci
            elimină vârful
    sfârșit pentru
SFÂRȘIT ALGORITM

ALGORITM Coada
    coada ← goală
    pentru fiecare operație execută
        dacă este adăugare atunci
            adaugă la sfârșit
        dacă este eliminare și coada nu este goală atunci
            elimină primul
    sfârșit pentru
SFÂRȘIT ALGORITM

Problemă

Stiva este goală. Operațiile sunt: adaugă 5, adaugă 8, adaugă 2, elimină, adaugă 9, elimină. Determinați elementele eliminate și starea finală.

Analiză

Aplicăm regula LIFO: la fiecare eliminare luăm elementul din vârf.

Algoritm

stiva ← goală
adaugă 5
adaugă 8
adaugă 2
elimină vârful
adaugă 9
elimină vârful
scrie elementele eliminate și starea finală

Python

stiva = []
eliminate = []

stiva.append(5)
stiva.append(8)
stiva.append(2)

if len(stiva) > 0:
    eliminate.append(stiva.pop())

stiva.append(9)

if len(stiva) > 0:
    eliminate.append(stiva.pop())

print("Eliminate:", eliminate)
print("Stiva finală:", stiva)

Urmărirea variabilelor

Testare

Caz normal: operațiile date → se elimină 2 și 9.

Caz-limită: încercare de eliminare din structură goală.

Caz particular: un singur element urmat de eliminare → structura devine goală.

Justificarea soluției

La prima eliminare, 2 este ultimul introdus, deci este scos primul. După adăugarea lui 9, acesta devine noul vârf și este eliminat la a doua operație. Starea finală este [5, 8].

1. Simulați 3,7,pop,4,pop.
2. Simulați coada Ana,Bogdan,Carla,pleacă,intră Dan,pleacă.
3. Undo: stivă sau coadă?
4. Ghișeu: stivă sau coadă?
5. Ce se întâmplă la eliminarea dintr-o stivă goală?

6. Simulați o coadă și discutați eficiența eliminării repetate de la începutul unei liste.
7. După 1,2,3,4 în stivă, este posibilă eliminarea 4,2 fără eliminarea lui 3?
8. Proiectați un istoric Undo folosind modelul stivei.
9. Comparați LIFO și FIFO într-un tabel: regulă, adăugare, eliminare, exemplu.