Zásobník (abstraktní datový typ) - Stack (abstract data type)

Podobně jako stoh desek je přidání nebo odebrání možné pouze nahoře.
Jednoduchá reprezentace modulu runtime zásobníku s operacemi push a pop .

Ve vědě o počítačích , je stack je abstraktní datový typ , který slouží jako sbírka prvků, se dvěma hlavními hlavní činnosti:

  • Push , který přidá prvek do kolekce, a
  • Pop , který odstraní naposledy přidaný prvek, který ještě nebyl odstraněn.

Pořadí, ve kterém prvky vycházejí ze zásobníku, dává vzniknout jeho alternativnímu názvu LIFO ( last in, first out ). Navíc nahlédnout operace může poskytnout přístup k vrcholu bez úpravy zásobníku. Název „zásobník“ pro tento typ struktury pochází z analogie k sadě fyzických položek naskládaných na sebe. Tato struktura usnadňuje vyjmutí položky z horní části hromádky, přičemž k tomu, abyste se dostali k položce hlouběji v zásobníku, může být nutné nejprve sundat několik dalších položek.

Považovány za lineární datovou strukturu nebo abstraktněji za sekvenční kolekci, operace push a pop se vyskytují pouze na jednom konci struktury, označovaném jako horní část zásobníku. Tato datová struktura umožňuje implementovat zásobník jako jednotlivě propojený seznam a ukazatel na horní prvek. Zásobník může být implementován tak, aby měl omezenou kapacitu. Pokud je zásobník plný a neobsahuje dostatek místa pro přijetí entity, která má být odeslána, je zásobník považován za ve stavu přetečení . Operace pop odebere položku z horní části zásobníku.

K implementaci hloubkového vyhledávání je potřeba zásobník .

Dějiny

Stacks vstoupil do počítačové vědy v roce 1946, kdy Alan M. Turing použil výrazy „pohřbít“ a „unbury“ jako prostředek k volání a návratu z podprogramů. Podprogramy už byl realizován v Konrad Zuse je Z4 v roce 1945.

Klaus Samelson a Friedrich L. Bauer z Technické univerzity v Mnichově navrhli myšlenku stohu v roce 1955 a podali patent v roce 1957. V březnu 1988, kdy Samelson zemřel, získal Bauer cenu IEEE Computer Pioneer Award za vynález zásobníku. zásada. Podobné koncepty byly vyvinuty nezávisle Charlesem Leonardem Hamblinem v první polovině roku 1954 a Wilhelmem Kämmererem  [ de ] v roce 1958.

Stohy jsou často popisovány pomocí analogie odpruženého stohu talířů v jídelně. Čisté talíře jsou umístěny na vrchol hromádky a tlačí dolů. Když je ze stohu vyjmut talíř, vyskočí talíř pod ním a stane se novou horní deskou.

Neesenciální operace

V mnoha implementacích má zásobník více operací než základní operace „push“ a „pop“. Příkladem nepodstatné operace je „top of stack“ nebo „peek“, který pozoruje horní prvek, aniž by jej odstranil ze zásobníku. Toho lze dosáhnout pomocí „pop“ následovaného „push“ pro vrácení stejných dat do zásobníku, takže to není považováno za zásadní operaci. Pokud je zásobník prázdný, dojde k provedení podtečení při provádění operací „top stack“ nebo „pop“. Mnoho implementací navíc poskytuje kontrolu, zda je zásobník prázdný a který vrací jeho velikost.

Zásobníky softwaru

Implementace

Zásobník lze snadno implementovat buď prostřednictvím pole, nebo propojeného seznamu . To, co v obou případech identifikuje datovou strukturu jako zásobník, není implementace, ale rozhraní: uživatel může pouze vysouvat nebo zasílat položky do pole nebo propojeného seznamu s několika dalšími pomocnými operacemi. Následující příklad předvede obě implementace pomocí pseudokódu .

Pole

