Zásobníky představují klíčovou datovou strukturu v informatice. Jedná se o abstraktní datový typ (ADT) s omezenými možnostmi, který se řídí principem LIFO (Last In, First Out), tedy „poslední dovnitř, první ven“. To znamená, že naposledy vložený prvek je první, který je možné z tohoto zásobníku odebrat.
V tomto textu se budeme věnovat procesu implementace zásobníku v programovacím jazyce C. Seznámíme se s hlavními zásadami, prozkoumáme různé metody jeho implementování a demonstrujeme si to na konkrétních příkladech.
Co je vlastně zásobník?
Zásobník je strukturovaná kolekce datových položek, s nimiž se manipuluje pouze na jednom konci, jenž je nazýván vrcholem. Operace, které se se zásobníkem provádějí, jsou:
- Vložení (Push): Vložení nového prvku na vrchol zásobníku.
- Odebrání (Pop): Odstranění prvku z vrcholu zásobníku.
- Náhled (Peek): Získání hodnoty prvku na vrcholu, aniž by byl prvek odstraněn.
- Test prázdnoty (isEmpty): Zjištění, zda je zásobník prázdný.
- Test plnosti (isFull): Zjištění, zda je zásobník plný.
Jak implementovat zásobník v C
Zásobník můžeme v jazyce C implementovat několika různými způsoby. Mezi nejčastější metody patří:
- S využitím pole:
- Pole je statická datová struktura s pevně definovanou velikostí, která nám umožňuje efektivně ukládat data sekvenčně za sebou.
- Implementace zásobníku za pomoci pole je poměrně jednoduchá, avšak omezuje nás fixní kapacitou zásobníku.
- S využitím zřetězených seznamů:
- Zřetězené seznamy jsou dynamické datové struktury, které nám umožňují měnit velikost zásobníku za běhu programu.
- Implementace zásobníku za pomoci zřetězených seznamů je flexibilnější, avšak může být komplexnější.
Implementace zásobníku s polem
1. Definice struktury:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int items[MAX_SIZE];
int top;
};
Vytvoříme strukturu Stack, která obsahuje pole items o dané maximální velikosti MAX_SIZE a celočíselnou proměnnou top, jež uchovává aktuální pozici vrcholu zásobníku.
2. Funkce pro vkládání (push):
void push(struct Stack *stack, int value) {
if (stack->top == MAX_SIZE - 1) {
printf("Zásobník je plný!\n");
return;
}
stack->top++;
stack->items[stack->top] = value;
}
Funkce push nejdříve ověří, zda je zásobník plný. Pokud ne, inkrementuje index top a na nově získanou pozici vloží novou hodnotu value.
3. Funkce pro odebírání (pop):
int pop(struct Stack *stack) {
if (stack->top == -1) {
printf("Zásobník je prázdný!\n");
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}
Funkce pop ověří, zda zásobník není prázdný. V případě, že prázdný není, vrátí hodnotu prvku nacházejícího se na vrcholu a poté sníží index top.
4. Funkce pro náhled (peek):
int peek(struct Stack *stack) {
if (stack->top == -1) {
printf("Zásobník je prázdný!\n");
return -1;
}
return stack->items[stack->top];
}
Funkce peek vrací hodnotu prvku, který se nachází na vrcholu zásobníku, aniž by tento prvek z něj odebrala.
5. Funkce pro test prázdnoty (isEmpty):
int isEmpty(struct Stack *stack) {
return stack->top == -1;
}
Funkce isEmpty vrátí hodnotu 1, pokud je zásobník prázdný, jinak vrací 0.
6. Funkce pro test plnosti (isFull):
int isFull(struct Stack *stack) {
return stack->top == MAX_SIZE - 1;
}
Funkce isFull vrací hodnotu 1, pokud je zásobník plný, jinak vrací 0.
Implementace zásobníku s propojeným seznamem
1. Definice struktury uzlu:
struct Node {
int data;
struct Node *next;
};
Vytvoříme strukturu Node, která má datové pole data pro uchovávání dat a ukazatel next pro odkazování na další uzel v seznamu.
2. Definice struktury zásobníku:
struct Stack {
struct Node *top;
};
Vytvoříme strukturu Stack s ukazatelem top odkazujícím na vrchol zásobníku.
3. Funkce pro vkládání (push):
void push(struct Stack *stack, int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = stack->top;
stack->top = newNode;
}
Funkce push alokuje dynamicky paměť pro nový uzel, jehož hodnotu nastaví na value. Ukazatel next nového uzlu se nastaví na aktuální vrchol zásobníku a poté se vrchol zásobníku přesune na nově vytvořený uzel.
4. Funkce pro odebírání (pop):
int pop(struct Stack *stack) {
if (stack->top == NULL) {
printf("Zásobník je prázdný!\n");
return -1;
}
struct Node *temp = stack->top;
int value = temp->data;
stack->top = stack->top->next;
free(temp);
return value;
}
Funkce pop ověří, zda je zásobník prázdný. Pokud ne, uloží ukazatel na vrchol do pomocné proměnné temp, načte hodnotu z aktuálního uzlu, posune vrchol zásobníku na další uzel a poté uvolní paměť původního uzlu z paměti.
5. Funkce pro náhled (peek):
int peek(struct Stack *stack) {
if (stack->top == NULL) {
printf("Zásobník je prázdný!\n");
return -1;
}
return stack->top->data;
}
Funkce peek vrací hodnotu prvku, který se nachází na vrcholu zásobníku, aniž by tento prvek z něj odebrala.
6. Funkce pro test prázdnoty (isEmpty):
int isEmpty(struct Stack *stack) {
return stack->top == NULL;
}
Funkce isEmpty vrací hodnotu 1, pokud je zásobník prázdný, jinak vrací 0.
7. Funkce pro test plnosti (isFull):
U zásobníků implementovaných pomocí zřetězeného seznamu není potřeba funkce isFull, neboť teoreticky můžeme přidávat prvky do zásobníku dokud nedojde volná paměť v počítači.
Příklad použití zásobníku
int main() {
struct Stack *stack = malloc(sizeof(struct Stack));
stack->top = NULL; // Inicializace prázdného zásobníku
push(stack, 10);
push(stack, 20);
push(stack, 30);
printf("Hodnota na vrcholu zásobníku: %d\n", peek(stack));
printf("Odebraná hodnota: %d\n", pop(stack));
printf("Hodnota na vrcholu zásobníku: %d\n", peek(stack));
free(stack);
return 0;
}
V tomto příkladu vytvoříme zásobník, vložíme do něj tři hodnoty, vypíšeme hodnotu na vrcholu, odebereme jednu hodnotu, vypíšeme znovu hodnotu na vrcholu a nakonec uvolníme zásobník z paměti.
Závěrem
Zásobníky jsou užitečné nástroje v oblasti informatiky. Existuje několik způsobů jejich implementace a nacházejí uplatnění v mnoha algoritmech a datových strukturách. Porozumění principům implementace zásobníku v jazyce C je zásadním krokem k vytváření kvalitního softwaru.
V tomto článku jsme se seznámili se dvěma obvyklými implementacemi zásobníku v jazyce C – pomocí pole a pomocí zřetězených seznamů. Prošli jsme si základní operace, které můžeme se zásobníkem provádět, a ukázali jsme si jejich využití v jednoduchém příkladu.
Doufáme, že vám tento článek pomohl lépe pochopit zásobník a jeho implementaci v jazyce C.
Často kladené otázky
1. Kde se zásobník používá?
Zásobníky se používají v mnoha algoritmech a datových strukturách, například při rekurzi, backtrackingu, vyhodnocování matematických výrazů, správě paměti nebo implementaci funkcí undo/redo.
2. Jaký je rozdíl mezi zásobníkem a frontou?
Zásobník se řídí principem „poslední dovnitř, první ven“ (LIFO), zatímco fronta pracuje na principu „první dovnitř, první ven“ (FIFO).
3. Jaký je rozdíl mezi statickou a dynamickou implementací zásobníku?
Statická implementace zásobníku využívá pole s pevně danou velikostí, zatímco dynamická implementace využívá zřetězené seznamy, které umožňují měnit velikost zásobníku za běhu.
4. Jaká je časová složitost operací push, pop a peek v zásobníku?
Obecně tyto operace mají časovou složitost O(1) pro obě implementace (pole i zřetězené seznamy).
5. Jaké jsou výhody použití pole pro implementaci zásobníku?
Implementace pomocí pole je snadnější a rychlejší při přístupu k prvkům, než dynamická implementace s zřetězeným seznamem.
6. Jaké jsou nevýhody použití pole pro implementaci zásobníku?
Pole má fixní velikost, a tudíž pokud se do něj snažíme uložit více prvků, než se vejde, může dojít k přetečení paměti.
7. Jaké jsou výhody použití zřetězeného seznamu pro implementaci zásobníku?
Zřetězený seznam nám umožňuje dynamicky měnit velikost zásobníku a ukládat více dat, než by bylo možné do statického pole.
8. Jaké jsou nevýhody použití zřetězeného seznamu pro implementaci zásobníku?
Zřetězený seznam je složitější implementovat, vyžaduje dynamickou alokaci paměti a může být méně efektivní pro přístup k prvkům, než je tomu u polí.
9. Jak se vyhnout únikům paměti při implementaci zásobníku s využitím zřetězených seznamů?
Je důležité uvolnit paměť, která byla alokována pro uzly, jež jsou ze zásobníku odstraněny, a to s použitím funkce free().
10. Kde se v reálném světě zásobníky využívají?
Zásobníky se používají například ve webových prohlížečích pro správu historie navštívených stránek, v textových editorech pro implementaci funkcí undo/redo, v kompilátorech pro vyhodnocování výrazů a v operačních systémech pro správu paměti.