Zásobník (datová struktura)

Zásobník je jednou z nejdůležitějších datových struktur v informatice. Chcete-li pochopit, jak zásobník funguje, představte si balíček hracích karet, který je položen lícem dolů. Snadno můžeme přistupovat pouze ke kartě, která je nahoře. Když se chceme podívat na horní kartu, můžeme udělat dvě věci: můžeme na ni nahlédnout, ale nechat ji na hromádce, nebo ji můžeme odklopit. Když vrchní předmět odklopíme, vyjmeme jej z hromádky. Chceme-li na vrchol hromádky přidat další kartu, zatlačíme ji.

Zásobník se nazývá kolekce LIFO (last-in-first-out). To znamená, že poslední věc, kterou jsme přidali (pushed), je první, která se z něj vytáhne (popped). Pokud poslední karta, kterou jsme na hromádku karet přiložili, bylo eso, pak první karta, kterou jsme z ní vytáhli, je totéž eso.

Dvě akce na zásobníku: push a pop.Zoom
Dvě akce na zásobníku: push a pop.

Historie

Tento komín poprvé navrhl v roce 1955 a v roce 1957 si jej nechal patentovat Němec Friedrich L. Bauer. Stejný koncept vyvinul nezávisle na něm přibližně ve stejné době Australan Charles Leonard Hamblin.

Ostatní operace

V moderních počítačových jazycích je zásobník obvykle implementován pomocí více operací než jen "push" a "pop". Některé implementace mají funkci, která vrací aktuální délku zásobníku. Další typickou pomocnou operací je "top" (známá také jako "peek"), která může vrátit aktuální horní prvek zásobníku, aniž by jej odstranila. Další běžnou operací je "dup", která vytvoří kopii prvku na vrcholu zásobníku.

Související stránky

  • Stack machine

AlegsaOnline.com - 2020 / 2023 - License CC3