Stapel

алгоритм, стек, сортировка

Stack-Konzept

Der Stack ist eine nützliche Datenstruktur beim Programmieren. Es ist wie ein Stapel Teller, die übereinander gestapelt sind.

Überlegen Sie, was Sie mit so einem Haufen Teller machen können:

• Setzen Sie eine neue Platte darauf;
• Bewegen Sie die obere Platte.

Wenn Sie möchten, dass die Platte unten ist, müssen Sie alle oberen Platten entfernen. Diese Anordnung wird Last In First Out oder LIFO (Last In First Out) genannt – das letzte Element, das eingefügt wird, ist das erste Element, das herauskommt.

Stack in Programmierbedingungen

In Bezug auf die Programmierung wird das Platzieren eines Elements auf dem Stapel als "Push" und das Entfernen eines Elements als "Pop" bezeichnet. Das zuletzt hinzugefügte Element wird als oberstes Element des Stapels oder "oben" bezeichnet.

Im Bild sehen Sie, dass Element 2 zuletzt gespeichert wurde, aber zuerst entfernt wird, da es dem LIFO-Prinzip (last in, first out) folgt.

Wir können einen Stack in jeder Programmiersprache wie C, C++, Java, Python oder C# mit fast der gleichen Spezifikation implementieren.

Stack-Spezifikation

Ein Stapel ist ein Objekt, oder genauer gesagt eine abstrakte Datenstruktur (ADT), mit der Sie die folgenden Operationen ausführen können:

• Push: Fügen Sie ein Element oben auf dem Stapel hinzu;
• Pop: Entferne ein Element von der Spitze des Stapels;
• IsEmpty: prüfen, ob der Stack leer ist;
• IsFull: prüfen, ob der Stack voll ist;
• Peek: Holen Sie sich den Wert des obersten Elements, ohne es zu entfernen.

So funktioniert der Stack

Operationen funktionieren wie folgt:

1. Der TOP-Zeiger wird aufgerufen, um das oberste Element auf dem Stapel zu verfolgen.
2. Beim Initialisieren des Stacks setzen wir seinen Wert auf -1, damit wir prüfen können, ob der Stack leer ist, indem wir TOP == -1 vergleichen.
3. Durch Klicken auf ein Element erhöhen wir den Wert von TOP und platzieren das neue Element an der Position, auf die TOP zeigt.
4. Wenn wir ein Element erhalten, geben wir das Element zurück, auf das TOP zeigt, und dekrementieren seinen Wert.
5. Bevor wir ein Element hinzufügen, prüfen wir, ob der Stack voll ist.
6. Bevor wir ein Element entfernen, prüfen wir, ob der Stack leer ist.

Implementieren eines Stacks in einer Programmiersprache

Die gebräuchlichste Implementierung eines Stacks verwendet Arrays, aber Implementierungen mit Listen sind ebenfalls möglich.

Hier ist eine Implementierung mit Arrays in C.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define MAX 10

struct stack
{
    int items[MAX];
    int top;
};
typedef struct stack st;

void createEmptyStack(st *s)
{
    s->top=-1;
}

int isfull(st *s)
{
    if (s->top==MAX-1)
        return 1;
    else
        return 0;
}

int isempty(st *s)
{
    if (s->top==-1)
        return 1;
    else
        return 0;
}

void push(st *s)
{
    int newitem;
    printf("Enter item to be inserted: ");
    scanf("%d",&newitem);
    if (isfull(s))
    {
        printf("STACK FULL");
    }
    else
    {
        s->top++;
        s->items[s->top]=newitem;
    }
}


void pop (st *s)
{
    if (isempty(s))
    {
        printf("\n STACK EMPTY \n");
    }
    else
    {
        printf("Item popped= %d",s->items[s->top]);
        s->top--;
    }
}

void main()
{
    int ch;
    int loop;
    loop=1;
    st *s;

    createEmptyStack(s);

    do
    {
        printf("\n ***STACK OPERATIONS");
        printf("\n 1. PUSH");
        printf("\n 2. POP");
        printf("\n 3. EXIT");
        printf("\n ***************");
        printf("\n Enter your choice: ");
        scanf("%d", &ch);

        switch (ch)
        {
            case 1: 
                push(s);
                break;
            case 2:
                pop(s);
                break;
            case 3:
                printf("THANK YOU");
                loop=0;
                exit(0);
            default:
                printf("Invalid choice");
        }
    } while(loop);

    getch();
}

Verwendung des Stapels

Obwohl der Stack eine einfach zu implementierende Datenstruktur ist, ist er sehr nützlich. Die häufigsten Anwendungen für den Stack sind die folgenden Aufgaben:

• Um ein Wort umzudrehen - legen Sie alle Buchstaben auf einen Stapel und ziehen Sie sie heraus. Aufgrund der Reihenfolge des LIFO-Stapels erhalten Sie die Buchstaben in umgekehrter Reihenfolge.
• In Compilern - Compiler verwenden den Stack, um den Wert von Ausdrücken wie 2 + 4/5 * (7-9) zu berechnen, indem sie den Ausdruck in Präfix- oder Postfixform umwandeln.
• In Browsern - Der Zurück-Button im Browser speichert alle zuvor besuchten URLs im Stack. Jedes Mal, wenn Sie eine neue Seite besuchen, wird diese oben im Stapel hinzugefügt. Wenn Sie auf die Schaltfläche „Zurück“ klicken, wird die aktuelle URL aus dem Stapel entfernt und die vorherige URL geöffnet.