Zhrnutie na Zásobník (stack)

Zásobník (Stack): Princíp LIFO, operácie, využitie a príklady

Zhrnutie Test znalostí Kartičky Podcast Myšlienková mapa

Zásobník (Stack): Princíp LIFO

Ahoj! Dnes sa pozrieme na jednu zo základných a najčastejšie používaných dátových štruktúr v informatike – zásobník, anglicky stack. Predstav si ho ako hromadu tanierov, ktorú máš v kuchyni. Keď umyješ nový tanier, položíš ho na vrch hromady. Keď potrebuješ čistý tanier, vezmeš si ten, ktorý je navrchu. Nikdy neberieš tanier zo stredu alebo spodku a ani tam žiadny nový nepridávaš. Toto jednoduché pravidlo je kľúčové pre pochopenie zásobníka a volá sa LIFO.

LIFO (Last In, First Out): Princíp, podľa ktorého posledný pridaný prvok do zásobníka je prvý, ktorý bude zo zásobníka odobratý. Je to ako prístup k veciam v zásobníku streliva alebo k balíčku kariet, kde vždy berieš tú vrchnú.

Základné operácie zásobníka

Zásobník nie je len o skladovaní dát, ale aj o tom, ako s nimi interagujeme. Existuje päť základných operácií, ktoré každý zásobník musí podporovať. Sú to akoby pravidlá hry, ktoré určujú, ako sa s tanierovou hromadou môže manipulovať.

Push (vloženie): Táto operácia slúži na pridanie nového prvku na vrchol zásobníka. Je to ako keď pridáš nový tanier na hromadu. Ak by hromada tanierov mala pevne danú maximálnu výšku (čo v programovaní znamená pevnú kapacitu), a ty by si sa pokúsil pridať ďalší tanier, keď je už plná, nastala by chyba nazývaná pretečenie (overflow).
Pop (odobratie): Pomocou tejto operácie odoberieme a zároveň získame prvok, ktorý je aktuálne na vrchole zásobníka. Jednoducho si vezmeš vrchný tanier. Ak by si sa pokúsil odobrať tanier z prázdnej hromady, nastala by chyba nazývaná podtečenie (underflow).
Top (nahliadnutie): Táto operácia ti umožní pozrieť sa na prvok, ktorý je na vrchole zásobníka, ale bez toho, aby si ho odstránil. Je to ako keď sa pozrieš, aký tanier je navrchu, ale nevezmeš si ho. To je užitočné, keď potrebuješ vedieť, čo tam je, ale nechceš to hneď odstrániť.
IsEmpty (kontrola prázdnoty): Táto operácia nám povie, či je zásobník prázdny alebo obsahuje nejaké prvky. Vráti buď true (pravda), ak je prázdny, alebo false (nepravda), ak obsahuje aspoň jeden prvok.
Size (veľkosť): Táto operácia vráti aktuálny počet prvkov, ktoré sa nachádzajú v zásobníku. Povie ti, koľko tanierov je aktuálne na hromade.

💡 Vedeli ste?Did you know that LIFO princíp sa nepoužíva len v informatike? Nájdete ho napríklad v reálnom živote pri stohovaní novín, kde vždy čítate najnovšie správy z vrchu, alebo pri zásobníkoch streliva, kde posledná vložená nábojka je vystrelená ako prvá.

Implementácia zásobníka pomocou poľa

Zásobník je abstraktná dátová štruktúra, čo znamená, že si môžeme vybrať, ako ju chceme implementovať. Jedným z najčastejších a najjednoduchších spôsobov je použitie poľa. Predstav si pole ako dlhý rad priehradiek, kde do každej môžeš uložiť jeden prvok. Aby sme vedeli, kde je „vrchol“ nášho zásobníka, potrebujeme špeciálnu premennú, ktorú budeme volať napríklad vrchol alebo topIndex.

Ako to funguje?

Inicializácia: Keď vytvoríme nový, prázdny zásobník, premennú vrchol nastavíme zvyčajne na hodnotu $-1$. To signalizuje, že v zásobníku zatiaľ nič nie je. Ak by sme indexovali pole od $1$, vrchol by mohol byť nastavený na $0$ a ukazovať na prvú voľnú pozíciu.
Operácia Push (pridanie):
1. Najprv skontrolujeme, či zásobník nie je plný (ak máme pole s pevnou veľkosťou). Ak je plný, nemôžeme pridať ďalší prvok (overflow).
2. Ak nie je plný, zvýšime hodnotu vrchol o $1$. Matematicky to môžeme zapísať ako vrchol = vrchol + 1 alebo vrchol++.
3. Na novú pozíciu v poli, ktorú teraz ukazuje vrchol (napríklad pole[vrchol]), uložíme nový prvok.
Príklad: Ak je vrchol = -1 a chceme pridať prvý prvok, vrchol sa stane $0$ a prvok sa uloží do pole[0]. Ak chceme pridať druhý prvok, vrchol sa stane $1$ a prvok sa uloží do pole[1]. A tak ďalej.
Operácia Pop (odobratie):
1. Najprv skontrolujeme, či zásobník nie je prázdny. Ak je prázdn

Zaregistruj sa pre celé zhrnutie

KartičkyTest znalostíZhrnutiePodcastMyšlienková mapa

Začni zadarmo

Už máš účet? Prihlásiť sa

Zásobník (Stack)

Klíčová slova: Zásobník (Stack) v informatike, Využitie zásobníka v programovaní, Zásobníky dátových štruktúr

Klíčové pojmy: Zásobník (Stack) je lineárna dátová štruktúra pracujúca na princípe LIFO., LIFO znamená "Last In, First Out" (posledný dnu, prvý von)., Operácia `Push` pridáva prvok na vrchol zásobníka; môže spôsobiť "overflow"., Operácia `Pop` odoberá a vracia prvok z vrcholu zásobníka; môže spôsobiť "underflow"., Operácia `Top` vráti prvok z vrcholu bez jeho odstránenia., Operácia `IsEmpty` kontroluje, či je zásobník prázdny., Operácia `Size` vracia počet prvkov v zásobníku., Zásobník sa často implementuje pomocou poľa a premennej `vrchol` (alebo `topIndex`)., Pre prázdny zásobník je `vrchol` zvyčajne nastavený na $-1$., Všetky základné operácie zásobníka (`push`, `pop`, `top`, `isEmpty`, `size`) majú konštantnú časovú zložitosť $O(1)$.

