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 .