data-structures
Stack

Introduktion till Stack

Bunten är en LIFO (sist-in, först-ut) datastruktur, dvs det senaste (eller "senast in") -elementet som läggs till i stacken kommer att vara det första elementet som tas bort ("först ut").

Låt oss ta hänsyn till exemplet med böcker i en låda. Endast en bok kan läggas till eller tas bort från rutan åt gången, och den kan bara läggas till och tas bort från toppen.

Nu ser rutan med de två första böckerna ut så här:

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

Om vi lägger till bok 3 kommer den att vara överst. Resten av böckerna, som lades till före bok 3, kommer att förbli under den:

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

Rutan är som en bunt och böckerna är dataelement. Att lägga till en bok i rutan är pushoperationen medan du tar bort / hämtar en bok från toppen av rutan är popoperationen. Om vi utför pop-operationen kommer vi att få bok 3, och rutan kommer att gå tillbaka till den var innan vi tryckte på bok 3. Det betyder att det sista (eller senaste) elementet som vi satte in var det första elementet vi kom ut (LIFO). För att få bok 1 måste vi utföra ytterligare två pop: en för att ta bort bok 2, och den andra för att få bok 1.

Implementering av stacken med hjälp av en matris. För detta behöver vi ett index som pekar till den översta platsen (tos). Varje gång ett element skjuts in i bunten stegs tos av en och närhelst en pop-operation utförs, minskas indexet som pekar toppen av bunten (tos) med en.

SKJUTA PÅ:

Innan PUSH-operationen

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

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

Efter PUSH-operationen Bunten har en pekare till toppen av bunten. Närhelst push-operationen kallas placerar den värdet högst upp och uppdaterar värdet.

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

POP: Pop-operationen tar bort innehållet från toppen av bunten och uppdaterar värdet på tos genom att dekrementera med 1

Innan popoperationen:

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

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

Efter pop-operationen:

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

Använd staplar för att hitta palindromer

En palindrome är ett ord som kan läsas på båda sätten, som "kajak".

Detta exempel visar hur man hittar om ett givet ord är en palindrome med Python3.

Först måste vi förvandla en sträng till en bunt (vi kommer att använda matriser som staplar).

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 måste vi invertera ordet.

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 kan vi jämföra ordet och den inverterade formen.

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

Stapla implementering med hjälp av matris och länkad lista

Arrayimplementering

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

Implementerad länkad lista

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

Kontrollera balanserade pareteser

Ett fäste anses vara något av följande tecken: ( , ) , { , } , [ eller ] .

Två konsoler anses vara ett matchat par om en öppningsfäste (dvs ( , [ , eller { ) förekommer till vänster om en stängningsfäste (dvs ) , ] eller } ) av exakt samma typ. Det finns tre typer av matchade parparentespar: [] , {} och () .

Ett matchande par parentes är inte balanserat om den uppsättning parentes som den bifogas inte matchas. Till exempel är {[(])} inte balanserad eftersom innehållet mellan { och } inte är balanserat. Paret med fyrkantiga konsoler inkluderar en enda, obalanserad öppningsfäste, ( , och paret inom parentes innehåller en enda obalanserad fyrkantig konsol, ] .

Med denna logik säger vi att en sekvens av parentes anses vara balanserad om följande villkor är uppfyllda:

Det innehåller inga oöverträffade konsoler.

Deluppsättningen av konsoler som är inneslutna inom gränserna för ett matchat parparentes är också ett matchat par parentes.

Algoritm:

1. Förklara en bunt (säg stack ).
2. Korsa nu stränginmatningen.

• a) Om det aktuella tecknet är en startfäste (dvs. ( eller { eller [ ), tryck sedan på den för att stapla).
• b) Om det aktuella tecknet är en stängningsfäste (dvs. ) eller } eller ] ), pop från bunten. Om det poppade tecknet är den matchande startkonsolen, är bra annars parentes not balanced .
• c) Om det aktuella tecknet är en stängningsfäste (dvs. ) eller } eller ] ) och bunten är tom är parenteserna not balanced .

3. Efter fullständig genomgång, om det finns någon startkonsol kvar i bunten så är strängen not balanced annars har vi en balanced sträng.