Datenstruktur und Algorithmen - Stack
Ein Stapel ist ein abstrakter Datentyp (ADT), der in den meisten Programmiersprachen häufig verwendet wird. Es wird Stapel genannt, da es sich beispielsweise wie ein realer Stapel verhält - ein Kartenspiel oder ein Stapel Teller usw.
Ein realer Stapel ermöglicht Operationen nur an einem Ende. Zum Beispiel können wir eine Karte oder einen Teller nur von der Oberseite des Stapels platzieren oder entfernen. Ebenso erlaubt Stack ADT alle Datenoperationen nur an einem Ende. Zu jedem Zeitpunkt können wir nur auf das oberste Element eines Stapels zugreifen.
Diese Funktion macht es LIFO-Datenstruktur. LIFO steht für Last-in-first-out. Hier wird zuerst auf das Element zugegriffen, das zuletzt platziert (eingefügt oder hinzugefügt) wurde. In der Stapelterminologie wird die Einfügeoperation aufgerufenPUSH Operation und Entfernung Operation wird aufgerufen POP Betrieb.
Stapelrepräsentation
Das folgende Diagramm zeigt einen Stapel und seine Operationen -
Ein Stapel kann mithilfe von Array, Struktur, Zeiger und verknüpfter Liste implementiert werden. Der Stapel kann entweder eine feste Größe haben oder eine dynamische Größenänderung aufweisen. Hier werden wir Stack mithilfe von Arrays implementieren, was es zu einer Stack-Implementierung mit fester Größe macht.
Grundoperationen
Bei Stapeloperationen kann der Stapel initialisiert, verwendet und anschließend de-initialisiert werden. Abgesehen von diesen grundlegenden Dingen wird ein Stapel für die folgenden zwei Hauptoperationen verwendet -
push() - Ein Element auf den Stapel schieben (speichern).
pop() - Entfernen (Zugreifen) eines Elements vom Stapel.
Wenn Daten auf den Stapel gedrückt werden.
Um einen Stapel effizient zu nutzen, müssen wir auch den Status des Stapels überprüfen. Aus dem gleichen Grund wird den Stapeln die folgende Funktionalität hinzugefügt:
peek() - Holen Sie sich das oberste Datenelement des Stapels, ohne es zu entfernen.
isFull() - Überprüfen Sie, ob der Stapel voll ist.
isEmpty() - Überprüfen Sie, ob der Stapel leer ist.
Wir behalten jederzeit einen Zeiger auf die letzten PUSHed-Daten auf dem Stapel bei. Da dieser Zeiger immer die Spitze des Stapels darstellt, daher benannttop. Dastop Der Zeiger liefert den höchsten Wert des Stapels, ohne ihn tatsächlich zu entfernen.
Zuerst sollten wir uns mit Verfahren zur Unterstützung von Stapelfunktionen vertraut machen -
spähen()
Algorithmus der Funktion peek () -
begin procedure peek
return stack[top]
end procedure
Implementierung der Funktion peek () in der Programmiersprache C -
Example
int peek() {
return stack[top];
}
ist voll()
Algorithmus der isfull () Funktion -
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementierung der Funktion isfull () in der Programmiersprache C -
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
ist leer()
Algorithmus der Funktion isempty () -
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
Die Implementierung der Funktion isempty () in der Programmiersprache C unterscheidet sich geringfügig. Wir initialisieren top bei -1, da der Index im Array bei 0 beginnt. Wir prüfen also, ob der top unter Null oder -1 liegt, um festzustellen, ob der Stapel leer ist. Hier ist der Code -
Example
bool isempty() {
if(top == -1)
return true;
else
return false;
}
Push-Betrieb
Das Einfügen eines neuen Datenelements in einen Stapel wird als Push-Operation bezeichnet. Der Push-Betrieb umfasst eine Reihe von Schritten -
Step 1 - Überprüft, ob der Stapel voll ist.
Step 2 - Wenn der Stapel voll ist, wird ein Fehler ausgegeben und beendet.
Step 3 - Wenn der Stapel nicht voll ist, werden die Schritte erhöht top um auf den nächsten leeren Raum zu zeigen.
Step 4 - Fügt dem Stapelspeicherort ein Datenelement hinzu, auf das oben zeigt.
Step 5 - Gibt den Erfolg zurück.
Wenn die verknüpfte Liste zum Implementieren des Stapels verwendet wird, müssen wir in Schritt 3 Speicherplatz dynamisch zuweisen.
Algorithmus für den PUSH-Betrieb
Ein einfacher Algorithmus für die Push-Operation kann wie folgt abgeleitet werden:
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
Die Implementierung dieses Algorithmus in C ist sehr einfach. Siehe folgenden Code -
Example
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Pop-Betrieb
Der Zugriff auf den Inhalt beim Entfernen vom Stapel wird als Pop-Operation bezeichnet. In einer Array-Implementierung der pop () -Operation wird das Datenelement stattdessen nicht entfernttopwird auf eine niedrigere Position im Stapel dekrementiert, um auf den nächsten Wert zu zeigen. Bei der Implementierung einer verknüpften Liste entfernt pop () jedoch tatsächlich Datenelemente und gibt Speicherplatz frei.
Eine Pop-Operation kann die folgenden Schritte umfassen:
Step 1 - Überprüft, ob der Stapel leer ist.
Step 2 - Wenn der Stapel leer ist, wird ein Fehler ausgegeben und beendet.
Step 3 - Wenn der Stapel nicht leer ist, wird auf das Datenelement zugegriffen, an dem top zeigt.
Step 4 - Verringert den Wert von top um 1.
Step 5 - Gibt den Erfolg zurück.
Algorithmus für die Pop-Operation
Ein einfacher Algorithmus für die Pop-Operation kann wie folgt abgeleitet werden:
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Die Implementierung dieses Algorithmus in C ist wie folgt:
Example
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
Für ein vollständiges Stack-Programm in der Programmiersprache C klicken Sie bitte hier .