You can build many structures out of conses. Perhaps the simplest is a
linked list: the car of each cons points to one of the elements of the
list, and the cdr points either to another cons or to nil. You can
create such a linked list with the list fuction:
> (list 4 5 6)
(4 5 6)
Notice that LISP prints linked lists a special way: it omits some of
the periods and parentheses. The rule is: if the cdr of a cons is
nil,
LISP doesn't bother to print the period or the nil; and if the
cdr of
cons A is cons B, then LISP doesn't bother to print the period for cons
A or the parentheses for cons B. So:
> (cons 4 nil)
(4)
> (cons 4 (cons 5 6))
(4 5 . 6)
> (cons 4 (cons 5 (cons 6 nil)))
(4 5 6)
The last example is exactly equivalent to the call (list 4 5 6). Note
that nil now means the list with no elements: the cdr of (a b), a list
with 2 elements, is (b), a list with 1 element; and the cdr of (b), a
list with 1 element, is nil, which therefore must be a list with no
elements.
The car and cdr of nil are defined to be nil.
If you store your list in a variable, you can make it act like a stack:
> (setq a nil)
NIL
> (push 4 a)
(4)
> (push 5 a)
(5 4)
> (pop a)
5
> a
(4)
> (pop a)
4
> (pop a)
NIL
> a
NIL