Pole lze použít k implementaci (ohraničeného) zásobníku následujícím způsobem. První prvek, obvykle s nulovým posunem , je spodní, což má za následek, array[0]že je první prvek zasunut do zásobníku a poslední prvek vyskočil. Program musí sledovat velikost (délku) zásobníku pomocí variabilního vrcholu, který zaznamenává počet dosud zasunutých položek, proto ukazuje na místo v poli, kam má být vložen další prvek (za předpokladu nulové konvence založená na indexu). Samotný zásobník tedy lze efektivně implementovat jako tříprvkovou strukturu:

structure stack:
    maxsize : integer
    top : integer
    items : array of item
procedure initialize(stk : stack, size : integer):
    stk.items ← new array of size items, initially empty
    stk.maxsize ← size
    stk.top ← 0

Operace push přidá prvek a zvýší horní index po kontrole přetečení:

procedure push(stk : stack, x : item):
    if stk.top = stk.maxsize:
        report overflow error
    else:
        stk.items[stk.top] ← x
        stk.top ← stk.top + 1

Podobně pop sníží horní index po kontrole podtečení a vrátí položku, která byla dříve nejlepší:

procedure pop(stk : stack):
    if stk.top = 0:
        report underflow error
    else:
        stk.top ← stk.top − 1
        r ← stk.items[stk.top]
        return r

Pomocí dynamického pole je možné implementovat zásobník, který se může zvětšovat nebo zmenšovat podle potřeby. Velikost zásobníku je jednoduše velikost dynamického pole, což je velmi účinná implementace zásobníku, protože přidávání položek nebo odebírání položek na konci dynamického pole vyžaduje amortizovaný čas O (1).

Spojový seznam

Další možností implementace zásobníků je použít jednotlivě propojený seznam . Zásobník je pak ukazatelem na „hlavu“ seznamu, případně s počítadlem pro sledování velikosti seznamu:

structure frame:
    data : item
    next : frame or nil
structure stack:
    head : frame or nil
    size : integer
procedure initialize(stk : stack):
    stk.head ← nil
    stk.size ← 0

Tlačení a vysouvání položek se děje v čele seznamu; přetečení není v této implementaci možné (pokud není paměť vyčerpána):

procedure push(stk : stack, x : item):
    newhead ← new frame
    newhead.data ← x
    newhead.next ← stk.head
    stk.head ← newhead
    stk.size ← stk.size + 1
procedure pop(stk : stack):
    if stk.head = nil:
        report underflow error
    r ← stk.head.data
    stk.head ← stk.head.next
    stk.size ← stk.size - 1
    return r

Zásobníky a programovací jazyky

Některé jazyky, jako například Perl , LISP , JavaScript a Python , zpřístupňují operace zásobníku push a pop na svých standardních typech seznamů/polí. Některé jazyky, zejména ty z rodiny Forthů (včetně PostScriptu ), jsou navrženy kolem jazykově definovaných zásobníků, které jsou přímo viditelné a manipulovány programátorem.

Následuje příklad manipulace se zásobníkem v Common Lisp („ > “ je výzva interpreta Lisp; řádky začínající na „ > “ jsou reakce tlumočníka na výrazy):

