Informatyka MIMUW

Zadanie 1 (symulacja kolejki dwoma stosami)

Opracuj sposób implementacji kolejki typu FIFO z pomocą dwóch stosów w taki sposób, żeby zamortyzowany koszt operacji stosowych był stały. Dokonaj analizy kosztu metodami księgowania i funkcji potencjału.

Zadanie 2 (stos w tablicy dynamicznej)

Reprezentujemy stos w dynamicznej tablicy $S[1..n]$, gdzie $n = 2^m$, dla pewnego całkowitego $m \ge 0$. Poszczególne operacje implementujemy następująco: