Úvod

Datové struktury organizují úložiště v počítačích tak, abychom mohli efektivně přistupovat k datům a měnit je. Zásobníky a fronty jsou jedny z prvních datových struktur definovaných v informatice.

Jsou jednoduché na naučení a snadno se implementují, jejich použití je běžné a nejspíš se setkáte s jejich začleněním do svého softwaru pro různé úlohy.

Obvykle se zásobníky a fronty implementují pomocí pole nebo propojeného seznamu. Budeme se spoléhat na datovou strukturu List, která pojme jak zásobníky, tak fronty.

Jak fungují?

Zásobník

Zásobníky, jak název napovídá, se řídí principem LIFO (Last-in-First-Out). Jako bychom pokládali mince na sebe, poslední mince, kterou položíme na vrchol, je ta, která bude později z hromádky odstraněna jako první.

K realizaci zásobníku tedy potřebujeme dvě jednoduché operace:

• push – přidá prvek na vrchol zásobníku:

• pop – odebere prvek na vrcholu zásobníku:

Queue

Queue, jak už název napovídá, se řídí principem FIFO (First-in-First-Out). Jako když čekáte ve frontě na lístky do kina, kdo první stojí ve frontě, ten si jako první koupí lístek a užije si film.

K realizaci fronty tedy potřebujeme dvě jednoduché operace:

• enqueue – přidá prvek na konec fronty:

• dequeue – odstraní prvek na začátku fronty:

Zásobníky a fronty pomocí seznamů

Vestavěná datová struktura List jazyka Python je vybavena metodami pro simulaci operací se zásobníky i frontami.

Uvažujme o zásobníku písmen:

Stejné funkce můžeme použít k implementaci fronty. Funkce pop volitelně přebírá jako argument index položky, kterou chceme získat.

Můžeme tedy použít pop s prvním indexem seznamu, tj. 0, abychom získali chování podobné frontě.

Přemýšlejme o „frontě“ ovoce:

Znovu zde použijeme operace append a pop seznamu, abychom simulovali základní operace fronty.

Sklady a fronty s knihovnou Deque

Python má knihovnu deque (vyslovuje se „deck“), která poskytuje posloupnost s efektivními metodami pro práci jako zásobník nebo fronta.

deque je zkratka pro Double Ended Queue – zobecněnou frontu, která může získat první nebo poslední uložený prvek:

Pokud se chcete dozvědět více o knihovně deque a dalších typech kolekcí, které Python poskytuje, můžete si přečíst náš článek Úvod do modulu kolekcí Pythonu.

Implementace zásobníku v Pythonu

Pokud váš kód potřeboval zásobník a vy mu poskytnete List, nic nebrání programátorovi volat insert, remove nebo jiné funkce seznamu, které ovlivní pořadí zásobníku! To zásadně ničí smysl definování zásobníku, protože už nefunguje tak, jak by měl.

Někdy bychom rádi zajistili, aby se s našimi daty prováděly pouze platné operace.

Můžeme vytvořit třídy, které pro každou datovou strukturu vystaví pouze potřebné metody.

Za tímto účelem vytvoříme nový soubor s názvem stack_queue.py a definujeme dvě třídy:

Programátoři, kteří používají naše třídy Stack a Queue, jsou nyní vyzváni, aby k manipulaci s daty používali raději poskytnuté metody.

Příklad

Představte si, že jste vývojář pracující na zcela novém textovém procesoru. Máte za úkol vytvořit funkci undo – umožňující uživatelům vrátit se zpět ke svým akcím až na začátek relace.

Pro tento scénář se ideálně hodí zásobník. Každou akci, kterou uživatel provede, můžeme zaznamenat tím, že ji přesuneme do zásobníku. Když chce uživatel nějakou akci vrátit zpět, vysune ji ze zásobníku. Tuto funkci můžeme rychle simulovat takto:

Kufry mají široké využití i v programování. Vzpomeňte si na hry jako Street Fighter nebo Super Smash Brothers. Hráči v těchto hrách mohou provádět speciální pohyby stisknutím kombinace tlačítek. Tyto kombinace tlačítek lze uložit do fronty.

Teď si představte, že jste vývojář pracující na nové bojové hře. Ve vaší hře se při každém stisknutí tlačítka spustí vstupní událost. Jeden z testerů si všiml, že pokud jsou tlačítka stisknuta příliš rychle, hra zpracuje pouze první z nich a speciální pohyby nebudou fungovat!“

To můžete vyřešit pomocí fronty. Můžeme zařadit do fronty všechny vstupní události tak, jak přicházejí. Tímto způsobem nezáleží na tom, že vstupní události přicházejí s malým časovým odstupem, všechny budou uloženy a k dispozici pro zpracování. Až budeme pohyby zpracovávat, můžeme je z fronty vyřadit. Speciální tah lze zpracovat takto:

Závěr

Sklady a fronty jsou jednoduché datové struktury, které nám umožňují ukládat a načítat data postupně. V zásobníku platí, že poslední položka, kterou do něj vložíme, je první, která z něj vyjde. Ve frontě je první položka, kterou zadáme, první, která vyjde.

Položky můžeme do zásobníku přidávat pomocí operace push a položky můžeme načítat pomocí operace pop. U fronty přidáváme položky pomocí operace enqueue a získáváme položky pomocí operace dequeue.

V jazyce Python můžeme implementovat zásobníky a fronty jen pomocí vestavěné datové struktury List. Python má také knihovnu deque, která může efektivně poskytovat operace zásobníku a fronty v jednom objektu. Nakonec jsme si vytvořili třídy zásobníků a front pro přísnější kontrolu nad našimi daty.

Pro zásobníky a fronty existuje mnoho reálných případů použití, jejich pochopení nám umožňuje snadno a efektivně řešit mnoho problémů s ukládáním dat.

Příklady použití zásobníků a front v reálném světě jsou velmi široké.