Listes pour représenter des piles

Une liste est une excellente façon de représenter une pile. Pour obtenir le sommet de la pile, il suffit d'utiliser la fonction car, pour empiler un élément, on utilise cons et pour dépiler cdr.

Ces opérations sont sans effet de bord. Empiler un objet avec cons implique la création d'une nouvelle pile mais avec un élément de plus.

Parfois, il est souhaitable de modifier une variable contenant une pile. On obtient alors souvent des idiomes comme :

(setf *pile* (cons obj *pile*))
(setf *pile* (cdr *pile*)

pour empiler ou dépiler une pile, ici valeur de la variable *pile*. Les deux macros Common Lisp push et pop capturent ces idiomes :

* (defparameter *pile* '())

*PILE*
* (push 'a *pile*)

(A)
* (push 'b *pile*)

(B A)
* (pop *pile*)

B
* *pile*

(A)
* (pop *pile*)

A
* *pile*

NIL
*

Les deux macros push et pop sont impossibles à écrire sous forme de fonctions, car aucune fonction n'est capable de modifier la valeur d'une variable donnée en argument.

Irene DURAND
2011-10-14