data-structures
stack

Inleiding tot stapelen

De stapel is een LIFO-gegevensstructuur (last-in, first-out), dat wil zeggen dat het meest recente element (of "last in") dat aan de stapel wordt toegevoegd, het eerste verwijderde element is ("first out").

Laten we het voorbeeld van boeken in een doos bekijken. Er kan slechts één boek tegelijk worden toegevoegd of verwijderd uit de doos en het kan alleen worden toegevoegd en van boven worden verwijderd.

Nu ziet de doos met de eerste twee boeken er als volgt uit:

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

Als we boek 3 toevoegen, staat dit bovenaan. De rest van de boeken, die vóór boek 3 zijn toegevoegd, blijven eronder:

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

De doos is als een stapel en de boeken zijn gegevenselementen. Een boek toevoegen aan de doos is de push-operatie, terwijl het verwijderen / krijgen van een boek van de bovenkant van de doos de pop-operatie is. Als we de pop-bewerking uitvoeren, krijgen we boek 3 en gaat het vak terug naar de manier waarop het was voordat we boek 3 hebben gepusht. Dit betekent dat het laatste (of meest recente) element dat we erin hebben gestopt, het eerste element was dat we stapte uit (LIFO). Om boek 1 te krijgen, moeten we nog twee pops uitvoeren: een om boek 2 te verwijderen en de tweede om boek 1 te krijgen.

Implementatie van de stapel met behulp van een array. Hiervoor hebben we een index nodig die naar de bovenste locatie (tos) verwijst. Telkens wanneer een element in de stapel wordt geduwd, wordt de tos met één verhoogd en telkens wanneer een pop-bewerking wordt uitgevoerd, wordt de index die naar de bovenkant van de stapel (tos) wijst met één verlaagd.

DUWEN:

Voor de PUSH-bewerking

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

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

Na de PUSH-bewerking heeft de stapel een wijzer naar de bovenkant van de stapel. Telkens wanneer de push-bewerking wordt aangeroepen, wordt de waarde bovenaan geplaatst en wordt de waarde bijgewerkt.

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

POP: de pop-bewerking verwijdert de inhoud van de bovenkant van de stapel en werkt de waarde van tos bij door te verlagen met 1

Voor de pop-operatie:

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

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

Na de pop-operatie:

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

Stapels gebruiken om palindromen te vinden

Een palindroom is een woord dat op beide manieren kan worden gelezen, zoals 'kajak'.

In dit voorbeeld wordt getoond hoe te bepalen of een bepaald woord een palindroom is met Python3.

Eerst moeten we een string in een stapel veranderen (we zullen arrays als stapels gebruiken).

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

Nu moeten we het woord omkeren.

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

Nu kunnen we het woord en de omgekeerde vorm vergelijken.

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

Stapel implementatie met behulp van array en Linked List

Implementatie van de array

#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 implementatie

#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();    
}

Evenwichtige haakjes controleren

Een haakje wordt beschouwd als een van de volgende tekens: ( , ) , { , } , [ of ] .

Twee haakjes worden als een passend paar beschouwd als de openingshaak (dwz ( , [ , of { ) links van een sluithaak (dwz, ) , ] of } ) van exact hetzelfde type voorkomt. Er zijn drie soorten overeenkomende haakjesparen: [] , {} en () .

Een bijpassend paar haakjes is niet gebalanceerd als de set haakjes die het omsluit niet overeenkomen. {[(])} Is bijvoorbeeld niet in balans omdat de inhoud tussen { en } niet in balans is. Het paar vierkante haken omsluit een enkele, ongebalanceerde vierkante haak ( , en het paar haakjes omsluit een enkele, onevenwichtige vierkante haak, ] .

Volgens deze logica zeggen we dat een reeks haakjes als evenwichtig wordt beschouwd als aan de volgende voorwaarden is voldaan:

Het bevat geen ongeëvenaarde beugels.

De subset van haakjes ingesloten binnen de grenzen van een aangepast paar haakjes is ook een aangepast paar haakjes.

Algoritme:

1. Verklaar een stapel (zeg maar stack ).
2. Beweeg nu de string-invoer.

• a) Als het huidige teken een starthaak is (dwz ( of { of [ ), druk het dan op stapel.
• b) Als het huidige teken een haakje is (bijv. ) of } of ] ) spring je uit de stapel. Als het popping-teken de overeenkomende starthaak is, zijn haakjes anders not balanced .
• c) Als het huidige teken een haakje is (bijv. ) of } of ] ) en de stapel leeg is, zijn haakjes not balanced .

3. Als er na volledige doorloop nog een starthaak in de stapel over is, is de string not balanced anders hebben we een balanced string.