Bästa svaret
Från Abstrakt datatyp:
I datavetenskap , en abstrakt datatyp ( ADT ) är en matematisk modell för datatyper där en datatyp definieras av dess beteende ( semantik ) från en användare av uppgifterna, särskilt när det gäller möjliga värden, möjliga operationer av data av denna typ och beteendet hos dessa operationer. Detta står i kontrast till datastrukturer , som är konkreta representationer av data och är en implementerares synvinkel, inte en användare.
Från Datastruktur :
I datavetenskap , en datastruktur är ett särskilt sätt att organisera data i en dator så att den kan användas effektivt .
Datastrukturer kan implementera en eller flera specifika abstrakta datatyper (ADT), vilket är sättet att specificera kontraktet och deras komplexitet
En datastruktur är en konkret implementering av kontraktet som tillhandahålls av en ADT
Vad det betyder är:
1. ADT är abstrakt -representation, ur användarsynpunkt
2. DS är konkret representation, inte ur användarens synvinkel
Enkelt uttryckt:
1. Stack är ADT , det anger bara att det ska finnas en push, pop etc. för användaren att använda.
2. Stack (som andra ADT: er som kö) implementeras med DS som array eller lista (länkad lista, etc.)
Sammanfattning:
Stack är inte DS, det är ADT och implementeras med annan DS.
Hoppas det hjälpte.
Lycka till
Svar
Stacks
En stack är en behållare med föremål som sätts in och tas bort enligt LIFO-principen (last-in first-out). I pushdown-staplarna är endast två operationer tillåtna: push objektet i stacken och pop föremålet ur bunten. En stack är en begränsad åtkomstdatastruktur – element kan läggas till och tas bort från stacken endast högst upp. push lägger till ett objekt högst upp i stapeln, pop tar bort objektet från toppen . En bra analogi är att tänka på en bunt böcker; du kan bara ta bort den översta boken, du kan också lägga till en ny bok överst.
En stack är en rekursiv datastruktur. Här är en strukturell definition av en stack:
Applications
- Den enklaste applikationen av en stack är att vända ett ord. Du trycker på ett visst ord för att stapla – bokstav för bokstav – och poppar sedan bokstäver från stapeln.
- Ett annat program är en ”ångra” -mekanism i textredigerare; den här åtgärden utförs genom att hålla alla textändringar i en stapel. Backtracking . Detta är en process när du behöver komma åt det senaste dataelementet i en serie element. Tänk på en labyrint eller labyrint – hur hittar du en väg från en ingång till en utgång? När du når en återvändsgränd, måste du backtrack. Men tillbaka till vart? till föregående valpunkt. Därför lagrar du alla möjliga val på en stapel vid varje valpunkt. Sedan betyder backtrack helt enkelt att poppa ett nästa val från stacken.
- Språkbehandling: utrymme för parametrar och lokala variabler skapas internt med hjälp av en stack.compilers syntaxkontroll för matchande hakparentes implementeras med stack.support för rekursion
Implementering
I standardbiblioteket med klasser är datatypen en -adapter -klass, vilket innebär att en stack byggs ovanpå andra datastrukturer. Den underliggande strukturen för en stack kan vara en array, en vektor, en ArrayList, en länkad lista eller någon annan samling. Oavsett typen av underliggande datastruktur måste en stack implementera samma funktionalitet.Detta uppnås genom att tillhandahålla ett unikt gränssnitt:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
The följande bild visar tanken på implementering genom komposition .
Ett annat implementeringskrav (förutom ovanstående gränssnitt) är att alla stackoperationer måste köras i
konstant tid O (1)
. Konstant tid betyder att det finns någon konstant k så att en operation tar k nanosekunder av beräkningstid oavsett stackstorleken.
Arraybaserad implementering
I en arraybaserad implementering behåller vi följande fält: en array A med standardstorlek (≥ 1 ), variabeln topp som hänvisar till toppelementet i stacken och kapacitet som hänvisar till gruppstorleken. Variabeln överst ändras från -1 till capacity - 1. Vi säger att en stack är tom när top = -1, och stacken är full när top = capacity-1.
I en fast -storlek abstraktion, stacken förblir oförändrad, därför när topp når kapacitet , stacken objekt ger ett undantag.
I en dynamisk stackabstraktion när topp når kapacitet , vi dubblar stapelstorleken.
Länkad listbaserad implementering
Länkad listbaserad implementering ger den bästa (ur effektivitetssynpunkt) dynamisk stackimplementering.
Källa – Travar och köer