12.3 示例：队列 (Example: Queues)

共享结构并不是一个总让人担心的特性。我们也可以对其加以利用的。这一节展示了怎样用共享结构来表示队列。队列对象是我们可以按照数据的插入顺序逐个检出数据的仓库，这个规则叫做先进先出 (FIFO, first in, first out)。

用列表表示栈 (stack)比较容易，因为栈是从同一端插入和检出。而表示队列要困难些，因为队列的插入和检出是在不同端。为了有效的实现队列，我们需要找到一种办法来指向列表的两个端。

图 12.6 给出了一种可行的策略。它展示怎样表示一个含有 a，b，c 三个元素的队列。一个队列就是一对列表，最后那个 cons 在相同的列表中。这个列表对由被称作头端 (front)和尾端 (back)的两部分组成。如果要从队列中检出一个元素，只需在其头端 pop，要插入一个元素，则创建一个新的 cons ，把尾端的 cdr 设置成指向这个 cons ，然后将尾端指向这个新的 cons 。

图 12.6 一个队列的结构

(defun make-queue () (cons nil nil))
(defun enqueue (obj q)
  (if (null (car q))
      (setf (cdr q) (setf (car q) (list obj)))
      (setf (cdr (cdr q)) (list obj)
            (cdr q) (cdr (cdr q))))
  (car q))
(defun dequeue (q)
  (pop (car q)))

图 12.7 队列实现

图 12.7 中的代码实现了这一策略。其用法如下：

> (setf q1 (make-queue))
(NIL)
> (progn (enqueue 'a q1)
         (enqueue 'b q1)
         (enqueue 'c q1))
(A B C)

现在， q1 的结构就如图 12.6 那样：

> q1
((A B C) C)

从队列中检出一些元素：

> (dequeue q1)
A
> (dequeue q1)
B
> (enqueue 'd q1)
(C D)