Table of Contents
Jak implementovat zásobník v C
Zásobníky jsou jedním z nejdůležitějších datových struktur v informatice. Jsou to abstraktní datové typy (ADT) s omezenou funkčností, které fungují podle principu „poslední dovnitř, první ven“ (LIFO). To znamená, že poslední prvek, který byl přidán do zásobníku, je první, který může být odebrán.
V tomto článku se podíváme na to, jak implementovat zásobník v jazyce C. Projdeme si základní principy zásobníku, představíme si různé způsoby jeho implementace a ukážeme si konkrétní příklady kódu.
Co je to zásobník?
Zásobník je strukturovaná sbírka položek, ve které se můžeme pohybovat pouze na jednom konci – vrcholu. Operace, které provádíme se zásobníkem, se nazývají:
* Push: Přidání nového prvku na vrchol zásobníku.
* Pop: Odebrání prvku z vrcholu zásobníku.
* Peek: Získání přístupu k prvku na vrcholu zásobníku, aniž bychom jej odebrali.
* isEmpty: Zjištění, zda je zásobník prázdný.
* isFull: Zjištění, zda je zásobník plný.
Implementace zásobníku v C
Existuje několik způsobů, jak implementovat zásobník v C. Ty nejčastější zahrnují:
* Pomocí polí:
* Pole je statická struktura s pevně stanovenou velikostí, která umožňuje bezproblémové ukládání dat za sebou.
* Implementuje zásobník pomocí pole je jednoduché, avšak omezuje nás na fixní velikost zásobníku.
* Pomocí propojených seznamů:
* Propojené seznamy jsou dynamické struktury, které umožňují měnit velikost zásobníku za běhu.
* Implementuje zásobník pomocí propojených seznamů je flexibilnější, ale může být složitější.
Implementace zásobníku s polem
1. Definice struktury:
c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int items[MAX_SIZE];
int top;
};
* Vytvoříme strukturu Stack s polem items o velikosti MAX_SIZE a proměnnou top, která sleduje pozici vrcholu zásobníku.
2. Funkce push:
c
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 zkontroluje, zda je zásobník plný.
* Pokud není, zvětší se index top a na tuto pozici se uloží nová hodnota value.
3. Funkce pop:
c
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 zkontroluje, zda je zásobník prázdný.
* Pokud není, vrátí hodnotu prvku na vrcholu a sníží index top.
4. Funkce peek:
c
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 vrátí hodnotu prvku na vrcholu zásobníku, aniž by jej odebrala.
5. Funkce isEmpty:
c
int isEmpty(struct Stack *stack) {
return stack->top == -1;
}
* Funkce isEmpty vrátí hodnotu 1, pokud je zásobník prázdný, a 0 jinak.
6. Funkce isFull:
c
int isFull(struct Stack *stack) {
return stack->top == MAX_SIZE - 1;
}
* Funkce isFull vrátí hodnotu 1, pokud je zásobník plný, a 0 jinak.
Implementace zásobníku s propojeným seznamem
1. Definice struktury uzlu:
c
struct Node {
int data;
struct Node *next;
};
* Vytvoříme strukturu Node s polem data pro uložení hodnoty a ukazatelem next pro propojení s dalším uzlem.
2. Definice struktury zásobníku:
c
struct Stack {
struct Node *top;
};
* Vytvoříme strukturu Stack s ukazatelem top na vrchol zásobníku.
3. Funkce push:
c
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 paměť pro nový uzel a nastaví jeho hodnotu na value.
* Ukazatel next nového uzlu se nastaví na aktuální vrchol zásobníku a vrchol zásobníku se nastaví na nový uzel.
4. Funkce pop:
c
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 zkontroluje, zda je zásobník prázdný.
* Pokud není, uloží se ukazatel na vrchol do proměnné temp, odečte se hodnota z uzlu a vrchol se posune na další uzel. Nakonec se uzel temp uvolní z paměti.
5. Funkce peek:
c
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 vrátí hodnotu prvku na vrcholu zásobníku, aniž by jej odebrala.
6. Funkce isEmpty:
c
int isEmpty(struct Stack *stack) {
return stack->top == NULL;
}
* Funkce isEmpty vrátí hodnotu 1, pokud je zásobník prázdný, a 0 jinak.
7. Funkce isFull:
* Funkce isFull není nutná, jelikož u zásobníku s propojeným seznamem není žádný omezující faktor, který by bránil v přidávání dalších prvků.
Příklad použití zásobníku
c
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 se vytvoří zásobník, přidají se do něj tři položky, vytiskne se hodnota na vrcholu, odebere se jedna položka, vytiskne se hodnota na vrcholu a nakonec se zásobník uvolní z paměti.
Závěr
Zásobníky jsou mocným nástrojem v informatice. Existuje několik způsobů, jak je implementovat, a jejich použití se nachází v mnoha algoritmech a datových strukturách. Pochopení principů implementace zásobníku v C je klíčovým krokem pro budování efektivního softwaru.
V tomto článku jsme si představili dvě běžné implementace zásobníku v C – pomocí pole a pomocí propojených seznamů. Prošli jsme si základní operace, které můžeme se zásobníkem provádět, a prověřili jsme si jejich použití v jednoduchém příkladu.
Doufáme, že tento článek vám pomohl získat hlubší pochopení zásobníku a jeho implementace v C.
Časté dotazy
1. K čemu se používá zásobník?
* Zásobníky se používají v mnoha algoritmech a datových strukturách, včetně rekurze, backtrackingu, vyhodnocování výrazu, správy paměti a implementace undo/redo funkcí.
2. Jaký je rozdíl mezi zásobníkem a frontou?
* Zásobník je struktura „poslední dovnitř, první ven“, zatímco fronta je struktura „první dovnitř, první ven“.
3. Jaký je rozdíl mezi statickou a dynamickou implementací zásobníku?
* Statická implementace zásobníku používá pole s pevně stanovenou velikostí, zatímco dynamická implementace používá propojené seznamy, které umožňují měnit velikost zásobníku za běhu.
4. Jaká je složitost operací push, pop a peek v zásobníku?
* Všeobecně platí, že tyto operace mají v průměru časovou složitost O(1) pro obě implementace (pole a propojené seznamy).
5. Jaká je výhoda použití pole při implementaci zásobníku?
* Pole je jednodušší na implementaci a rychlejší pro přístup k prvkům, než dynamické implementace s propojeným seznamem.
6. Jaká je nevýhoda použití pole při implementaci zásobníku?
* Pole má fixní velikost, takže pokud se do něj snažíme umístit více prvků, než se do něj vejde, může dojít k přetečení paměti.
7. Jaká je výhoda použití propojeného seznamu při implementaci zásobníku?
* Propojený seznam umožňuje dynamicky měnit velikost zásobníku a umožňuje tak ukládat více dat, než by se vešlo do statického pole.
8. Jaká je nevýhoda použití propojeného seznamu při implementaci zásobníku?
* Propojený seznam je složitější na implementaci, vyžaduje dynamické alokování paměti a může být méně efektivní pro přístup k prvkům než pole.
9. Jak se zbavit paměťových úniků při implementaci zásobníku s propojeným seznamem?
* Je důležité uvolnit paměť alokovanou pro uzly, které jsou odstraněny ze zásobníku, pomocí funkce free().
10. Kde se používá zásobník v reálném světě?
* Zásobníky se používají například v webových prohlížečích pro správu historie stránek, v textových editorech pro implementaci undo/redo funkcí, v kompilátorech pro vyhodnocování výrazu a v operačních systémech pro správu paměti.