data-structures
Stapel

Intro zum Stapeln

Der Stack ist eine LIFO-Datenstruktur (Last-In, First-Out), dh das letzte (oder "letzte") Element, das dem Stack hinzugefügt wird, ist das erste entfernte Element ("first out").

Betrachten wir das Beispiel von Büchern in einer Box. Es kann immer nur ein Buch hinzugefügt oder aus der Box entfernt werden, und es kann nur von oben hinzugefügt und entfernt werden.

Nun sieht die Box mit den ersten beiden Büchern so aus:

  |--------|
  | book 2 | ◀──── top of box
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

Wenn wir Buch 3 hinzufügen, wird es ganz oben stehen. Der Rest der Bücher, die vor Buch 3 hinzugefügt wurden, wird darunter bleiben:

  |--------|
  | book 3 | ◀──── top of box
  |--------|
  | book 2 |
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

Die Box ist wie ein Stapel und die Bücher sind Datenelemente. Das Hinzufügen eines Buchs zur Box ist die Push-Operation, während ein Buch aus dem oberen Bereich der Box entfernt / abgerufen wird. Wenn Sie die Pop-Operation ausführen, erhalten Sie das Buch 3, und die Box kehrt zu dem Zustand zurück, den wir vor dem Pushen des Buchs 3 hatten stieg aus (LIFO). Um Buch 1 zu erhalten, müssen wir zwei weitere Pops ausführen: einen, um Buch 2 zu entfernen, und den zweiten, um Buch 1 zu erhalten.

Implementierung des Stacks mit einem Array. Dafür benötigen wir einen Index, der auf die oberste Position (tos) zeigt. Jedes Mal, wenn ein Element in den Stack geschoben wird, erhöht sich der Wert der tos um eins, und bei jedem Popup-Vorgang wird der Index, der auf den Stack (tos) zeigt, um eins verringert.

DRÜCKEN:

Vor dem PUSH-Vorgang

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

void push(dataElment item){
    stack[top]=item; //item = i4
    top++;
    
}

Nach der PUSH-Operation Der Stapel verfügt über einen Zeiger auf die Oberseite des Stapels. Wenn der Push-Vorgang aufgerufen wird, wird der Wert oben angezeigt und der Wert wird aktualisiert.

        tos -- Top of the stack
                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |     |
        |-----|-----|-----|-----|

POP: Die Pop-Operation entfernt den Inhalt vom Stapel und aktualisiert den Wert von tos durch Dekrementieren um 1

Vor der Popoperation:

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

dataElment pop(){
    dataElment value = stack[tos--];
    return value;
}

Nach der Popoperation:

                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |
        |-----|-----|-----|-----|
        When a push operation is performed it overwrites i4.
    

Verwenden von Stapeln, um Palindrome zu finden

Ein Palindrom ist ein Wort, das in beide Richtungen gelesen werden kann, wie "Kajak".

In diesem Beispiel wird gezeigt, wie mit Python3 ermittelt wird, ob ein bestimmtes Wort ein Palindrom ist.

Zuerst müssen wir eine Zeichenfolge in einen Stapel verwandeln (wir verwenden Arrays als Stapel).

str = "string"
stk = [c for c in str] #this makes an array: ["s", "t", "r", "i", "n", "g"]
stk.append("s") #adds a letter to the array
stk.pop() #pops the last element

Jetzt müssen wir das Wort umkehren.

def invert(str):
    stk = [c for c in str]
    stk2 = []
    while len(stk) > 0:
        stk2.append(stk.pop())
    #now, let's turn stk2 into a string
    str2 = ""
    for c in stk2:
        str2 += c
    return str2

Jetzt können wir das Wort und die umgekehrte Form vergleichen.

def palindrome(str):
    return str == invert(str)

Stack-Implementierung mit Array und Linked List

Array-Implementierung

#include<stdio.h>

#define MAX 100000                    //Global variables
int top = -1;
int a[MAX];

void push(int x){
    
    if(top == MAX-1){                         // Check whether stack is full
        printf("Stack Overflow\n");
        return;
    }
    
    a[++top] = x;                            // Otherwise increment top and insert x
}

void pop(){
    if(top == -1){                                     // if top = -1, empty stack
        printf("Empty stack\n");
        return;
    }
    top--;        
}

void print(){                         //printing stack values
    
    for(int i=0;i <= top;i++){
        printf("%d ",a[i]);        
    }        
    printf("\n");        
}

void topValue(){                        // Method can print the top value of a stack
    printf("%d",a[top]);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();
    topValue();    
    
}

Linked List-Implementierung

#include<stdio.h>
#include<malloc.h>

 struct node{
    int data;
    node* link;
};
node* top = NULL;

void push(int data){
    
    node* temp = (struct node*)malloc(sizeof(struct node*));
    temp->data = data;
    temp->link = top;
    top = temp;
}

void pop(){
    
    if(top == NULL) return;
    node* temp = top;
    top = top->link;
    free(temp);
}
void print(){
    
    node* t = top;
    while(t != NULL){
        printf("%d ",t->data);
        t=t->link;
    }
    printf("\n");
}

void topValue(){
    printf("%d ",top->data);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();            
    topValue();    
}

Ausgewogene Klammern prüfen

Eine Klammer gilt als eines der folgenden Zeichen: ( , ) , { , } , [ oder ] .

Zwei Halterungen sind als ein passendes Paar sein , wenn die Halterung eine Öffnung (dh ( , [ oder { ) tritt auf der linken Seite von einem Schließbügel (dh ) , ] oder } ) des gleichen Typs. Es gibt drei Arten von übereinstimmenden Klammerpaaren: [] , {} und () .

Ein übereinstimmendes Paar Klammern ist nicht abgeglichen, wenn die von ihm eingeschlossenen Klammern nicht übereinstimmen. Beispielsweise ist {[(])} nicht abgeglichen, da der Inhalt zwischen { und } nicht abgeglichen ist. Das Paar eckige Klammern umschließt eine einzelne, unausgeglichene Öffnungsklammer ( und das Klammerpaar umschließt eine einzelne, unausgeglichene schließende eckige Klammer ] .

Nach dieser Logik wird eine Folge von Klammern als ausgeglichen betrachtet, wenn die folgenden Bedingungen erfüllt sind:

Es enthält keine unübertroffenen Klammern.

Die Untergruppe von Klammern, die innerhalb der Grenzen eines übereinstimmenden Klammerpaares eingeschlossen sind, ist ebenfalls ein übereinstimmendes Klammerpaar.

Algorithmus:

1. Deklarieren Sie einen Stack (zB stack ).
2. Nun die String-Eingabe durchqueren.

• a) Wenn das aktuelle Zeichen eine Startklammer ist (dh ( oder { oder [ )), drücken Sie es zum Stapeln.
• b) Wenn das aktuelle Zeichen eine schließende Klammer ist (dh ) oder } oder ] ), dann vom Stapel springen. Wenn das geknackte Zeichen die übereinstimmende Startklammer ist, sind feine Klammern ansonsten not balanced .
• c) Wenn das aktuelle Zeichen eine schließende Klammer ist (dh ) oder } oder ] ) und der Stapel leer ist, sind die Klammern not balanced .

3. Wenn nach dem vollständigen Durchlauf einige Startklammern im Stapel übrig sind, ist die Zeichenfolge not balanced andernfalls haben wir eine balanced Zeichenfolge.