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