cours_9.md

title: "Piles et files d'attente"
date: "2022-12-07"
#define MAX_CAPACITY 500
typedef struct _stack {
    int data[MAX_CAPACITY]; // les données
    int top;                // indice du sommet
} stack;
void stack_init(stack *s) {
    s->top = -1;
}
bool stack_is_empty(stack s) {
    return s.top == -1;
}
void stack_push(stack *s, int val) {
    s->top += 1;
    s->data[s->top] = val;
}
int stack_pop(stack *s) {
    s->top -= 1;
    return s->data[s->top+1];
}
int stack_peek(stack *s) {
    return s->data[s->top];
}
#include <assert.h>
void assert(int expression);
#include <assert.h>
void stack_push(stack *s, int val) {
    assert(s->top < MAX_CAPACITY-1);
    s->top += 1;
    s->data[s->top] = val;
}
int stack_pop(stack *s) {
    assert(s->top >= 0);
    s->top -= 1;
    return s->data[s->top+1];
}
int stack_peek(stack *s) {
    assert(s->top >= 0);
    return s->data[s->top];
}
// alloue une zone mémoire de size octets
void *malloc(size_t size);
// change la taille allouée à size octets (contiguïté garantie)
void *realloc(void *ptr, size_t size);
stack_create(); // crée une pile avec une taille par défaut
// vérifie si la pile est pleine et réalloue si besoin
stack_push();
// vérifie si la pile est vide/trop grande
// et réalloue si besoin
stack_pop();
pour i de 0 à N-1
    tant que (tab[i] > que le sommet de G)
        dépiler G dans D
    tant que (tab[i] < que le sommet de D)
        dépiler de D dans G
    empiler tab[i] sur G
dépiler tout D dans G
tab est trié dans G