队列的表示

讲解如何用可变列表高效地实现队列这一 FIFO 数据结构，包括前后指针与增删操作的完整代码。

队列数据结构

借助 set-car! 和 set-cdr!，我们可以实现一种此前无法高效构造的数据结构：队列（queue）。队列是一种序列，元素从一端（称为队尾，rear）插入，从另一端（队首，front）删除。由于元素总是按插入的顺序被移除，队列有时也称为 FIFO（先进先出，first in, first out）结构。

队列如何工作

假设我们有这样几个函数：make-queue 返回一个新队列，insert-queue! 向队列添加一个新元素，delete-queue! 从队列中删除一个元素（我们马上就会实现它们）。来看一看队列的运作机制。

操作	操作后的队列
`(define q (make-queue))`	空队列
`(insert-queue! q 'a)`	`a`
`(insert-queue! q 'b)`	`a b`
`(delete-queue! q)`	`b`
`(insert-queue! q 'c)`	`b c`
`(insert-queue! q 'd)`	`b c d`
`(delete-queue! q)`	`c d`

从数据抽象的角度看，队列可以由下面这组操作来定义：

一个构造函数：(make-queue) 返回一个空队列（不含任何元素的队列）。
两个选择函数：
- (empty-queue? <queue>) 判断队列是否为空。
- (front-queue <queue>) 返回队首的元素，队列为空时报错。它不会修改队列。
两个变动器：
- (insert-queue! <queue> <item>) 把元素插入队尾，返回修改后的队列。
- (delete-queue! <queue>) 删除队首的元素，返回修改后的队列；若删除前队列为空则报错。

用列表表示队列

队列是元素组成的序列，所以理论上可以用普通列表来表示：队首对应列表的 car，插入新元素相当于在末尾追加一个新序对，删除元素就是取 cdr。为什么我们不这么做？问题出在运行时间上。要在列表尾部添加一个元素，必须沿着 cdr 一路走到底。如果列表很长，找到最后一个序对会花很长时间，这部分开销是 $\Theta(n)$ ，其中 $n$ 是列表的长度。

列表让我们能在常数时间内访问第一个元素，但找最后一个序对却很慢。解决办法是：保存并维护一个指向最后一个序对的指针。

看上面的队列，我们保存了两个指针：一个指向列表的开头，一个指向末尾。如果往队列里加入一个新元素 'd'，结构会变成这样：

当我们要找 q 的最后一个序对时，顺着 (cdr q) 指针走即可。

实现

要定义队列操作，先用下面几个过程选取和修改队列的前后指针：

(define (front-ptr queue)
    (car queue))
(define (rear-ptr queue)
    (cdr queue))
(define (set-front-ptr! queue item)
    (set-car! queue item))
(define (set-rear-ptr! queue item)
    (set-cdr! queue item))

现在可以实现真正的队列操作了。当前指针指向空列表时，我们认为队列为空：

(define (empty-queue? queue)
    (null? (front-ptr queue)))

构造函数 make-queue 返回一个初始为空的队列——一个 car 和 cdr 都为空列表的序对：

(define (make-queue)
    (cons '() '()))

要选取队首元素，就返回前指针所指序对的 car：

(define (front-queue queue)
    (if (empty-queue? queue)
        (error "FRONT called with an empty queue" queue)
        (car (front-ptr queue))))

入队

按照前面概述的通用算法：

用 cons 构造一个装有新元素的新序对；
若队列为空，把它的前指针和后指针都指向这个新序对；
若队列非空，找到最后一个序对，把它的 cdr 改成新序对，并更新后指针。

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else
           (set-cdr! (rear-ptr queue) new-pair)
           (set-rear-ptr! queue new-pair)
           queue))))

出队

出队时，只需把前指针改成指向下一个序对：

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        (else
         (set-front-ptr! queue (cdr (front-ptr queue)))
         queue)))

从上面的队列出发执行一次删除，只有前指针的指向发生变化：

要点总结

借助 set-car! 和 set-cdr!，我们能把队列这种新数据结构实现得远比单靠 cons、car、cdr 构造的方案高效。