Wie implementiert man einen Stack in der C-Programmierung?

Einführung

Ein Stack ist eine lineare Datenstruktur, eine Sammlung von Elementen desselben Typs. In einem Stack erfolgen das Einfügen und Entfernen von Elementen nur an einem Ende. Das Verhalten eines Stacks wird als “Last In, First Out” (LIFO) beschrieben. Wenn ein Element auf den Stack “gepusht” wird, ist es das erste Element, das vom Stack “gepoppt” wird. Um das älteste eingefügte Element zu erreichen, müssen alle vorherigen Elemente vom Stack entfernt werden.

In diesem Artikel lernen Sie das Konzept der Stack-Datenstruktur und ihre Implementierung mithilfe von Arrays in C kennen.

An Stacks durchgeführte Operationen

Nachfolgend sind die grundlegenden Operationen von Stacks aufgeführt.

• push: Fügt ein Element oben auf den Stapel hinzu.
• pop: Entfernt das oberste Element vom Stapel.
• isEmpty: Prüft, ob der Stack leer ist.
• isFull: Prüft, ob der Stack voll ist oder nicht.
• top: Zeigt das oberste Element des Stapels an.

Die zugrundeliegenden Mechanismen von Stacks

Zunächst wird ein Zeiger (nach oben) gesetzt, um das oberste Element im Stapel zu verfolgen. Der Stapel wird mit -1 initialisiert.

Anschließend wird überprüft, ob der Stack leer ist, indem das oberste Element mit -1 verglichen wird.

Beim Hinzufügen von Elementen zum Stapel wird die oberste Position aktualisiert.

Sobald Elemente entfernt oder gelöscht werden, wird das oberste Element entfernt und die oberste Position aktualisiert.

Stack-Implementierung in C

STACKS können mithilfe von Strukturen, Zeigern, Arrays oder verketteten Listen dargestellt werden.

Dieses Beispiel implementiert Stacks mithilfe von Arrays in C:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
int top = -1, inp_array[SIZE];
void push();
void pop();
void show();
int main()
{
int choice;
while (1)
{
printf("\nPerform operations on the stack:");
printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
printf("\n\nEnter the choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("\nInvalid choice!!");
}
}
}
void push()
{
int x;
if (top == SIZE - 1)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter the element to be added onto the stack: ");
scanf("%d", &x);
top = top + 1;
inp_array[top] = x;
}
}
void pop()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d", inp_array[top]);
top = top - 1;
}
}
void show()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nElements present in the stack: \n");
for (int i = top; i >= 0; --i)
printf("%d\n", inp_array[i]);
}
}

Dieses Programm bietet dem Benutzer vier Optionen:

• Ein Element verschieben
• Ein Element platzen lassen
• Zeigen
• Ende

Wartet darauf, dass der Benutzer eine Zahl eingibt.

• Wählt der Benutzer 1 aus, führt das Programm eine `push()`-Operation durch. Zuerst wird geprüft, ob `top` gleich `SIZE - 1` ist. Trifft dies zu, wird “Überlauf!!” angezeigt. Andernfalls wird der Benutzer aufgefordert, ein neues Element zum Hinzufügen zum Stapel anzugeben.
• Wählt der Benutzer 2 aus, führt das Programm einen `pop()`-Aufruf durch. Zuerst wird geprüft, ob `top` gleich -1 ist. Trifft dies zu, wird “Unterlauf!!” angezeigt. Andernfalls wird das oberste Element entfernt und der resultierende Stack ausgegeben.
• Wählt der Benutzer 3 aus, führt das Programm eine `show()`-Funktion aus. Zuerst wird geprüft, ob `top` gleich -1 ist. Trifft dies zu, wird “Unterlauf!!” angezeigt. Andernfalls gibt das Programm den resultierenden Stack aus.
• Wählt der Benutzer die 4, wird das Programm beendet.

Führe diesen Code aus, um die Zahl “10” auf den Stack zu pushen:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 1
Enter the element to be inserted onto the stack: 10

Anschließend werden die Elemente in Stack() angezeigt:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Elements present in the stack: 
10

Dann pop():

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 2

Der Stack ist nun leer. Versuche Pop() erneut:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Underflow!! Your code... */

Experimentieren Sie weiter mit diesem Programm, um zu verstehen, wie ein Stack funktioniert.

Zeitkomplexität von Stapeloperationen

In Stacks kann immer nur auf ein Element gleichzeitig zugegriffen werden.

Die Ausführung von push()- und pop()-Operationen auf dem Stack benötigt O(1) Zeit.

Ergebnis

In diesem Artikel haben Sie das Konzept der Stack-Datenstruktur und ihre Implementierung mithilfe von Arrays in C kennengelernt.