data-structures
Stos

Wprowadzenie do stosu

Stos jest strukturą danych LIFO (ostatnie wejście, pierwsze wyjście), tzn. Najnowszy (lub „ostatni”) dodany do stosu będzie pierwszym usuniętym elementem („pierwszy”).

Rozważmy przykład książek w pudełku. Jednorazowo można dodawać lub usuwać z pudełka tylko jedną książkę i można ją dodawać i usuwać tylko z góry.

Teraz pudełko z dwiema pierwszymi książkami wygląda następująco:

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

Jeśli dodamy książkę 3, będzie ona na górze. Reszta książek, które zostały dodane przed książką 3, pozostanie poniżej:

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

Pudełko jest jak stos, a książki są elementami danych. Dodanie książki do skrzynki to operacja wypychania, podczas gdy usuwanie / pobieranie książki z górnej części skrzynki to operacja pop. Jeśli wykonamy operację pop, otrzymamy książkę 3, a pudełko wróci do poprzedniego stanu, zanim wypchnęliśmy książkę 3. Oznacza to, że ostatni (lub najnowszy) element, który wprowadziliśmy, był pierwszym elementem, który wyszedł (LIFO). Aby zdobyć książkę 1, musimy wykonać dwa kolejne kliknięcia: jeden, aby usunąć książkę 2, a drugi, aby uzyskać książkę 1.

Implementacja stosu za pomocą tablicy. W tym celu potrzebujemy indeksu wskazującego najwyższą lokalizację (tos). Za każdym razem, gdy element jest wpychany do stosu, tos zwiększa się o jeden i za każdym razem, gdy wykonywana jest operacja pop, indeks wskazujący górę stosu (tos) jest zmniejszany o jeden.

PCHAĆ:

Przed operacją PUSH

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

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

Po operacji PUSH Stos ma wskaźnik na górze stosu. Za każdym razem, gdy wywoływana jest operacja wypychania, umieszcza wartość na górze i aktualizuje ją.

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

POP: Operacja pop usuwa zawartość z góry stosu i aktualizuje wartość tos, zmniejszając o 1

Przed operacją pop:

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

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

Po operacji pop:

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

Używanie stosów do znajdowania palindromów

Palindrom to słowo, które można odczytać na dwa sposoby, np. „Kajak”.

Ten przykład pokaże, jak sprawdzić, czy dane słowo jest palindromem przy użyciu Python3.

Najpierw musimy przekształcić ciąg w stos (użyjemy tablic jako stosów).

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

Teraz musimy odwrócić słowo.

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

Teraz możemy porównać słowo i odwróconą formę.

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

Implementacja stosu przy użyciu tablicy i listy połączonej

Implementacja macierzy

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

Implementacja listy połączonej

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

Sprawdzanie zrównoważonych nawiasów

Za nawias uznaje się jeden z następujących znaków: ( , ) , { , } , [ lub ] .

Dwa nawiasy są uważane za dopasowaną parę, jeśli nawias otwierający (tj. ( , [ Lub { ) występuje po lewej stronie nawiasu zamykającego (tj. ) , ] Lub } ) tego samego typu. Istnieją trzy typy dopasowanych par nawiasów: [] , {} i () .

Pasująca para nawiasów nie jest zrównoważona, jeśli zestaw nawiasów w niej zawartych nie jest dopasowany. Na przykład {[(])} nie jest zrównoważony, ponieważ zawartość pomiędzy { a } nie jest zrównoważona. Para kwadratowych nawiasów zawiera pojedynczy, niezrównoważony nawias otwierający ( , a para w nawiasach zawiera pojedynczy, niezrównoważony zamykający nawias kwadratowy, ] .

Zgodnie z tą logiką mówimy, że sekwencja nawiasów jest uważana za zrównoważoną, jeśli spełnione są następujące warunki:

Nie zawiera niepasujących nawiasów klamrowych.

Podzbiór nawiasów zamknięty w ramach dopasowanej pary nawiasów jest również dopasowaną parą nawiasów.

Algorytm:

1. Zadeklaruj stos (powiedz stack ).
2. Teraz przejdź przez ciąg znaków.

• a) Jeśli bieżącym znakiem jest nawias początkowy (tj. ( lub { lub [ ), a następnie pchnij go na stos.
• b) Jeśli bieżącym znakiem jest nawias zamykający (tj. ) lub } lub ] ), to wyskakuj ze stosu. Jeśli wyskakujący znak jest pasującym nawiasem początkowym, to w przeciwnym razie nawiasy not balanced są not balanced .
• c) Jeśli bieżącym znakiem jest nawias zamykający (tj. ) lub } lub ] ), a stos jest pusty, wówczas nawiasy not balanced są not balanced .

3. Po całkowitym przejściu, jeśli w stosie pozostało trochę wspornika początkowego, łańcuch not balanced jest not balanced , w przeciwnym razie mamy łańcuch balanced .