data-structures
Pila

Introduzione allo stack

Lo stack è una struttura di dati LIFO (last-in, first-out), ovvero l'elemento più recente (o "ultimo arrivato") aggiunto allo stack sarà il primo elemento rimosso ("first out").

Prendiamo in considerazione l'esempio di libri in una scatola. È possibile aggiungere o rimuovere un solo libro alla volta, e può essere aggiunto e rimosso solo dall'alto.

Ora, la scatola con i primi due libri ha questo aspetto:

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

Se aggiungiamo il libro 3, sarà in cima. Il resto dei libri, che sono stati aggiunti prima del libro 3, rimarranno al di sotto di esso:

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

La scatola è come una pila e i libri sono elementi di dati. L'aggiunta di un libro alla scatola è l'operazione push mentre l'estrazione / acquisizione di un libro dalla parte superiore della scatola è l'operazione pop. Se eseguiremo l'operazione pop, otterremo il libro 3, e la scatola tornerà al modo in cui era prima che avessimo spinto il libro 3. Ciò significa che l'ultimo (o più recente) elemento che abbiamo inserito è stato il primo elemento che abbiamo uscito (LIFO). Per ottenere il libro 1, dobbiamo eseguire altri due pop: uno per rimuovere il libro 2 e il secondo per ottenere il libro 1.

Implementazione dello stack utilizzando un array. Per questo, abbiamo bisogno di un indice che punta alla posizione in alto (ts). Ogni volta che un elemento viene inserito nello stack, l'importo di incrementi di uno e ogni volta che viene eseguita un'operazione di pop, l'indice che punta in cima allo stack (tos) viene decrementato di uno.

SPINGERE:

Prima dell'operazione PUSH

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

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

Dopo l'operazione PUSH Lo stack ha un puntatore in cima alla pila. Ogni volta che viene chiamata l'operazione push, colloca il valore nella parte superiore e lo aggiorna.

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

POP: L'operazione pop rimuove il contenuto dalla cima dello stack e aggiorna il valore di tos decrementando di 1

Prima dell'operazione pop:

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

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

Dopo l'operazione pop:

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

Usare pile per trovare palindromi

Un palindromo è una parola che può essere letta in entrambi i modi, come "kayak".

Questo esempio mostrerà come trovare se una determinata parola è un palindromo usando Python3.

Per prima cosa, dobbiamo trasformare una stringa in una pila (useremo gli array come stack).

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

Ora, dobbiamo invertire la parola.

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

Ora possiamo confrontare la parola e la forma invertita.

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

Implementazione dello stack utilizzando la matrice e l'elenco collegato

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

Implementazione della lista collegata

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

Controllo delle parentesi equilibrate

Una parentesi è considerata come uno dei seguenti caratteri: ( , ) , { , } , [ , o ] .

Due parentesi sono considerate come una coppia abbinata se la parentesi aperta (cioè, ( , [ , o { ) si verifica a sinistra di una parentesi chiusa (cioè, ) , ] o } ) dello stesso identico tipo. Esistono tre tipi di coppie di parentesi corrispondenti: [] , {} e () .

Una coppia di parentesi corrispondente non è bilanciata se il set di parentesi che racchiude non è abbinato. Ad esempio, {[(])} non è bilanciato perché i contenuti tra { e } non sono bilanciati. La coppia di parentesi quadre racchiude una singola staffa di apertura sbilanciata, ( , e la coppia di parentesi racchiude una singola parentesi quadra chiusa squilibrata, ] .

Con questa logica, diciamo che una sequenza di parentesi è considerata equilibrata se sono soddisfatte le seguenti condizioni:

Non contiene parentesi non abbinate.

Il sottoinsieme di parentesi racchiuso tra i confini di una coppia di parentesi abbinata è anche una coppia di parentesi abbinata.

Algoritmo:

1. Dichiarare uno stack (ad esempio stack ).
2. Ora attraversa la stringa di input.

• a) Se il personaggio corrente è una parentesi iniziale (es. ( o { o [ ), quindi spingerlo per impilarlo.
• b) Se il personaggio corrente è una parentesi chiusa (cioè ) o } o ] ), quindi pop dalla pila. Se il carattere scoppiato è la parentesi iniziale corrispondente, allora le altre parentesi not balanced sono not balanced .
• c) Se il carattere corrente è una parentesi chiusa (cioè ) o } o ] ) e lo stack è vuoto, le parentesi not balanced sono not balanced .

3. Dopo aver completato il traversal, se c'è una parentesi di partenza rimasta in pila, allora la stringa not balanced è not balanced altrimenti abbiamo una stringa balanced .