cours_11.md

title: "Applications des piles, listes chaînées et files d'attente"
date: "2024-12-09"
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


2 + 3 = 2 3 +,
2 * (3 + 2) - 4 = 6.
2 3 2 + * 4 - = 6.
2 3 4 * * 2 + = (2 * (3 * 4)) + 2.
^   : priorité 3
* / : priorité 2
+ - : priorité 1
( ) : priorité 0 // pas un opérateur mais bon
Infixe              Postfixe            Pile    Priorité
((A*B)/D-F)/(G+H)   Vide                Vide    Néant
 (A*B)/D-F)/(G+H)   Vide                (       0
  A*B)/D-F)/(G+H)   Vide                ((      0
   *B)/D-F)/(G+H)   A                   ((      0
    B)/D-F)/(G+H)   A                   ((*     2
     )/D-F)/(G+H)   AB                  ((*     2
      /D-F)/(G+H)   AB*                 (       0
       D-F)/(G+H)   AB*                 (/      2
        -F)/(G+H)   AB*D                (/      2
         F)/(G+H)   AB*D/               (-      1
          )/(G+H)   AB*D/F              (-      1
           /(G+H)   AB*D/F-             Vide    Néant
Infixe              Postfixe            Pile    Priorité
((A*B)/D-F)/(G+H)   Vide                Vide    Néant
--------------------------------------------------------
           /(G+H)   AB*D/F-             Vide    Néant
            (G+H)   AB*D/F-             /       2
             G+H)   AB*D/F-             /(      0
              +H)   AB*D/F-G            /(      0
               H)   AB*D/F-G            /(+     1
                )   AB*D/F-GH           /(+     1
             Vide   AB*D/F-GH+          /       2
             Vide   AB*D/F-GH+/         Vide    Néant
char *infix_to_postfix(char* infix) { // init and alloc stack and postfix
    for (size_t i = 0; i < strlen(infix); ++i) {
        if (is_operand(infix[i])) {
            // we just add operands in the new postfix string
        } else if (infix[i] == '(') {
            // we push opening parenthesis into the stack
        } else if (infix[i] == ')') {
            // we pop everything into the postfix
        } else if (is_operator(infix[i])) {
            // this is an operator. We add it to the postfix based
            // on the priority of what is already in the stack and push it
        }
    }
    // pop all the operators from the s at the end of postfix
    // and end the postfix with `\0`
    return postfix;
}
2 3 4 + * 5 - = ?
Caractère lu        Pile opérandes
    2               2
    3               2, 3
    4               2, 3, 4
    +               2, (3 + 4)
    *               2 * 7
    5               14, 5
    -               14 - 5 = 9
double evaluate(char *postfix) { // init stack
    for (size_t i = 0; i < strlen(postfix); ++i) {
        if (is_operand(postfix[i])) {
            stack_push(&s, postfix[i]);
        } else if (is_operator(postfix[i])) {
            double rhs = stack_pop(&s);
            double lhs = stack_pop(&s);
            stack_push(&s, op(postfix[i], lhs, rhs));
        }
    }
    return stack_pop(&s);
}
typedef struct _element {
    int data;
    struct _element *next;
} element;
typedef element* stack;
void stack_create(stack *s); // *s = NULL;
void stack_destroy(stack *s);
void stack_push(stack *s, int val);
void stack_pop(stack *s, int *val);
void stack_peek(stack s, int *val);
bool stack_is_empty(stack s); // reutrn NULL == stack;


void stack_push(stack *s, int val) {
    element *elem = malloc(sizeof(*elem));
    elem->data = val;
    elem->next = *s;
    *s = elem;
}


void stack_peek(stack s, int *val) {
    *val = s->data;
}


void stack_pop(stack *s, int *val) {
    stack_peek(*s, val);
    element *tmp = *s;
    *s = (*s)->next;
    free(tmp);
}


void stack_destroy(stack *s) {
    while (!stack_is_empty(*s)) {
        int val;
        stack_pop(s, &val);
    }
}
typedef struct _element {  // Elément de liste
   int data;
   struct _element* next;
} element;
typedef struct _queue {    // File d'attente:
   element* head;  //    tête de file d'attente
   element* tail;  //    queue de file d'attente
} queue;
void queue_init(queue *fa); // head = tail = NULL
bool queue_is_empty(queue fa); // fa.head == fa.tail == NULL
int queue_tail(queue fa); // return fa.tail->data
int queue_head(queue fa); // return fa.head->data
void queue_enqueue(queue *fa, int val);
// adds an element before the tail
int queue_dequeue(queue *fa);
// removes the head and returns stored value
void queue_destroy(queue *fa);
// dequeues everything into oblivion
void queue_enqueue(queue *fa, int val) {
    element* elmt = malloc(sizeof(*elmt));
    elmt->data = val;
    elmt->next = NULL;
    if (queue_is_empty(*fa)) {
        fa->head = elmt;
        fa->tail = elmt;
    } else {
        fa->tail->next = elmt;
        fa->tail = elmt;
    }
}
int queue_dequeue(queue *fa) {
    element* elmt = fa->head;
    int val = elmt->data;
    fa->head = fa->head->next;
    free(elmt);
    if (NULL == fa->head) {
        fa->tail = NULL;
    }
    return val;
}
typedef struct _queue {
    int *data;
    int tail, capacity;
} queue;


typedef struct _queue {
    int *data;
    int head, tail, capacity;
} queue;
void queue_enqueue(queue *fa, int val) {
    if ((fa->head == 0 && fa->tail == fa->capacity-1) ||
            (fa->tail == (fa->head-1) % (fa->capacity-1))) {
        return; // queue is full
    }
    if (fa->head == -1) { // queue was empty
        fa->head = fa->tail = 0;
        fa->data[fa->tail] = val;
    } else if (fa->tail == fa->capacity-1 && fa->head != 0) {
        // the tail reached the end of the array
        fa->tail = 0;
        fa->data[fa->tail] = val;
    } else {
        // nothing particular
        fa->tail += 1;
        fa->data[fa->tail] = val;
    }
}
void queue_dequeue(queue *fa, int *val) {
    if (queue_is_empty(*fa)) {
        return; // queue is empty
    }
    *val = fa->data[fa->head];
    if (fa->head == fa->tail) { // that was the last element
        fa->head = fa->tail = -1;
    } else if (fa->head == fa->capacity-1) {
        fa->head = 0;
    } else {
        fa->head += 1;
    }
}


typedef struct _element { // chaque élément
    int data;
    struct _element *next;
} element;
typedef element* sorted_list; // la liste
// insertion de val
sorted_list sorted_list_push(sorted_list list, int val);
// la liste est-elle vide?
bool is_empty(sorted_list list); // list == NULL
// extraction de val (il disparaît)
sorted_list sorted_list_extract(sorted_list list, int val);
 // rechercher un élément et le retourner
element* sorted_list_search(sorted_list list, int val);
sorted_list sorted_list_push(sorted_list list, int val) {
    if (sorted_list_is_empty(list)) {
        list = malloc(sizeof(*list));
        list->data = val;
        list->next = NULL;
        return list;
    }
}
sorted_list sorted_list_push(sorted_list list, int val) {
    if (list->data >= val) {
        element *tmp = malloc(sizeof(*tmp));
        tmp->data = val;
        tmp->next = list;
        list = tmp;
        return list;
    }
}
sorted_list sorted_list_push(sorted_list list, int val) {
    element *tmp = malloc(sizeof(*tmp));
    tmp->data = val;
    element *crt = list;
    while (NULL != crt->next && val > crt->next->data) {
        crt = crt->next;
    }
    tmp->next = crt->next;
    crt->next = tmp;
    return list;
}