3.12 栈 (Stacks)

用 Cons 对象来表示的列表，很自然地我们可以拿来实现下推栈 (pushdown stack)。这太常见了，以致于 Common Lisp 提供了两个宏给堆使用： (push x y) 把 x 放入列表 y 的前端。而 (pop x) 则是将列表 x 的第一个元素移除，并返回这个元素。

两个函数都是由 setf 定义的。如果参数是常数或变量，很简单就可以翻译出对应的函数调用。

表达式

(push obj lst)

等同于

(setf lst (cons obj lst))

而表达式

(pop lst)

等同于

(let ((x (car lst)))
  (setf lst (cdr lst))
  x)

所以，举例来说：

> (setf x '(b))
(B)
> (push 'a x)
(A B)
> x
(A B)
> (setf y x)
(A B)
> (pop x)
(A)
> x
(B)
> y
(A B)

以上，全都遵循上述由 setf 所给出的相等式。图 3.9 展示了这些表达式被求值后的结构。

图 3.9 push 及 pop 的效果

你可以使用 push 来定义一个给列表使用的互动版 reverse 。

(defun our-reverse (lst)
  (let ((acc nil))
    (dolist (elt lst)
      (push elt acc))
    acc))

在这个版本，我们从一个空列表开始，然后把 lst 的每一个元素放入空表里。等我们完成时，lst 最后一个元素会在最前端。

pushnew 宏是 push 的变种，使用了 adjoin 而不是 cons ：

 > (let ((x '(a b)))
     (pushnew 'c x)
     (pushnew 'a x)
     x)
(C A B)

在这里， c 被放入列表，但是 a 没有，因为它已经是列表的一个成员了。