Coadă construită din două stive
O întrebare de interviu foarte populară: „Ai doar stive. Construiește o coadă.” Răspunsul folosește două stive și introduce o idee importantă: complexitatea amortizată, adică O(1) în medie pe operație, chiar dacă o operație anume poate fi mai lentă.
Ideea: o stivă inversează
Ai văzut că o stivă inversează ordinea. Dacă inversezi de două ori, revii la ordinea inițială. Deci: pui elementele într-o stivă de intrare, iar când trebuie scoase le muți într-o stivă de ieșire. În ieșire, primul venit ajunge în vârf.
intrare = [1, 2, 3]
iesire = []
while intrare:
iesire.append(intrare.pop())
print('ieșire:', iesire)
print('primul scos:', iesire.pop()) Completează clasa Coada cu metodele adauga(x), scoate() și primul() folosind doar două liste folosite ca stive (append și pop()). Mută din intrare în iesire doar când iesire este goală.
- adauga pune în self.intrare.
- scoate și primul: dacă self.iesire e goală, mută tot din intrare cu pop() + append.
- Trebuie să apară, pe linii: 1, 1, 2, 3, 3, 4.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Hash map, stive, cozi și liste înlănțuite.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan