Úvod
datové struktury organizují úložiště v počítačích, abychom mohli efektivně přistupovat a měnit data. Stohy a fronty jsou některé z prvních datových struktur definovaných v informatice.
jednoduché se naučit a snadno implementovat, jejich použití jsou běžné a budete s největší pravděpodobností ocitnete jejich začlenění do softwaru pro různé úkoly.
je běžné, že zásobníky a fronty mají být implementovány s polem nebo propojeným seznamem. Budeme se spoléhat na datovou strukturu List, abychom vyhověli jak zásobníkům, tak frontám.
jak fungují?
zásobník
zásobníky, jak název napovídá, se řídí principem Last-in-First-Out (LIFO). Jako by stohování mincí jeden na druhého, poslední mince, kterou jsme položili na vrchol, je ta, která je první, která bude později odstraněna ze zásobníku.
K provedení zásobníku, proto potřebujeme dvě jednoduché operace:
-
push– přidá prvek na vrchol zásobníku:
-
pop– odstraní prvek na vrcholu zásobníku:
Queue
Fronty, stejně jako název napovídá, postupujte First-in-First-Out (FIFO) principu. Jako by čekal ve frontě na lístky do kina, první stát v řadě je první, kdo koupit lístek a užijte si film.
zavést fronty, proto potřebujeme dvě jednoduché operace:
-
enqueue– přidá prvek na konec fronty:
-
dequeue– odstraní prvek na začátku fronty:
Komíny a Fronty pomocí Seznamů
Python je postaven-v List datová struktura je dodáván s metodami simulovat oba zásobníku a fronty operací.
uvažujme hromadu písmen:
můžeme použít stejné funkce k implementaci fronty. Funkce pop volitelně bere index položky, kterou chceme načíst, jako argument.
Takže můžeme použít pop s první index seznamu, tj. 0, aby se fronty-jako chování.
Zvážit „fronty“ ovoce:
Opět zde můžeme použít appendpop operace ze seznamu simulovat základní operace z fronty.
Komíny a Fronty s Deque Knihovna
Python deque (vyslovuje se „balíčku“) je knihovna, která poskytuje posloupnosti s efektivní metody práce jako zásobník nebo fronta.
deque je zkratka pro Double Ended Queue – generalizované frontě, že můžete získat první nebo poslední prvek, který je uložen:
Pokud byste se chtěli dozvědět více o deque knihovny a jiné typy sbírek Python nabízí, můžete si přečíst náš Úvod do Pythonu Sbírek Modul čl.
Přísnější Implementace v Pythonu
Pokud je váš kód potřebný zásobníku a poskytují List, tam je nic zastavit programátor z povolání insertremove nebo další seznam funkcí, které budou mít vliv na pořadí svůj stack! To zásadně ničí bod definování zásobníku, protože již nefunguje tak, jak by měl.
jsou chvíle, kdy bychom chtěli zajistit, aby s našimi daty bylo možné provádět pouze platné operace.
můžeme vytvořit třídy, které odhalí pouze potřebné metody pro každou datovou strukturu.
takže, pojďme vytvořit nový soubor s názvem stack_queue.py a definují dvě třídy:
programátoři pomocí našeho StackQueue jsou nyní vedeni k používání metody za předpokladu, manipulovat data místo.
příklady
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žňuje uživatelům ustoupit své akce až do začátku relace.
zásobník je pro tento scénář ideální. Můžeme zaznamenat každou akci, kterou uživatel provede tím, že ji zatlačíme do zásobníku. Když chce uživatel vrátit zpět akci, vyskočí ji ze zásobníku. Tuto funkci můžeme rychle simulovat:
fronty mají také široké využití v programování. Přemýšlejte o hrách 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.
nyní si představte, že jste vývojář pracující na nové bojové hře. Ve vaší hře, při každém stisknutí tlačítka, je vypálena vstupní událost. Tester si všiml, že pokud jsou tlačítka stisknuta příliš rychle, Hra zpracovává pouze první a speciální pohyby nebudou fungovat!
můžete to opravit pomocí fronty. Můžeme se zeptat na všechny vstupní události, jakmile přijdou. Tímto způsobem nezáleží na tom, zda vstupní události přicházejí s malým časem mezi nimi, budou všechny uloženy a jsou k dispozici pro zpracování. Když zpracováváme pohyby, můžeme je dequeue. Speciální tah může být zpracován takto:
závěr
zásobníky a fronty jsou jednoduché datové struktury, které nám umožňují ukládat a načítat data postupně. V zásobníku je poslední položka, kterou zadáme, první, která vyjde. Ve frontě je první položka, kterou zadáme, první, která vyjde.
můžeme přidat položky do zásobníku pomocí operace push a načíst položky pomocí operace pop. U front přidáme položky pomocí operace enqueue a načteme položky pomocí operace dequeue.
v Pythonu můžeme implementovat stohy a fronty pouze 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 vytvořili naše třídy zásobníku a fronty pro přísnější kontrolu našich dat.
existuje mnoho případů použití v reálném světě pro stohy a fronty, jejich pochopení nám umožňuje snadno a efektivně vyřešit mnoho problémů s ukládáním dat.