Zásobník (stack)

Zásobník (stack) si vieme predstaviť ako krabice naukladané na sebe tak, že tvoria vežu. Novú krabicu môžeme pridať len na vrch, a odoberať krabice môžeme tiež len z vrchu. Okrem toho máme k dispozícii ešte jednu operáciu: môžeme sa pozrieť, čo je vo vrchnej krabici. V súvislosti so zásobníkom sa môžeme stretnúť aj s názvom LIFO -- "last in, first out", čiže "posledný dnu, prvý von" (pretože krabica, ktorú vezmeme zo zásobníka ako prvú, je tá, ktorú sme na zásobník položili ako poslednú).

Na čo je zásobník dobrý? Môžeme ním implementovať napríklad operáciu "undo" (späť) v textovom editore (a mnoho iných vecí) -- keď píšeme, každá zmena, ktorú v dokumente spravíme, sa uloží na zásobník. Keď klikneme na "undo" alebo stlačíme zodpovedajúcu kombináciu kláves, textový editor vytiahne zo zásobníka poslednú operáciu, ktorú sme spravili, a vykoná ju "naopak", čím uvedie dokument do stavu pred ňou.¹

Zásobník je abstraktná dátová štruktúra, čo znamená, že keď hovoríme o zásobníku, nemáme na mysli žiadnu konkrétnu implementáciu, ale len abstraktný objekt, ktorý podporuje nasledovné (vyššie spomínené) operácie:

• pridať prvok (na vrch),
• odobrať prvok (z vrchu),
• pozrieť sa na vrchný prvok.

Tieto tri operácie môžeme implementovať viacerými spôsobmi. Jednou z možných implementácií je implementácia pomocou poľa: vytvoríme si pole $A$ dlhé $n$ a premennú $vrch$, ktorá označuje, na ktorom indexe poľa sa nachádza vrchný prvok zásobníka. Na začiatku nastavíme $vrch = -1$ (pretože zásobník je prázdny, a teda sa jeho vrchný prvok nenachádza na žiadnom indexe v poli). Keď chceme pridať prvok, skontrolujeme, či $vrch + 1 < n$, a ak to platí, tak zväčšíme $vrch$ o $1$ a vložíme nový prvok na $vrch$-té miesto poľa $A$. (Ak je $vrch + 1$ rovný $n$, tak je celé pole plné, takže sa nám doň nový prvok nezmestí -- vtedy môžeme napríklad vyhlásiť chybu, alebo si vytvoriť nové, dlhšie pole, do ktorého prekopírujeme celý obsah poľa $A$ a pole $A$ zahodíme.) Keď chceme odobrať prvok, skontrolujeme, či $vrch \geq 0$, a ak to platí, tak zmenšíme $vrch$ o 1.² (Ak je $vrch$ menší ako $0$, znamená to, že zásobník je prázdny a nemáme aký prvok odobrať.) No a napokon, ak sa chceme pozrieť na vrchný prvok zásobníka, pozrieme sa na $A[vrch]$.

Ďalšou možnosťou je implementácia pomocou obojsmerne spájaného zoznamu. V tomto prípade nám stačí si pamätať pointer na posledný prvok zoznamu (resp. nulový pointer, ak je zásobník prázdny). Pri vkladaní nového prvku vyrobíme nový prvok zoznamu, prepojíme ho s doterajším posledným a zapamätáme si pointer naň ako pointer na posledný prvok. Pri vyberaní postupujeme naopak. (Samozrejme, nezabudneme skontrolovať, či náhodou zoznam -- a teda aj zásobník -- nebol prázdny.) Ak sa chceme pozrieť na posledný prvok, jednoducho budeme nasledovať pointer, ktorý si pamätáme.

Obe implementácie majú rovnaké zložitosti. Pamäťová zložitosť celej štruktúry je $n$. Časové zložitosti jednotlivých operácií sú rovnaké -- $O(1)$. (Toto platí iba ak sa pri implementácii poľom uspokojíme v prípade plného poľa s vyhlásením chyby. Ak namiesto toho vytvoríme nové pole a pôvodné do neho budeme chcieť nakopírovať, v najhoršom prípade bude mať operácia pridania nového prvku lineárnu časovú zložitosť.)