Pomysł jest taki:
Na dwóch pierwszych stosach trzymamy elementy kolejki. Np. S1 = (en, ..., ej ), S2 = (e1, ..., ej-1) (pierwszy element na stosie S1 jest ostatnim elementem w kolejce, a pierwszy element na stosie S2 jest pierwszym elementem w kolejce.
Niezmiennikiem jest to, że mają one tą samą ilość elementów (z dokładnością do 1). Równowagę zachowujemy przez wykorzystanie trzeciego stosu.
Jak udowodnić, że zamortyzowany koszt operacji jest stały?
Z góry dzięki za pomoc.