Nejlepší odpověď
V počítačové vědě je abstraktní datový typ ( ADT ) je matematický model pro datové typy , kde je datový typ definován jeho chováním ( sémantika ) z hlediska uživatel dat, zejména pokud jde o možné hodnoty, možné operace s daty tohoto typu a chování těchto operací. To kontrastuje s datovými strukturami , které jsou konkrétními reprezentacemi dat a jsou hlediskem implementátora, nikoli uživatele.
Z Datové struktury :
V počítačové vědě je datová struktura je zvláštní způsob organizace dat v počítači, aby jej bylo možné použít efektivně .
Datové struktury mohou implementovat jeden nebo více konkrétních abstraktních datových typů (ADT), což jsou prostředky k určení smlouvy o provozu a jejich složitosti
Datová struktura je konkrétní implementace smlouvy poskytované ADT
Co to znamená:
1. ADT je z pohledu uživatele abstraktní reprezentace
2. DS je konkrétní reprezentace, ne z pohledu uživatele
Zjednodušeně řečeno:
1. Zásobník je ADT , pouze specifikuje, že by uživatel měl mít push, pop atd.
2. Stack (stejně jako jiné ADT jako Queue) je implementován pomocí DS like pole nebo seznam (propojený seznam atd.)
Shrnutí:
Zásobník není DS, je to ADT a je implementován pomocí ostatní DS.
Doufám, že to pomohlo.
Hodně štěstí
Odpověď
Hromádky
Hromádka je kontejner objektů, které jsou vkládány a odebírány v souladu s principem Last-in-First-Out (LIFO). V zásobních zásobnících jsou povoleny pouze dvě operace: zatlačit položku do zásobníku a pop položka ze zásobníku. Zásobník je datová struktura s omezeným přístupem – prvky lze přidávat a odebírat ze zásobníku pouze nahoře. push přidá položku do horní části zásobníku, pop odebere položku z horní části . Užitečnou analogií je vymyslet hromadu knih; můžete odstranit pouze horní knihu, a také můžete přidat novou knihu nahoře.
Zásobník je rekurzivní datová struktura. Zde je strukturální definice zásobníku:
Aplikace
- Nejjednodušší aplikací zásobníku je obrácení slova. Posunete dané slovo do zásobníku – písmeno za písmenem – a poté ze zásobníku vyskočíte písmena.
- Další aplikací je mechanismus „zpět“ v textových editorech; této operace je dosaženo udržováním všech textových změn v zásobníku. Zpětný sled . Jedná se o proces, kdy potřebujete získat přístup k nejnovějšímu datovému prvku v řadě prvků. Přemýšlejte o labyrintu nebo bludišti – jak najdete cestu od vchodu k východu? Jakmile se dostanete do slepé uličky, musíte ustoupit. Ale ústup ke kterému? k předchozímu bodu výběru. Proto v každém bodě výběru ukládáte na hromádku všechny možné možnosti. Backtracking simply means popping a next choice from the stack.
- Language processing: space for parameters and local variables is created internally using a stack.compiler „s syntaxe check for matching braces is implemented by using stack.support pro rekurzi
Implementace
Ve standardní knihovně tříd je zásobník datového typu třída adaptéru , což znamená, že zásobník je postaven nad ostatní datové struktury. Základní strukturou zásobníku může být pole, vektor, ArrayList, propojený seznam nebo jakákoli jiná kolekce. Bez ohledu na typ podkladové datové struktury musí zásobník implementovat stejnou funkci.Toho je dosaženo poskytnutím jedinečného rozhraní:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
následující obrázek demonstruje myšlenku implementace složením .
Dalším implementačním požadavkem (kromě výše uvedeného rozhraní) je, že všechny operace zásobníku musí běžet
konstantní čas O (1)
. Konstantní čas znamená, že existuje nějaká konstanta k taková, že operace trvá k nanosekundám výpočetního času bez ohledu na velikost zásobníku.
Implementace na základě pole
V implementaci založené na poli udržujeme následující pole: pole A výchozí velikosti (≥ 1 ), proměnná top , která odkazuje na horní prvek v zásobníku a kapacita , která odkazuje na velikost pole. Proměnná nahoře se změní z -1 na capacity - 1. Říkáme, že zásobník je prázdný, když top = -1, a zásobník je plný, když top = capacity-1.
V pevném – abstrakce velikosti zásobníku, kapacita zůstane nezměněna, proto když nahoře dosáhne kapacity , zásobník objekt vyvolá výjimku.
V dynamické abstrakci zásobníku, když nahoru dosáhne kapacity , zdvojnásobíme velikost zásobníku.
Implementace na základě propojeného seznamu
Na základě propojeného seznamu implementace poskytuje nejlepší (z hlediska efektivity) dynamickou implementaci zásobníku.
Zdroj – Hromádky a fronty