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.

Pamäťová zložitosť zásobníka je $n$. Časové zložitosti jednotlivých operácií sú rovnaké -- $O(1)$.

Implementácia pomocou listu

Zásobník, o ktorom sme hovorili, môžeme implementovať rôznymi spôsobmi. Jedným z bežných riešení je použiť list.

Pridanie prvku (operácia "push")

Pre pridanie nového prvku na "vrch" zásobníka využijeme metódu .append(). Táto metóda pridá prvok na koniec zoznamu, a tým efektívne simuluje položenie novej krabice na vrch veže.

zasobnik = []  # Inicializácia prázdneho zásobníka (ako prázdny zoznam)
zasobnik.append("kniha")  # Pridáme prvok "kniha"
zasobnik.append("pero")   # Pridáme prvok "pero"

Odobratie prvku (operácia "pop")

Na odobratie vrchného prvku zo zásobníka použijeme metódu .pop(). Táto metóda nielenže prvok odstráni z konca zoznamu, ale ho aj vráti, čo je užitočné, ak s odobraným prvkom potrebujeme ďalej pracovať.

vrchny_prvok = zasobnik.pop()
print(vrchny_prvok) # Výstup: pero (posledný pridaný prvok)

Jedným z problémov .pop() je, že ak sa pokúsime odobrať prvok z prázdneho zoznamu, Python vyvolá chybu IndexError. Preto je dobré skontrolovať, či nie je zásobník pred odobratím prázdny (napríklad pomocou funkcie len). V Pythone dokonca môžeme spraviť niečo takéto:

if zasobnik:
    # Zásobník má aspoň jeden prvok

if not zasobnik:
    # Zásobník nemá už žiadny prvok

Nahliadnutie na vrchný prvok (operácia "peek")

Ak chceme len zistiť, aký prvok je na vrchole zásobníka bez toho, aby sme ho odstránili, jednoducho pristúpime k poslednému prvku zoznamu. V Pythone to dosiahneme pomocou indexu -1.

vrchny = zasobnik[-1]

Pred prístupom k indexu -1 je však dobré vždy skontrolovať, či zoznam (zásobník) nie je prázdny. Ak by bol prázdny a pokúsili by ste sa o prístup pomocou -1, opäť by to viedlo k chybe IndexError.