## Zásobník (Stack): Princíp LIFO Ahoj! Dnes sa pozrieme na jednu zo základných a najčastejšie používaných dátových štruktúr v informatike – **zásobník**, anglicky **stack**. Predstav si ho ako hromadu tanierov, ktorú máš v kuchyni. Keď umyješ nový tanier, položíš ho na vrch hromady. Keď potrebuješ čistý tanier, vezmeš si ten, ktorý je navrchu. Nikdy neberieš tanier zo stredu alebo spodku a ani tam žiadny nový nepridávaš. Toto jednoduché pravidlo je kľúčové pre pochopenie zásobníka a volá sa **LIFO**. > **LIFO (Last In, First Out)**: Princíp, podľa ktorého posledný pridaný prvok do zásobníka je prvý, ktorý bude zo zásobníka odobratý. Je to ako prístup k veciam v zásobníku streliva alebo k balíčku kariet, kde vždy berieš tú vrchnú. ### Základné operácie zásobníka Zásobník nie je len o skladovaní dát, ale aj o tom, ako s nimi interagujeme. Existuje päť základných operácií, ktoré každý zásobník musí podporovať. Sú to akoby pravidlá hry, ktoré určujú, ako sa s tanierovou hromadou môže manipulovať. 1. **Push (vloženie)**: Táto operácia slúži na pridanie nového prvku na vrchol zásobníka. Je to ako keď pridáš nový tanier na hromadu. Ak by hromada tanierov mala pevne danú maximálnu výšku (čo v programovaní znamená pevnú kapacitu), a ty by si sa pokúsil pridať ďalší tanier, keď je už plná, nastala by chyba nazývaná **pretečenie (overflow)**. 2. **Pop (odobratie)**: Pomocou tejto operácie odoberieme a zároveň získame prvok, ktorý je aktuálne na vrchole zásobníka. Jednoducho si vezmeš vrchný tanier. Ak by si sa pokúsil odobrať tanier z prázdnej hromady, nastala by chyba nazývaná **podtečenie (underflow)**. 3. **Top (nahliadnutie)**: Táto operácia ti umožní pozrieť sa na prvok, ktorý je na vrchole zásobníka, ale bez toho, aby si ho odstránil. Je to ako keď sa pozrieš, aký tanier je navrchu, ale nevezmeš si ho. To je užitočné, keď potrebuješ vedieť, čo tam je, ale nechceš to hneď odstrániť. 4. **IsEmpty (kontrola prázdnoty)**: Táto operácia nám povie, či je zásobník prázdny alebo obsahuje nejaké prvky. Vráti buď `true` (pravda), ak je prázdny, alebo `false` (nepravda), ak obsahuje aspoň jeden prvok. 5. **Size (veľkosť)**: Táto operácia vráti aktuálny počet prvkov, ktoré sa nachádzajú v zásobníku. Povie ti, koľko tanierov je aktuálne na hromade. Did you know that LIFO princíp sa nepoužíva len v informatike? Nájdete ho napríklad v reálnom živote pri stohovaní novín, kde vždy čítate najnovšie správy z vrchu, alebo pri zásobníkoch streliva, kde posledná vložená nábojka je vystrelená ako prvá. ### Implementácia zásobníka pomocou poľa Zásobník je abstraktná dátová štruktúra, čo znamená, že si môžeme vybrať, ako ju chceme implementovať. Jedným z najčastejších a najjednoduchších spôsobov je použitie **poľa**. Predstav si pole ako dlhý rad priehradiek, kde do každej môžeš uložiť jeden prvok. Aby sme vedeli, kde je „vrchol“ nášho zásobníka, potrebujeme špeciálnu premennú, ktorú budeme volať napríklad `vrchol` alebo `topIndex`. #### Ako to funguje? * **Inicializácia**: Keď vytvoríme nový, prázdny zásobník, premennú `vrchol` nastavíme zvyčajne na hodnotu $-1$. To signalizuje, že v zásobníku zatiaľ nič nie je. Ak by sme indexovali pole od $1$, `vrchol` by mohol byť nastavený na $0$ a ukazovať na prvú voľnú pozíciu. * **Operácia Push (pridanie)**: 1. Najprv skontrolujeme, či zásobník nie je plný (ak máme pole s pevnou veľkosťou). Ak je plný, nemôžeme pridať ďalší prvok (overflow). 2. Ak nie je plný, zvýšime hodnotu `vrchol` o $1$. Matematicky to môžeme zapísať ako `vrchol = vrchol + 1` alebo `vrchol++`. 3. Na novú pozíciu v poli, ktorú teraz ukazuje `vrchol` (napríklad `pole[vrchol]`), uložíme nový prvok. *Príklad:* Ak je `vrchol = -1` a chceme pridať prvý prvok, `vrchol` sa stane $0$ a prvok sa uloží do `pole[0]`. Ak chceme pridať druhý prvok, `vrchol` sa stane $1$ a prvok sa uloží do `pole[1]`. A tak ďalej. * **Operácia Pop (odobratie)**: 1. Najprv skontrolujeme, či zásobník nie je prázdny. Ak je prázdn