Beste antwoord
In informatica , een abstract gegevenstype ( ADT ) is een wiskundig model voor gegevenstypen waarbij een gegevenstype wordt gedefinieerd door zijn gedrag ( semantiek ) vanuit het oogpunt van een gebruiker van de gegevens, met name in termen van mogelijke waarden, mogelijke bewerkingen op gegevens van dit type en het gedrag van deze bewerkingen. Dit staat in contrast met datastructuren , die concrete weergaven van gegevens zijn en het standpunt zijn van een implementator, niet van een gebruiker.
Van Datastructuur :
In informatica , een gegevensstructuur is een specifieke manier om gegevens op een computer te ordenen, zodat deze kunnen worden gebruikt efficiënt .
Datastructuren kunnen een of meer specifieke abstracte gegevenstypen implementeren (ADT), die het middel zijn om het bewerkingscontract en hun complexiteit
Een datastructuur is een concrete uitvoering van het contract geleverd door een ADT
Wat dat betekent is:
1. ADT is een abstracte weergave, vanuit het standpunt van de gebruiker
2. DS is concrete representatie, niet vanuit het oogpunt van de gebruiker
In eenvoudige bewoordingen:
1. Stack is ADT , het specificeert alleen dat er een push, pop, etc. moet zijn die de gebruiker kan gebruiken.
2. Stack (net als andere ADTs zoals Queue) wordt geïmplementeerd met DS zoals array of lijst (gekoppelde lijst, etc.)
Samenvatting:
Stack is niet DS, het is ADT en wordt geïmplementeerd met andere DS.
Hoop dat dat heeft geholpen.
Veel succes
Antwoord
Stapels
Een stapel is een container met objecten die worden geplaatst en verwijderd volgens het last-in first-out (LIFO) -principe. In de pushdown-stapels zijn slechts twee bewerkingen toegestaan: push het item in de stapel, en pop het item uit de stapel. Een stapel is een datastructuur met beperkte toegang – elementen kunnen alleen bovenaan aan de stapel worden toegevoegd en verwijderd. push voegt een item toe aan de bovenkant van de stapel, pop verwijdert het item van de bovenkant . Een nuttige analogie is te denken aan een stapel boeken; je kunt alleen het bovenste boek verwijderen, je kunt ook een nieuw boek bovenaan toevoegen.
Een stapel is een recursieve datastructuur. Hier is een structurele definitie van een stapel:
Applicaties
- De eenvoudigste toepassing van een stapel is om een woord om te keren. Je drukt op een bepaald woord om te stapelen – letter voor letter – en dan laat je letters uit de stapel.
- Een andere toepassing is een “ongedaan maken” -mechanisme in teksteditors; deze bewerking wordt bereikt door alle tekstwijzigingen in een stapel te bewaren. Backtracking . Dit is een proces waarbij u toegang moet hebben tot het meest recente gegevenselement in een reeks elementen. Denk aan een labyrint of doolhof – hoe vind je een weg van een ingang naar een uitgang? Als je eenmaal op een doodlopende weg bent, moet je teruggaan. Maar terug naar waar? naar het vorige keuzepunt. Daarom slaat u op elk keuzepunt alle mogelijke keuzes op een stapel op. Backtracking betekent dan simpelweg een volgende keuze uit de stapel halen.
- Taalverwerking: ruimte voor parameters en lokale variabelen wordt intern gemaakt met behulp van een stack. Compilers syntaxiscontrole voor overeenkomende accolades wordt geïmplementeerd met behulp van stack.support voor recursie
Implementatie
In de standaardbibliotheek met klassen is de datatype-stack een adapter class, wat betekent dat een stack bovenop andere gegevensstructuren wordt gebouwd. De onderliggende structuur van een stack kan een array, een vector, een ArrayList, een gekoppelde lijst of een andere verzameling Ongeacht het type onderliggende datastructuur, een Stack moet dezelfde functionaliteit implementeren.Dit wordt bereikt door een unieke interface te bieden:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
De de volgende afbeelding toont het idee van implementatie op compositie .
Een andere implementatie-eis (naast de bovenstaande interface) is dat alle stack-operaties moeten worden uitgevoerd in
constante tijd O (1)
. Constante tijd betekent dat er een constante k is, zodat een bewerking k nanoseconden rekentijd in beslag neemt, ongeacht de grootte van de stack.
Array-gebaseerde implementatie
In een array-gebaseerde implementatie onderhouden we de volgende velden: een array A met een standaardgrootte (≥ 1 ), de variabele top die verwijst naar het bovenste element in de stapel en de capaciteit die verwijst naar de array-grootte. De variabele top verandert van -1 in capacity - 1. We zeggen dat een stapel leeg is wanneer top = -1, en de stapel is vol wanneer top = capacity-1.
In een vaste -size stack abstractie, de capaciteit blijft ongewijzigd, dus wanneer top capaciteit bereikt, de stack object genereert een uitzondering.
In een dynamische stack-abstractie wanneer top capaciteit bereikt , verdubbelen we de stackgrootte.
Linked List-gebaseerde implementatie
Linked List-gebaseerde implementatie biedt de beste (vanuit het oogpunt van efficiëntie) dynamische stack-implementatie.
Bron – Stapels en wachtrijen