> (setf stack (list 'a 'b 'c))  ;; set the variable "stack"
(A B C)
> (pop stack)  ;; get top (leftmost) element, should modify the stack
A
> stack        ;; check the value of stack
(B C)
> (push 'new stack)  ;; push a new top onto the stack
(NEW B C)

Několik typů kontejnerů standardní knihovny C ++operace push_back a pop_back se sémantikou LIFO; Navíc stack šablona třídy přizpůsobí stávající kontejnery poskytnout omezený API pouze s push / pop operací. PHP má třídu SplStack . Knihovna Javy obsahuje Stacktřídu, která je specializací Vector. Následuje příklad programu v jazyce Java , který tuto třídu používá.

import java.util.Stack;

class StackDemo {
    public static void main(String[]args) {
        Stack<String> stack = new Stack<String>();
        stack.push("A");    // Insert "A" in the stack
        stack.push("B");    // Insert "B" in the stack
        stack.push("C");    // Insert "C" in the stack
        stack.push("D");    // Insert "D" in the stack
        System.out.println(stack.peek());    // Prints the top of the stack ("D")
        stack.pop();    // removing the top ("D")
        stack.pop();    // removing the next top ("C")
    }
}

Hardware stack

Běžné použití zásobníků na úrovni architektury je způsob přidělování a přístupu k paměti.

Základní architektura zásobníku

Typický zásobník, který ukládá místní data a informace o hovorech pro volání vnořených procedur (nemusí to být nutně vnořené procedury ). Tento zásobník roste směrem dolů od svého původu. Ukazatel zásobníku ukazuje na aktuální nejvyšší vztažný bod v zásobníku. Operace push zmenší ukazatel a zkopíruje data do zásobníku; operace pop zkopíruje data ze zásobníku a poté zvýší ukazatel. Každá procedura vyvolaná v programu ukládá informace o návratu procedury (žlutě) a lokální data (v jiných barvách) jejich vložením do zásobníku. Tento typ implementace zásobníku je extrémně běžný, ale je náchylný k útokům přetečení vyrovnávací paměti (viz text).

Typický zásobník je oblast počítačové paměti s pevným původem a proměnnou velikostí. Zpočátku je velikost zásobníku nulová. Ukazatel zásobníku, obvykle ve formě hardwarového registru, poukazuje na poslední odkazované umístění na zásobníku; když má zásobník velikost nula, ukazatel zásobníku ukazuje na počátek zásobníku.

Dvě operace použitelné pro všechny hromádky jsou:

  • tlak provoz, ve kterém je datová položka umístěna v místě, na který ukazuje ukazatel zásobníku, a adresa na ukazatel zásobníku se nastaví podle velikosti datové položky;
  • pop nebo pull operace: položka dat v aktuální poloze, na který ukazuje ukazatel zásobníku se odstraní, a ukazatel zásobníku se nastaví podle velikosti datové položky.

Existuje mnoho variací na základní princip operací zásobníku. Každý zásobník má pevné místo v paměti, na kterém začíná. Když jsou do zásobníku přidávány datové položky, ukazatel zásobníku se posune, aby indikoval aktuální rozsah zásobníku, který expanduje od počátku.

Ukazatele zásobníku mohou ukazovat na počátek zásobníku nebo na omezený rozsah adres buď nad, nebo pod původem (v závislosti na směru, ve kterém zásobník roste); ukazatel zásobníku však nemůže překročit původ zásobníku. Jinými slovy, pokud je počátek zásobníku na adrese 1000 a zásobník narůstá směrem dolů (směrem k adresám 999, 998 atd.), Ukazatel zásobníku nikdy nesmí být zvýšen nad 1000 (na 1001, 1002 atd.). Pokud operace pop na zásobníku způsobí, že se ukazatel zásobníku přesune za původ zásobníku, dojde k podtečení zásobníku . Pokud operace push způsobí, že se ukazatel zásobníku zvýší nebo sníží nad maximální rozsah zásobníku, dojde k přetečení zásobníku .

Některá prostředí, která do značné míry spoléhají na komíny, mohou poskytovat další operace, například:

  • Duplikovat : horní položka je vysunuta a poté znovu stisknuta (dvakrát), takže další kopie bývalé horní položky je nyní nahoře a originál pod ní.
  • Peek : je zkontrolována (nebo vrácena) nejvyšší položka, ale ukazatel zásobníku a velikost zásobníku se nezmění (což znamená, že položka zůstává v zásobníku). Tomu se také v mnoha článcích říká špičková operace.
  • Vyměnit nebo vyměnit : dvě nejvyšší položky na místech výměny zásobníku.
  • Rotate (or Roll) : n top položky jsou přesunuty na hromádku rotujícím způsobem. Pokud je například n = 3, položky 1, 2 a 3 v balíčku se přesunou do pozic 2, 3 a 1 v tomto pořadí. Možných je mnoho variant této operace, přičemž nejběžnější se nazývá otáčení doleva a doprava.

Stohy jsou často vizualizovány a rostou zdola nahoru (jako hromady v reálném světě). Mohou být také vizualizovány rostoucí zleva doprava, takže „topmost“ se stane „rightmost“, nebo dokonce rostoucí shora dolů. Důležitou vlastností je, že dno hromádky je v pevné poloze. Obrázek v této části je příkladem vizualizace růstu shora dolů: nahoře (28) je „dole“ zásobníku, protože „nahoře“ (9) zásobníku je místo, kde se položky tlačí nebo vyskakují.

Přímo otáčení se posune první prvek do třetí polohy, druhý pro první a třetí na druhou. Zde jsou dvě ekvivalentní vizualizace tohoto procesu:

apple                         banana
banana    ===right rotate==>  cucumber
cucumber                      apple
cucumber                      apple
banana    ===left rotate==>   cucumber
apple                         banana

Stoh je v počítačích obvykle reprezentován blokem paměťových buněk, přičemž „dno“ je na pevném místě a ukazatel zásobníku obsahuje adresu aktuální „horní“ buňky v zásobníku. Horní a dolní terminologie se používají bez ohledu na to, zda zásobník skutečně roste směrem k nižším adresám paměti nebo k adresám s vyšší pamětí.

Posunutí položky na zásobník upraví ukazatel zásobníku podle velikosti položky (buď zmenšení nebo zvýšení, v závislosti na směru, ve kterém se zásobník zvětšuje v paměti), nasměrováním na další buňku a zkopírováním nové horní položky na oblast zásobníku. V závislosti opět na přesné implementaci může na konci operace push ukazatele zásobníku ukazovat na další nevyužité místo v zásobníku nebo může ukazovat na nejvyšší položku v zásobníku. Pokud zásobník ukazuje na aktuální nejvyšší položku, ukazatel zásobníku se aktualizuje před vložením nové položky do zásobníku; pokud ukazuje na další dostupné místo v zásobníku, bude aktualizováno po vložení nové položky do zásobníku.

Vyskakování hromádky je prostě opakem tlačení. Nejvyšší položka v zásobníku je odebrána a ukazatel zásobníku je aktualizován v opačném pořadí, než jaké bylo použito v operaci push.

Zásobník v hlavní paměti

Mnoho CISC -type CPU designy, včetně x86 , Z80 a 6502 , má vyhrazený registr pro použití jako volání zásobníku ukazatel zásobníku s vyhrazeným hovoru, návrat, push a pop pokyny, které implicitně aktualizovat vyhrazený registr, čímž se zvyšuje kód hustotu. Některé procesory CISC, jako PDP-11 a 68000 , mají také speciální režimy adresování pro implementaci zásobníků , obvykle také s částečně vyhrazeným ukazatelem zásobníku (například A7 v 68000). Naproti tomu většina návrhů CPU RISC nemá vyhrazené instrukce zásobníku, a proto většina, ne -li všechny registry, lze podle potřeby použít jako ukazatele zásobníku.

Stack do registrů nebo vyhrazené paměti

Architektura x87 s plovoucí desetinnou čárkou je příkladem sady registrů organizovaných jako zásobník, kde je také možný přímý přístup k jednotlivým registrům (vzhledem k aktuálnímu vrcholu). Stejně jako u strojů založených na zásobníku obecně platí, že špičkový zásobník jako implicitní argument umožňuje malou stopu strojového kódu s dobrým využitím šířky pásma sběrnice a mezipaměti kódu , ale také brání některým typům možných optimalizací na procesorech, které umožňují náhodný přístup k souboru registru pro všechny (dva nebo tři) operandy. Struktura zásobníku také dělá superskalární implementace s přejmenováním registrů (pro spekulativní provádění ) o něco složitější na implementaci, i když je to stále možné, jak dokládají moderní implementace x87 .

Sun SPARC , AMD Am29000 a Intel i960 jsou příklady architektur využívajících okna registru v zásobníku registrů jako další strategii, jak se vyhnout použití pomalé hlavní paměti pro argumenty funkcí a návratové hodnoty.

Existuje také řada malých mikroprocesorů, které implementují zásobník přímo v hardwaru, a některé mikrokontroléry mají zásobník s pevnou hloubkou, který není přímo přístupný. Příkladem jsou mikrokontroléry PIC , Computer Cowboys MuP21 , řada Harris RTX a Novix NC4016 . K implementaci programovacího jazyka Forth na úrovni mikrokódu bylo použito mnoho stackových mikroprocesorů . Stohy byly také použity jako základ řady sálových počítačů a mini počítačů . Takovým strojům se říkalo stohovací stroje , nejznámější byly Burroughs B5000 .

Aplikace hromádek

Vyhodnocení výrazů a syntaktická analýza

Kalkulačky využívající reverzní polskou notaci používají k uchovávání hodnot strukturu zásobníku. Výrazy mohou být zastoupeny v prefixových, postfixových nebo infixových zápisech a převod z jedné formy do druhé lze provést pomocí zásobníku. Mnoho překladačů používá zásobník pro analýzu syntaxe výrazů, programových bloků atd. Před překladem do kódu nízké úrovně. Většina programovacích jazyků jsou jazyky bez kontextu , což jim umožňuje analyzovat stroje založené na zásobníku.

Zpětné sledování

Další důležitou aplikací stacků je zpětné sledování . Zvažte jednoduchý příklad nalezení správné cesty v bludišti. Existuje řada bodů, od výchozího bodu k cíli. Začínáme z jednoho bodu. K dosažení konečného cíle vede několik cest. Předpokládejme, že vybereme náhodnou cestu. Po sledování určité cesty si uvědomujeme, že cesta, kterou jsme si vybrali, je špatná. Musíme tedy najít způsob, kterým se můžeme vrátit na začátek této cesty. To lze provést pomocí hromádek. Pomocí hromádek si pamatujeme bod, kde jsme dosáhli. To se provádí zasunutím tohoto bodu do zásobníku. V případě, že skončíme na špatné cestě, můžeme vyskočit poslední bod ze zásobníku a vrátit se tak k poslednímu bodu a pokračovat v hledání správné cesty. Tomu se říká zpětné sledování.

Prototypickým příkladem algoritmu zpětného sledování je hloubkové vyhledávání , které najde všechny vrcholy grafu, které lze dosáhnout ze zadaného počátečního vrcholu. Jiné aplikace zpětného sledování zahrnují vyhledávání v prostorech, které představují potenciální řešení problému s optimalizací. Branch and bound je technika pro provádění takových zpětných vyhledávání, aniž by se vyčerpávajícím způsobem prohledávala všechna potenciální řešení v takovém prostoru.

Kompilace správy časové paměti

Řada programovacích jazyků je orientována na zásobník , což znamená, že definují většinu základních operací (sčítání dvou čísel, tisk znaku) jako převzetí argumentů ze zásobníku a vrácení všech návratových hodnot zpět do zásobníku. Například PostScript má návratový zásobník a zásobník operandů a také má zásobník stavů grafiky a zásobník slovníku. Mnoho virtuálních počítačů je také orientováno na zásobník, včetně stroje s p-kódem a Java Virtual Machine .

Téměř všechny konvence volání ‍ — ways způsoby, kterými podprogramy přijímají své parametry a vracejí výsledky‍ — ‌použití speciálního zásobníku („ zásobník volání “) k uchovávání informací o volání procedur/funkcí a vnořování za účelem přepnutí do kontextu volané funkce a po dokončení volání obnovit funkci volajícího. Funkce sledují běhový protokol mezi volajícím a volaným a ukládají argumenty a návratovou hodnotu do zásobníku. Zásobníky jsou důležitým způsobem podpory vnořených nebo rekurzivních volání funkcí. Tento typ zásobníku implicitně používá kompilátor k podpoře příkazů CALL a RETURN (nebo jejich ekvivalentů) a není manipulován přímo programátorem.

Některé programovací jazyky používají zásobník k ukládání dat, která jsou lokální pro proceduru. Místo pro místní datové položky je přiděleno ze zásobníku při zadání procedury a je uvolněno, když je procedura ukončena. C programovací jazyk je obvykle realizován tímto způsobem. Použití stejného zásobníku pro volání dat i procedur má důležité bezpečnostní důsledky (viz níže), kterých si musí být programátor vědom, aby se vyhnul zavádění závažných bezpečnostních chyb do programu.

Efektivní algoritmy

Několik algoritmů používá zásobník (oddělený od obvyklého zásobníku volání funkcí většiny programovacích jazyků) jako základní datovou strukturu, se kterou organizují své informace. Tyto zahrnují:

  • Grahamovo skenování , algoritmus pro konvexní trup dvojrozměrné soustavy bodů. Konvexní trup podmnožiny vstupu je udržován v zásobníku, který se používá k nalezení a odstranění konkávností na hranici, když je do trupu přidán nový bod.
  • Část algoritmu SMAWK pro hledání řádkových minim monotónní matice využívá hromádky podobným způsobem jako Grahamovo skenování.
  • Všechny nejbližší menší hodnoty , problém najít pro každé číslo v poli nejbližší předchozí číslo, které je menší než ono. Jeden algoritmus pro tento problém používá zásobník k udržení kolekce kandidátů na nejbližší menší hodnotu. Pro každou pozici v poli je zásobník vyskočen, dokud není na jeho vrcholu nalezena menší hodnota, a poté je hodnota v nové poloze zasunuta do zásobníku.
  • Algoritmus řetězce nejbližšího okolí , způsob aglomerativní hierarchického shlukování založené na udržení stohu shluků, z nichž každý je nejbližší soused jeho předchůdce na zásobníku. Když tato metoda najde pár klastrů, které jsou vzájemnými nejbližšími sousedy, jsou vyskočeny a sloučeny.

Bezpečnostní

Některá výpočetní prostředí používají komíny způsobem, který je činí zranitelnými vůči narušení zabezpečení a útokům. Programátoři pracující v takovém prostředí musí věnovat zvláštní pozornost tomu, aby se vyhnuli nástrahám těchto implementací.

Například některé programovací jazyky používají společný zásobník pro ukládání lokálních dat do volané procedury a informací o propojení, které umožňují proceduře návrat k jejímu volajícímu. To znamená, že program přesouvá data do a ze stejného zásobníku, který obsahuje kritické návratové adresy pro volání procedur. Pokud jsou data přesunuta na nesprávné místo v zásobníku nebo je nadměrně velká datová položka přesunuta do umístění zásobníku, které není dostatečně velké, aby je obsahovalo, může dojít k poškození návratových informací pro volání procedur, což způsobí selhání programu.

Škodlivé strany se mohou pokusit o hromadný útok, který využívá výhod tohoto typu implementace tím, že poskytuje nadměrné zadávání dat programu, který nekontroluje délku vstupu. Takový program může data zkopírovat celá na místo v zásobníku, a tím může změnit zpáteční adresy pro procedury, které jej zavolaly. Útočník může experimentovat, aby našel konkrétní typ dat, která mohou být poskytnuta takovému programu, takže návratová adresa aktuálního postupu je resetována tak, aby směřovala do oblasti v samotném zásobníku (a v datech poskytnutých útočníkem), který zase obsahuje pokyny, které provádějí neoprávněné operace.

Tento typ útoku je variací na útok přetečení vyrovnávací paměti a je extrémně častým zdrojem narušení zabezpečení v softwaru, zejména proto, že některé z nejpopulárnějších překladačů používají sdílený zásobník pro volání dat i procedur a neověřují délku datové položky. Programátoři často nepíší kód, aby ověřili velikost datových položek, a když se do zásobníku zkopíruje nadrozměrná nebo poddimenzovaná datová položka, může dojít k narušení zabezpečení.

Viz také

Reference

Další čtení

externí odkazy