Bedste svar
I datalogi er en abstrakt datatype ( ADT ) er en matematisk model til datatyper hvor en datatype defineres af dens adfærd ( semantik ) set fra et bruger af dataene, specifikt med hensyn til mulige værdier, mulige operationer på data af denne type og disse operationers adfærd. Dette står i kontrast til datastrukturer , som er konkrete repræsentationer af data og er synspunktet for en implementer, ikke en bruger.
Fra Datastruktur :
I datalogi , en datastruktur er en særlig måde at organisere data på en computer, så de kan bruges effektivt .
Datastrukturer kan implementere en eller flere bestemte abstrakte datatyper (ADT), som er midlerne til at specificere driftskontrakten og deres kompleksitet
En datastruktur er en konkret implementering af kontrakten leveret af en ADT
Hvad det betyder er:
1. ADT er abstrakt repræsentation set fra brugerens synspunkt
2. DS er konkret repræsentation, ikke fra brugerens synspunkt
Enkelt sagt:
1. Stack er ADT , det angiver kun, at der skal være et push, pop osv., som brugeren kan bruge.
2. Stak (som andre ADTer som kø) implementeres ved hjælp af DS som array eller liste (linket liste osv.)
Resumé:
Stack er ikke DS, det er ADT og implementeres ved hjælp af anden DS.
Håber det hjalp.
Held og lykke
Svar
Stakke
En stak er en beholder med objekter, der indsættes og fjernes i overensstemmelse med LIFO-princippet (last-in first-out). I pushdown-stakken er kun to operationer tilladt: skubber elementet i stakken, og pop genstanden ud af stakken. En stak er en begrænset adgangsdatastruktur – elementer kan kun tilføjes og fjernes fra stakken øverst. push tilføjer et element øverst i stakken, pop fjerner elementet fra toppen . En nyttig analogi er at tænke på en stak bøger; du kan kun fjerne den øverste bog, og du kan også tilføje en ny bog øverst.
En stak er en rekursiv datastruktur. Her er en strukturel definition af en stak:
Applikationer
- Den enkleste anvendelse af en stak er at vende et ord om. Du skubber et givet ord for at stakke – bogstav for bogstav – og derefter pop bogstaver fra stakken.
- Et andet program er en “fortryd” -mekanisme i tekstredigeringsprogrammer; denne handling udføres ved at opbevare alle tekstændringer i en stak. Backtracking . Dette er en proces, når du skal have adgang til det nyeste dataelement i en række elementer. Tænk på en labyrint eller labyrint – hvordan finder du en vej fra en indgang til en udgang? Når du når en blindgyde, skal du gå tilbage. Men tilbage til hvor? til det forrige valgpunkt. Derfor gemmer du på hvert valgpunkt på en stak alle mulige valg. Derefter betyder backtracking simpelthen at poppe et næste valg fra stakken.
- Sprogbehandling: plads til parametre og lokale variabler oprettes internt ved hjælp af en stack.compilers syntakscheck for matchende seler implementeres ved hjælp af stack.support til rekursion
Implementering
I standardbiblioteket med klasser er datatypestakken en adapter klasse, hvilket betyder at en stak er bygget oven på andre datastrukturer. Den underliggende struktur for en stak kan være en matrix, en vektor, en ArrayList, en linket liste eller enhver anden samling. Uanset typen af den underliggende datastruktur skal en stak implementere den samme funktionalitet.Dette opnås ved at tilvejebringe en unik grænseflade:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
det følgende billede demonstrerer ideen om implementering ved sammensætning .
Et andet implementeringskrav (ud over ovenstående interface) er, at alle stack-operationer skal køre i
konstant tid O (1)
. Konstant tid betyder, at der er nogle konstante k, således at en operation tager k nanosekunder beregningstid uanset stakstørrelsen.
Arraybaseret implementering
I en array-baseret implementering opretholder vi følgende felter: en array A med standardstørrelse (≥ 1 ), variablen top , der refererer til det øverste element i stakken og kapacitet henviser til arraystørrelsen. Variablen øverst ændres fra -1 til capacity - 1. Vi siger, at en stak er tom, når top = -1, og stakken er fuld, når top = capacity-1.
I en fast -størrelse stakabstraktion, kapaciteten forbliver uændret, derfor når top når kapacitet , stakken objekt kaster en undtagelse.
I en dynamisk stakabstraktion, når top når kapacitet , vi fordobler stakstørrelsen.
Linket listebaseret implementering
Linket listebaseret implementering giver den bedste (fra effektivitetsmæssigt synspunkt) dynamisk stakimplementering.
Kilde – Stakke og køer