Zásobník (dátová štruktúra)

Zásobník je jednou z najdôležitejších dátových štruktúr v informatike. Ak chcete pochopiť, ako zásobník funguje, predstavte si balíček hracích kariet, ktorý je otočený lícom nadol. Ľahko môžeme pristupovať len ku karte, ktorá je na vrchu. Keď sa chceme pozrieť na vrchnú kartu, môžeme urobiť dve veci: môžeme na ňu nahliadnuť, ale nechať ju na zásobníku, alebo ju môžeme vyložiť. Keď vrchný objekt odskočíme, odoberieme ho z hromádky. Ak chceme na vrchol zásobníka pridať ďalšiu kartu, tak ju vytlačíme.

Zásobník sa nazýva kolekcia LIFO (last-in-first-out). To znamená, že posledná vec, ktorú sme pridali (push), je prvá vec, ktorá sa vytiahne (popped). Ak poslednou kartou, ktorú sme pridali na náš zásobník kariet, bolo eso, potom prvou kartou, ktorú sme vytiahli z vrcholu, je to isté eso.

Dve akcie na zásobníku: push a pop.Zoom
Dve akcie na zásobníku: push a pop.

História

Tento komín prvýkrát navrhol v roku 1955 a v roku 1957 ho patentoval Nemec Friedrich L. Bauer. Rovnaký koncept vyvinul nezávisle, približne v rovnakom čase, Austrálčan Charles Leonard Hamblin.

Ostatné operácie

V moderných počítačových jazykoch sa zásobník zvyčajne implementuje pomocou viacerých operácií než len "push" a "pop". Niektoré implementácie majú funkciu, ktorá vracia aktuálnu dĺžku zásobníka. Ďalšou typickou pomocnou operáciou je operácia "top" (známa aj ako "peek"), ktorá môže vrátiť aktuálny horný prvok zásobníka bez toho, aby ho odstránila. Ďalšou bežnou operáciou je "dup", ktorá vytvorí kópiu prvku na vrchole zásobníka.

Súvisiace stránky

  • Stohovací stroj

AlegsaOnline.com - 2020 / 2023 - License CC3