Zásobník

Zásobník je základní abstraktní datový typ, který nám umožňuje vkládat prvky a vybírat poslední vložené prvky. Tomuto principu se říká LIFO - last in, fist out. Fungování fronty je velice intuitivn a chová stejně jako fronta, se kterou se setkáváme v každodenním životě (v obchodě u pokladny).

V literatuře se zaměňují pojmy stack a push-down store a rozdíl je v tom, že stack (využívaný např. jako programový zásobník) umožňuje adresovat prvky a přistupovat k nim. Tyto adresy jsou relativní vzhledem k vrcholu zásobníku. Naproti tomu push-down store umožňuje přistupovat pouze k vrcholu struktury. Tato struktura se využívá například u zásobníkových automatů.

Operace

Signatura operací zásobníku.

Operace Argumenty Popis Složitost
init vrací nově vytvořený prázdný zásobník. O(1)
push Stack s, Elem x vložení nového elementu (na vrchol zásobníku) O(1)
pop Stack s odebrání elementu z vrcholu zásobníku O(1)
top Stack s hodnota na vrcholu zásobníku O(1)
is_empty Stack s predikát, jehož výsledkem je true, jestliže je zásobník prázdný, jinak false O(1)

Pokud je zásobník dobře implementován, pak každá operace s ním má konstantní složitost.

Axiomy

  • is_empty(init) = true
  • is_empty(push (s, x)) = false
  • top(init) = error: stack underflow
  • top(push (s, x)) = x
  • pop(init) = init
  • pop(push(s, x)) = s

Chybové stavy

Pokud provedeme operaci pop na prázdném zásobníku nastává podtečení (stack underflow). Pokud není možné přidat další prvek, nastává přetečení (stack overflow).

Implementace

Pomocí pole

Zásobník umožňuje evidovat jediný index, který ukazuje na první volné místo, poslední vložený a tedy první vybíraný má index o jedničku menší, počet prvků v zásobníku je roven tomuto indexu. Všechny operace jsou tedy konstantní. Vše, co platilo o natahování pole v případě reprezentace množiny, platí i pro zásobník.

Pomocí spojového listu

LIFO strategie umožňuje pracovat pouze s čelem fronty a přestože operace v této implementaci mají vyšší režii než v případě implementace pomocí pole, složitost je stále konstantní.


C++

https://en.cppreference.com/w/cpp/container/stack

#include <stack>
template <class T, class Container = deque<T> > class stack;
Haskell

https://hackage.haskell.org/package/Stack-0.4.0/docs/Data-Stack.html

Související