Beste svaret
I informatikk , en abstrakt datatype ( ADT ) er en matematisk modell for datatyper der en datatype er definert av oppførselen ( semantikk ) fra et bruker av dataene, spesielt når det gjelder mulige verdier, mulige operasjoner på data av denne typen og oppførselen til disse operasjonene. Dette står i kontrast til datastrukturer , som er konkrete representasjoner av data, og er synspunktet til en implementer, ikke en bruker.
Fra Datastruktur :
I informatikk , en datastruktur er en bestemt måte å organisere data på en datamaskin slik at de kan brukes effektivt .
Datastrukturer kan implementere en eller flere bestemte abstrakte datatyper (ADT), som er middel til å spesifisere operasjonskontrakten og deres kompleksitet
En datastruktur er en konkret implementering av kontrakten levert av en ADT
Hva det betyr er:
1. ADT er abstrakt representasjon, fra brukerens synspunkt
2. DS er konkret representasjon, ikke fra brukerens synspunkt
Enkelt sagt:
1. Stack er ADT , det spesifiserer bare at det skal være trykk, pop osv. for brukeren å bruke.
2. Stack (som andre ADT-er som kø) er implementert ved hjelp av DS som array eller liste (lenket liste osv.)
Sammendrag:
Stack er ikke DS, det er ADT, og implementeres ved hjelp av annen DS.
Håper det hjalp.
Lykke til
Svar
Stabler
En stabel er en beholder med gjenstander som settes inn og fjernes i henhold til LIFO-prinsippet (last-in first-out). I nedtrappingsstakkene er bare to operasjoner tillatt: skyv elementet i bunken, og pop varen ut av bunken. En bunke er en datastruktur med begrenset tilgang – elementer kan bare legges til og fjernes fra bunken øverst. push legger til et element øverst i bunken, pop fjerner elementet fra toppen . En nyttig analogi er å tenke på en bunkebunke; du kan bare fjerne toppboken, og du kan også legge til en ny bok på toppen.
En stabel er en rekursiv datastruktur. Her er en strukturell definisjon av en stabel:
Programmer
- Den enkleste applikasjonen av en stabel er å snu et ord. Du skyver et gitt ord for å stable – bokstav for bokstav – og deretter spretter bokstaver fra stabelen.
- Et annet program er en «angre» -mekanisme i tekstredigeringsprogrammer; denne operasjonen oppnås ved å holde alle tekstendringer i en bunke. Backtracking . Dette er en prosess når du trenger tilgang til det nyeste dataelementet i en rekke elementer. Tenk på en labyrint eller labyrint – hvordan finner du en vei fra inngang til utgang? Når du er i en blindgate, må du gå tilbake. Men tilbake til hvor? til forrige valgpunkt. Derfor lagrer du på hvert valgpunkt på en bunke alle mulige valg. Da betyr backtracking ganske enkelt å poppe et neste valg fra bunken.
- Språkbehandling: Plass for parametere og lokale variabler opprettes internt ved hjelp av en stack.compilers syntaksjekk for matchende klammeparenteser implementeres ved hjelp av stack.support for rekursjon
Implementering
I standardbiblioteket med klasser er datatypestakken en adapter klasse, noe som betyr at en stabel er bygget oppå andre datastrukturer. Den underliggende strukturen for en stabel kan være en matrise, en vektor, en ArrayList, en koblet liste eller annen samling. Uavhengig av typen underliggende datastruktur, må en Stack implementere den samme funksjonaliteten.Dette oppnås ved å tilby et unikt grensesnitt:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
The følgende bilde demonstrerer ideen om implementering ved komposisjon .
Et annet implementeringskrav (i tillegg til grensesnittet ovenfor) er at alle stack-operasjoner må kjøre i
konstant tid O (1)
. Konstant tid betyr at det er noen konstante k slik at en operasjon tar k nanosekunder beregningstid uansett stabelstørrelse.
Arraybasert implementering
I en arraybasert implementering opprettholder vi følgende felt: en array A med standardstørrelse (≥ 1 ), variabelen topp som refererer til toppelementet i stakken og kapasitet refererer til matrisestørrelsen. Variabelen toppen endres fra -1 til capacity - 1. Vi sier at en stabel er tom når top = -1, og stakken er full når top = capacity-1.
I en fast -størrelsesstakkabstrahering, kapasiteten forblir uendret, derfor når toppen når kapasitet , stakken objekt kaster et unntak.
I en dynamisk stakkabstrahering når topp når kapasitet , vi dobler opp stabelstørrelsen.
Koblet listebasert implementering
Koblet listebasert implementering gir den beste (fra effektivitetssynspunktet) dynamisk stackimplementering.
Kilde – Stabler og køer