Zásobník

Zásobník je lineární datová struktura, která se řídí principem LIFO (Last In First Out).
- To znamená, že poslední prvek vložený do zásobníku je odstraněn jako první.
Datovou strukturu zásobníku si můžeme představit jako hromadu talířů na sobě.
- S touto hromadou talířů můžeme:
  - Položit nový talíř na vrchol hromádky,
  - oddělat horní talíř.
- A pokud chceme vzít talíř úplně vespod, musíme nejprve oddělat všechny talíře nad ním. A přesně takto funguje datová struktura zásobník.

V programování se uložení položky na vrchol zásobníku nazývá push a odebrání položky z vrcholu zásobníku se nazývá pop.

Základní operace zásobníku

Push: Přidání prvku na vrchol zásobníku.
Pop: Odebrání prvku z vrcholu zásobníku.
IsEmpty: Zjistí, zda je zásobník prázdný.
IsFull: Zjistí, zda je zásobník plný.
Peek: Zjistí hodnotu horního prvku bez jeho odstranění.

Implementace zásobníku

Zásobník můžeme reprezentovat pomocí jednosměrně zřetězeného seznamu. Každý prvek seznamu bude obsahovat hodnotu a ukazatel na následující prvek. Začátek seznamu bude ukazovat na poslední vložený prvek.

Struktura pro prvek zásobníku a inicializace zásobníku

Pro jednoduchost (abychom nemuseli funkcím posílat ukazatel na StackNode) si definujeme ukazatel na vrchol zásobníku (stackTop) jako globální proměnnou.

Funkce push

Parametry funkce push:

Hodnota, kterou chceme vložit (typu int).

Funkce vytvoří novou dynamickou proměnnou (strukturu) typu StackNode.

V této struktuře uloží do celočíselné proměnné data vkládanou hodnotu,
do ukazatele next uloží ukazatel na původně první prvek.

stackTop bude ukazovat na tento nově vytvořený prvek.

Funkce isEmpty

Pokud je zásobník prázdný, tak vrací true, jinak vrací false.

Funkce pop

Pokud zásobník není prázdný, tak

vytvoří se pomocná dynamická proměnná (struktura) typu StackNode,
ukazatel stackTop bude nyní ukazovat na druhý prvek,
zlikviduje se pomocná dynamická proměnná.

Funkce peek

Pokud zásobník není prázdný, tak

funkce vrátí hodnotu prvku na vrcholu.

Jinak

vrátí -1 (značí prázdný zásobník).

Funkce deleteStack

Dokud zásobník není prázdný, tak "vypopuj" všechny prvky.

Page updated

Report abuse