Une pile est une structure de données linéaire qui suit le principe LIFO (Last In, First Out). Les opérations d’insertion (push) et de suppresion (pop) ne sont autorisées qu’à une seule extrémité, appelée sommet de la pile. L’autre extrémité est fixe et appelée base.

Pile séquentielle

Une pile séquentielle utilise un tableau statique ou dynamique pour stocker ses éléments. Le sommet évolue avec les opérations, tandis que la base reste fixe. Un entier top indique l’indice du sommet actuel. Initialement, top = -1 signifie que la pile est vide.

Opérations fondamentalse

Initialisation

int init_stack(SeqStack *s, int capacity) {
    s->data = malloc(sizeof(DataType) * capacity);
    if (!s->data) return -1;
    s->capacity = capacity;
    s->top = -1;
    return 0;
}

Ajout (push)

int push(SeqStack *s, DataType val) {
    if (is_full(s)) return -1;
    s->data[++s->top] = val;
    return 0;
}

Retrait (pop)

int pop(SeqStack *s, DataType *val) {
    if (is_empty(s)) return -1;
    *val = s->data[s->top--];
    return 0;
}

Lecture du sommet

int peek(SeqStack *s, DataType *val) {
    if (is_empty(s)) return -1;
    *val = s->data[s->top];
    return 0;
}

Vérification de l’état

int is_empty(SeqStack *s) { return s->top == -1; }
int is_full(SeqStack *s)  { return s->top == s->capacity - 1; }

Destruction

void destroy(SeqStack *s) {
    free(s->data);
    s->data = NULL;
    s->top = -1;
}

Applications pratiques

Conversion décimal → binaire

void dec_to_bin(int n) {
    SeqStack s;
    init_stack(&s, 32);
    while (n > 0) {
        push(&s, n % 2);
        n /= 2;
    }
    while (!is_empty(&s)) {
        DataType bit;
        pop(&s, &bit);
        printf("%d", bit);
    }
    destroy(&s);
}

Évaluation d’expressions postfixées

int evaluate_postfix(const char *expr) {
    SeqStack s;
    init_stack(&s, 20);
    for (int i = 0; expr[i]; i++) {
        if (isdigit(expr[i])) {
            push(&s, expr[i] - '0');
        } else {
            DataType a, b;
            pop(&s, &a);
            pop(&s, &b);
            switch (expr[i]) {
                case '+': push(&s, b + a); break;
                case '-': push(&s, b - a); break;
                case '*': push(&s, b * a); break;
                case '/': push(&s, b / a); break;
            }
        }
    }
    DataType result;
    pop(&s, &result);
    destroy(&s);
    return result;
}

Fichiers source

seqstack.h

#ifndef SEQSTACK_H
#define SEQSTACK_H

typedef int DataType;

typedef struct {
    DataType *data;
    int capacity;
    int top;
} SeqStack;

int init_stack(SeqStack *s, int capacity);
int push(SeqStack *s, DataType val);
int pop(SeqStack *s, DataType *val);
int peek(SeqStack *s, DataType *val);
int is_empty(SeqStack *s);
int is_full(SeqStack *s);
void destroy(SeqStack *s);
void dec_to_bin(int n);
int evaluate_postfix(const char *expr);

#endif

main.c (extrait)

#include <stdio.h>
#include <stdlib.h>
#include "seqstack.h"

int main() {
    SeqStack stack;
    init_stack(&stack, 10);

    // Exemple : conversion
    printf("Binaire de 13 : ");
    dec_to_bin(13);
    printf("\n");

    // Exemple : expression postfixée "56+"
    printf("Résultat de \"56+\" : %d\n", evaluate_postfix("56+"));

    destroy(&stack);
    return 0;
}

La pile séquentielle est efifcace en temps constant pour les opérations principales, mais sa taille est limitée par la capacité initiale. Elle illustre parfaitement l’utilisation des structures linéaires dans des algorithmes récursifs, les analyseurs syntaxiques ou les conversions numériques.