Wie man einen Stack in C programmiert

Ein Stack ist eine lineare Datenstruktur, eine Sammlung von Elementen desselben Typs.

Einführung

In einem Stack erfolgt das Einfügen und Löschen von Elementen nur an einem Endpunkt. Das Verhalten eines Stacks wird als „Last In, First Out“ (LIFO) beschrieben. Wenn ein Element in den Stack „gepusht“ wird, wird es das erste Element, das wieder „gepopped“ wird. Um auf das älteste eingefügte Element zuzugreifen, müssen alle vorherigen Elemente entfernt werden.

Anwendungen von Stacks

Der Stack wird zur Lösung einiger allgemeiner Probleme verwendet, wie zum Beispiel:

• Türme von Hanoi
• N-Damen-Problem
• Infix-zu-Präfix-Konvertierung

Konzept und Implementierung

In diesem Artikel lernen Sie das Konzept der Stack-Datenstruktur und deren Implementierung mit Arrays in C kennen.

Operationen auf Stacks

Die folgenden grundlegenden Operationen werden von Stacks bereitgestellt:

• push: Fügt ein Element oben im Stack hinzu.
• pop: Entfernt das oberste Element aus dem Stack.
• isEmpty: Prüft, ob der Stack leer ist.
• isFull: Prüft, ob der Stack voll ist.
• top: Zeigt das oberste Element des Stacks an.

Mechanik von Stacks

Zu Beginn wird ein Zeiger (top) gesetzt, um das oberste Element im Stack zu verfolgen. Der Stack wird auf -1 initialisiert.

• Es wird überprüft, ob der Stack leer ist, indem top mit -1 verglichen wird.
• Wenn Elemente in den Stack eingefügt werden, wird die Position von top aktualisiert.
• Wenn Elemente entfernt werden, wird das oberste Element gelöscht, und die Position von top wird aktualisiert.

Implementierung eines Stacks in C

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

Dieses Beispiel implementiert Stacks mit Arrays in C:

 
#include 
#include 

#define SIZE 4

int top = -1, inp_array[SIZE];
void push();
void pop();
void show();

int main()
{
    int choice;

    while (1)
    {
        printf("\nOperationen auf dem Stack ausführen:");
        printf("\n1.Element hinzufügen (Push)\n2.Element entfernen (Pop)\n3.Anzeigen\n4.Beenden");
        printf("\n\nWählen Sie eine Option: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            show();
            break;
        case 4:
            exit(0);

        default:
            printf("\nUngültige Auswahl!!");
        }
    }
}

void push()
{
    int x;

    if (top == SIZE - 1)
    {
        printf("\nÜberlauf!!");
    }
    else
    {
        printf("\nGeben Sie das Element ein, das zum Stack hinzugefügt werden soll: ");
        scanf("%d", &x);
        top = top + 1;
        inp_array[top] = x;
    }
}

void pop()
{
    if (top == -1)
    {
        printf("\nUnterlauf!!");
    }
    else
    {
        printf("\nEntferntes Element: %d", inp_array[top]);
        top = top - 1;
    }
}

void show()
{
    if (top == -1)
    {
        printf("\nUnterlauf!!");
    }
    else
    {
        printf("\nIm Stack vorhandene Elemente: \n");
        for (int i = top; i >= 0; --i)
            printf("%d\n", inp_array[i]);
    }
}

Programmfunktionen

Dieses Programm bietet dem Benutzer vier Optionen:

1. Element hinzufügen (Push)
2. Element entfernen (Pop)
3. Anzeigen
4. Beenden

Das Programm wartet auf die Eingabe des Benutzers.

Ausführungsablauf

• Push: Das Programm führt push() aus. Zuerst wird überprüft, ob top gleich SIZE - 1 ist. Falls ja, zeigt es „Überlauf!!“ an. Andernfalls fordert es den Benutzer auf, das neue Element anzugeben.
• Pop: Das Programm führt pop() aus. Zuerst wird überprüft, ob top gleich -1 ist. Falls ja, zeigt es „Unterlauf!!“ an. Andernfalls entfernt es das oberste Element, und gibt den Stack aus.
• Show: Das Programm führt show() aus. Zuerst überprüft es, ob top gleich -1 ist. Falls ja, zeigt es „Unterlauf!!“ an. Andernfalls gibt es den Stack aus.
• End: Das Programm beendet sich.

Zeitkomplexität von Stack-Operationen

Nur ein Element kann zu einem Zeitpunkt in Stacks verarbeitet werden. Bei der Durchführung von push()– und pop()-Operationen beträgt die Zeitkomplexität O(1).

Fazit: Wie man einen Stack in C programmiert

In diesem Artikel haben Sie das Konzept der Stack-Datenstruktur und deren Implementierung mit Arrays in C kennengelernt. Stacks sind eine wichtige Grundlage für die Lösung komplexerer Probleme und ein wesentliches Werkzeug in der Programmierung. Experimentieren Sie mit dem bereitgestellten Code, um Ihre Kenntnisse weiter zu vertiefen.