data-structures
Empiler

Introduction à la pile

La pile est une structure de données LIFO (dernier entré, premier sorti), c'est-à-dire que l'élément le plus récent (ou "dernier entré") ajouté à la pile sera le premier élément supprimé ("premier sorti").

Considérons l'exemple des livres dans une boîte. Un seul livre peut être ajouté ou supprimé de la boîte à la fois et il ne peut être ajouté et supprimé que du haut.

Maintenant, la boîte avec les deux premiers livres ressemble à ceci:

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

Si on ajoute le livre 3, ce sera au sommet. Les autres livres, ajoutés avant le livre 3, resteront en dessous:

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

La boîte est comme une pile et les livres sont des éléments de données. L'ajout d'un livre à la boîte est l'opération de poussée pendant que vous retirez / récupérez un livre du haut de la boîte est l'opération pop. Si nous effectuons l'opération pop, nous aurons le livre 3, et la boîte retournera à la manière dont elle était avant que nous ne poussions le livre 3. Cela signifie que le dernier élément (ou le plus récent) que nous avons mis était le premier élément sorti (LIFO). Pour obtenir le livre 1, nous devons effectuer deux nouvelles fenêtres: une pour supprimer le livre 2 et la seconde pour obtenir le livre 1.

Implémentation de la pile en utilisant un tableau. Pour cela, nous avons besoin d'un index pointant vers le haut (tos). Chaque fois qu'un élément est poussé dans la pile, le tos s'incrémente de un et chaque fois qu'une opération pop est effectuée, l'index pointant vers le haut de la pile (tos) est décrémenté de un.

POUSSER:

Avant l'opération PUSH

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

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

Après l'opération PUSH La pile a un pointeur vers le haut de la pile. Chaque fois que l'opération Push est appelée, elle place la valeur en haut et la met à jour.

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

POP: l' opération pop supprime le contenu du haut de la pile et met à jour la valeur de tos en décrémentant de 1

Avant l'opération pop:

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

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

Après l'opération pop:

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

Utiliser des piles pour trouver des palindromes

Un palindrome est un mot qui peut être lu dans les deux sens, comme «kayak».

Cet exemple montre comment trouver si un mot donné est un palindrome utilisant Python3.

Premièrement, nous devons transformer une chaîne en une pile (nous utiliserons des tableaux comme piles).

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

Maintenant, nous devons inverser le mot.

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

Maintenant, nous pouvons comparer le mot et la forme inversée.

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

Implémentation de la pile à l'aide du tableau et de la liste liée

Implémentation du tableau

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

Implémentation de la liste liée

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

Vérification des parenthèses équilibrées

Un crochet est considéré comme l'un des caractères suivants: ( , ) , { , } , [ ou ou ] .

Deux crochets sont considérés comme une paire appariée si un crochet ouvrant (c'est-à-dire ( , [ , ou { ) se trouve à gauche d'un crochet de fermeture (par exemple, ) , ] ou } ) du même type. Il existe trois types de paires de parenthèses appariées: [] , {} et () .

Une paire de parenthèses correspondantes n'est pas équilibrée si le jeu de parenthèses qu'il contient ne correspond pas. Par exemple, {[(])} n'est pas équilibré car les contenus entre { et } ne sont pas équilibrés. La paire de crochets renferme une seule parenthèse d'ouverture non équilibrée ( et la paire de parenthèses renferme une seule parenthèse carrée non équilibrée ] .

Par cette logique, nous disons qu’une séquence de crochets est considérée comme équilibrée si les conditions suivantes sont remplies:

Il ne contient pas de parenthèses inégalées.

Le sous-ensemble de crochets inclus dans les limites d'une paire de crochets appariés est également une paire de crochets appariés.

Algorithme:

1. Déclarez une pile (disons stack ).
2. Maintenant, parcourez l'entrée de chaîne.

• a) Si le caractère actuel est un crochet de départ (c'est-à-dire ( ou { ou [ )), poussez-le pour empiler.
• b) Si le caractère actuel est un crochet de fermeture (c'est-à-dire ) ou } ou ] sortez de la pile. Si le caractère sauté correspond à la parenthèse de départ correspondante, alors les parenthèses not balanced sont not balanced .
• c) Si le caractère actuel est un crochet de fermeture (ie ) ou } ou ] ) et que la pile est vide, les parenthèses not balanced sont not balanced .

3. Après la traversée complète, s'il reste un support de départ dans la pile, la chaîne n'est not balanced sinon nous avons une chaîne balanced .