3.3.2 Representing Queues

The mutators set-car! and set-cdr! enable us to use pairs to

construct data structures that cannot be built with cons, car,

and cdr alone. This section shows how to use pairs to represent a data

structure called a queue. Section 3.3.3 will show how to represent data

structures called tables.

变动器 set-car! 和 set-cdr! 使我们能够用序对来构造单靠 cons、car 和 cdr 无法建立的数据结构。本节展示如何用序对来表示一种称为队列 (queue) 的数据结构；第 3.3.3 节将展示如何表示称为表格 (tables) 的数据结构。

A

queue is a sequence in which items are inserted at one end (called

the

rear of the queue) and deleted from the other end (the

队列是一个序列，其中元素从一端（称为队列的尾端 (rear)）插入，并从另一端（即

front). Figure 3.18 shows an initially empty queue in which

the items a and b are inserted. Then a is removed,

c and d are inserted, and b is removed. Because items are

always removed in the order in which they are inserted, a queue is sometimes

called a

FIFO (first in, first out) buffer.

Figure 3.18: Queue operations.

首端 (front)）删除。图 3.18 展示了一个初始为空的队列，依次插入元素 a 和 b，然后删除 a，再插入 c 和 d，最后删除 b 的过程。由于元素总是按照插入的顺序被删除，队列有时也被称为 FIFO（先进先出，first in, first out）缓冲区。图 3.18：队列操作。

In terms of data abstraction, we can regard a queue as defined by the following

set of operations:

从数据抽象的角度来看，我们可以将队列视为由以下一组操作所定义：

a constructor: (make-queue) returns an empty queue (a queue containing

no items).

一个构造函数：(make-queue) 返回一个空队列（不含任何元素的队列）。

two selectors:

两个选择函数：

(empty-queue? ⟨queue⟩)

tests if the queue is empty.

检测队列是否为空。

(front-queue ⟨queue⟩)

returns the object at the front of the queue, signaling an error if the queue

is empty; it does not modify the queue.

返回队列首端的对象；若队列为空则报告错误；该操作不修改队列。

two mutators:

两个变动器：

(insert-queue! ⟨queue⟩ ⟨item⟩)

inserts the item at the rear of the queue and returns the modified queue as its

value.

将元素插入队列尾端，并以修改后的队列作为返回值。

(delete-queue! ⟨queue⟩)

removes the item at the front of the queue and returns the modified queue as

its value, signaling an error if the queue is empty before the deletion.

删除队列首端的元素，并以修改后的队列作为返回值；若删除前队列已为空，则报告错误。

Because a queue is a sequence of items, we could certainly represent it as an

ordinary list; the front of the queue would be the car of the list,

inserting an item in the queue would amount to appending a new element at the

end of the list, and deleting an item from the queue would just be taking the

cdr of the list. However, this representation is inefficient, because

in order to insert an item we must scan the list until we reach the end. Since

the only method we have for scanning a list is by successive cdr

operations, this scanning requires Θ

(

n

) steps for a list of n

items. A simple modification to the list representation overcomes this

disadvantage by allowing the queue operations to be implemented so that they

require Θ

(

1

) steps; that is, so that the number of steps needed is

independent of the length of the queue.

由于队列是一个元素序列，我们当然可以用普通的表来表示它：队列的首端即为表的 car，向队列中插入元素相当于在表的末尾追加一个新元素，而从队列中删除元素则只需取表的 cdr。然而，这种表示方式效率低下，因为插入元素时必须扫描整个表直至末尾。由于我们扫描表的唯一方法是依次执行 cdr 操作，对于含 n 个元素的表，这样的扫描需要 Θ(n) 步。对表的表示方式做一个简单的改动，即可克服这一缺陷，使队列的各操作都只需 Θ(1) 步——也就是说，所需步数与队列的长度无关。

The difficulty with the list representation arises from the need to scan to

find the end of the list. The reason we need to scan is that, although the

standard way of representing a list as a chain of pairs readily provides us

with a pointer to the beginning of the list, it gives us no easily accessible

pointer to the end. The modification that avoids the drawback is to represent

the queue as a list, together with an additional pointer that indicates the

final pair in the list. That way, when we go to insert an item, we can consult

the rear pointer and so avoid scanning the list.

表的表示方式存在困难，根源在于需要扫描才能找到表的末尾。之所以必须扫描，是因为尽管将表表示为序对链的标准方式能够方便地提供指向表头的指针，却没有为我们提供任何易于访问的指向表尾的指针。可以避免这一缺陷的改进是：将队列表示为一个表，同时附加一个额外的指针，用以指明表中的最后一个序对。这样，当需要插入元素时，我们可以直接查询尾指针，从而避免扫描整个表。

A queue is represented, then, as a pair of pointers, front-ptr and

rear-ptr, which indicate, respectively, the first and last pairs in an

ordinary list. Since we would like the queue to be an identifiable object, we

can use cons to combine the two pointers. Thus, the queue itself will

be the cons of the two pointers. Figure 3.19 illustrates this

representation.

Figure 3.19: Implementation of a queue as a list with front and rear pointers.

于是，队列被表示为一对指针——front-ptr 和 rear-ptr——分别指向某个普通表中的第一个和最后一个序对。为了使队列成为一个可识别的对象，我们可以用 cons 将这两个指针组合在一起。这样，队列本身就是这两个指针的 cons。图 3.19 展示了这种表示方式。图 3.19：以带前端和后端指针的表实现队列。

To define the queue operations we use the following procedures, which enable us

to select and to modify the front and rear pointers of a queue:

为了定义队列操作，我们使用以下过程，它们使我们能够选取并修改队列的前端指针和后端指针：

Now we can implement the actual queue operations. We will consider a queue to

be empty if its front pointer is the empty list:

现在我们可以实现实际的队列操作了。若队列的前端指针为空表，则认为该队列为空：

The make-queue constructor returns, as an initially empty queue, a pair

whose car and cdr are both the empty list:

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

To select the item at the front of the queue, we return the car of the

pair indicated by the front pointer:

要选取队列首端的元素，我们返回前端指针所指序对的 car：

To insert an item in a queue, we follow the method whose result is indicated in

Figure 3.20. We first create a new pair whose car is the item to

be inserted and whose cdr is the empty list. If the queue was initially

empty, we set the front and rear pointers of the queue to this new pair.

Otherwise, we modify the final pair in the queue to point to the new pair, and

also set the rear pointer to the new pair.

Figure 3.20: Result of using (insert-queue! q 'd) on the queue of Figure 3.19.

要向队列中插入一个元素，我们按照图 3.20 所示结果的方法进行操作。首先创建一个新的序对，其 car 为待插入的元素，cdr 为空表。若队列初始为空，则将队列的前端指针和后端指针都指向这个新序对；否则，修改队列中最后一个序对，使其指向新序对，同时将后端指针也指向新序对。图 3.20：在图 3.19 的队列上执行 (insert-queue! q 'd) 的结果。

To delete the item at the front of the queue, we merely modify the front

pointer so that it now points at the second item in the queue, which can be

found by following the cdr pointer of the first item (see

Figure 3.21):

要删除队列首端的元素，只需修改前端指针，使其指向队列中的第二个元素，该元素可通过第一个元素的 cdr 指针找到（见图 3.21）：

Figure 3.21: Result of using (delete-queue! q) on the queue of Figure 3.20.

图 3.21：在图 3.20 的队列上执行 (delete-queue! q) 的结果。