Zásobník - jedna z klíčových datových struktur používaná v programovacím jazyce C.je součástí paměti počítače a je navržena tak, aby ukládala místní proměnné funkcí a návratných hodnot.
Zásobník je uspořádaný seznam paměti, ve kterém jsou přidány nové položky a odstraněny pouze z jednoho konce - vrcholu zásobníku. Říká se tomu princip LIFO (Last In, First Out), kde poslední přidaná položka je první, která bude odstraněna.
V C má každá funkce svůj vlastní zásobník, který je vytvořen a zničen během běhu. Při volání funkce jsou všechny její místní proměnné, včetně argumentů funkce, umístěny na vrchol zásobníku. Když je funkce dokončena, zásobník obnoví svůj stav a místní proměnné jsou odstraněny, aby se uvolnila paměť.
Zásobník funguje velmi efektivně a poskytuje rychlý přístup k datům, protože k přidání nebo odebrání položek se používá pouze jedno místo. Zásobník má však omezenou kapacitu, která je dána systémem, a překročení tohoto limitu může vést k chybě přetečení zásobníku (stack overflow).
Datová struktura-zásobník
Zásobník funguje na principu "last in, first out" (LIFO), což znamená, že prvky jsou přidány a odstraněny na jedné straně zásobníku zvaného vrchol. Když je přidána nová položka, umístí se na vrchol zásobníku a po odstranění se tato horní položka vyjme.
Mezi hlavní operace prováděné se zásobníkem patří:
| Obchod | Popis |
|---|---|
| push | Přidání položky na vrchol zásobníku |
| pop | Odstranění horního prvku ze zásobníku |
| peek | Získání hodnoty horního prvku bez jeho odstranění |
| isEmpty | Kontrola, zda je zásobník prázdný |
| isFull | Zkontrolujte, zda je zásobník plný (pokud je velikost zásobníku omezená) |
Zásobník je široce používán v mnoha programovacích oblastech, včetně rekurze, zpracování výrazů, obcházení stromů atd. Umožňuje efektivně řídit sekvenci operací a ukládat mezilehlé hodnoty.
Co je zásobník v programování?
Zásobník si lze představit jako hromadu knih nebo talířů, kde je každý nový prvek přidán nahoře a k odstranění dochází pouze z horní části hromádky. Poslední přidaná položka tak bude první, kterou lze odstranit.
Operace dostupné pro práci se zásobníkem:
- Push - přidává nový prvek na horní část zásobníku.
- Pop - odstraní a vrátí prvek z horní části zásobníku.
- Peek - vrátí prvek z horní části zásobníku, aniž by byl odstraněn.
- IsEmpty - zkontroluje, jestli je zásobník prázdný.
- IsFull - zkontroluje, zda je zásobník naplněn (kapacita je omezená).
Zásobník lze implementovat jako pole pevné velikosti nebo dynamický seznam. Je široce používán v různých programovacích oblastech, jako je zpracování rekurze, provádění funkcí, Správa hovorů a návratů z funkcí, zpracování výrazů a další.
Operace se zásobníkem v C
Operace zásobníku v C obvykle zahrnují následující:
| Obchod | Popis |
|---|---|
| push() | Přidá prvek na horní část zásobníku |
| pop() | Odstraní prvek z horní části zásobníku |
| is_empty() | Zkontroluje, zda je zásobník prázdný |
| is_full() | Zkontroluje, zda je zásobník plný |
| peek() | Vrátí hodnotu položky na horní straně zásobníku bez odstranění |
Funkce push () přidává nový prvek na horní část zásobníku. Pokud je zásobník plný, funkce způsobí chybu "zásobník je přeplněný". Funkce pop () odstraní prvek z horní části zásobníku a vrátí jeho hodnotu. Pokud je zásobník prázdný, funkce způsobí chybu "zásobník prázdný".
Funkce is_empty() a is_full () se používají ke kontrole stavu zásobníku. Funkce is_empty () vrátí true, pokud je zásobník prázdný, a false jinak. Funkce is_full () vrátí true, pokud je zásobník plný, a false jinak.
Funkce peek () vrací hodnotu položky na horní straně zásobníku, aniž by byla odstraněna. Tato funkce je užitečná, když chcete zobrazit horní položku zásobníku, ale není nutné ji odstranit.
Příklad použití zásobníku v C
Podívejme se na příklad použití zásobníku v programování v jazyce C.Představme si, že máme za úkol zkontrolovat správnost závorkové sekvence.
Pro tento úkol lze pomocí zásobníku sledovat otevřené závorky. Algoritmus bude následující:
- Projděte každý znak v řádku. Pokud je znak otvírací závorkou (jako ' ('nebo' <'), přidejte jej do zásobníku.
- Pokud je symbol uzavírací závorkou (jako ')' nebo '>'), zkontrolujte, zda odpovídá poslednímu otevřenému symbolu v zásobníku. Pokud ano, odstraňte poslední symbol ze zásobníku. Pokud ne, závorková sekvence není správná.
- Po dokončení průchodu všemi symboly zkontrolujte, zda je zásobník prázdný. Pokud ano, závorková sekvence je správná. Pokud ne, závorková sekvence není správná.
Zde je příklad kódu na C, který implementuje takový algoritmus:
#include #include #include #define MAX_STACK_SIZE 100typedef struct Stack;void initialize(Stack* stack) top = -1;>void push(Stack* stack, char c) top == MAX_STACK_SIZE - 1) stack->top++;stack->items[stack->top] = c;>char pop(Stack* stack) top == -1) char item = stack->items[stack->top];stack->top--;return item;>int is_empty(Stack* stack) top == -1;>int is_valid(char* sequence)