队列 ADT

像栈一样，队列（queue）也是表。然而，使用队列时插入在一端进行而删除则在另一端进行。

队列模型

队列的基本操作是 Enqueue（入队）—— 它是在表的末端（叫做队尾（rear））插入一个元素，还有 Dequeue（出队）—— 它是删除（或返回）在表的开头（叫做队头（front））的元素。

队列的数组实现

如同栈的情形一样，对于队列而言，任何表的实现都是合法的。像栈一样，对于每一种操作，链表实现和数组实现都给出快速的 O(1) 运行时间。队列的链表实现简单明了，无须多言。

现在我们的来讨论队列的数组实现。对于每一个队列数据结构，我们保留一个数组 Queue[] 以及位置 Front 和 Rear，他们代表队列的两端。我们还要记录实际存在于队列中的元素的个数 Size。所有这些信息是作为一个结构的一部分，除队列例程本身外通常不会有例程直接访问它们。

操作应该是很清楚的。为了使一个元素 X 入队，我们让 Size 和 Rear 增 1，然后置 Queue[Rear] = X。若使一个元素出队，我们置返回值为 Queue[Front]，Size 减 1，然后使 Front 增 1。也可能有其他的策略。

现在讨论错误的检测。简单的解决办法是，只要 Front 或 Rear 到达数组的尾端，它就又绕回开头。实现回绕所需要的附加代码是极小的（虽然它可能使得运行时间加倍）。如果 Front 或 Rear 增 1 后超越了数组规定的大小，那么其值就要重置为数组的第一个位置。

关于队列的循环实现，有两件事要警惕。第一，检测队列是否为空是很重要的，因为当队列为空时，一次 Dequeue 操作将不知不觉地返回一个不确定的值。第二，某些程序设计人员使用不同的方法来表示队列的队头和队尾。例如，有些人并不用一个单元来表示队列的大小，因为他们依靠的是基准情形，即当队列为空时 Rear = Front -1。队列的大小是通过比较 Rear 和 Front 隐式算出来的。这是一种非常隐秘的方法，因为存在某些特殊的情形，因此，如果你需要修改用这种方式编写的代码，那么就要特别仔细。如果队列的大小不是结构的一部分，那么若数组的大小为 ASize 个不同的大小值可区分，而 0 是其中的一个。采用任意一种你喜欢的风格，但要确保你的所有例程都是一致的。由于队列的实现方法还有很多种选择，因此如果你不使用 size 字段，那就有必要在代码中插入一些注释。

在 Enqueue 的次数肯定不会大于队列的大小的应用中，使用回绕是没有必要的。像栈一样，除非主调例程肯定队列非空，否则 Dequeue 很少执行，因此对这种操作，只要不是很关键的代码，错误的调用常常被跳过，一般来说这是无可非议的，因为你可能得到的时间节省量是极小的。

总结

表、栈和队列或许在全部计算机科学中是三个基本的数据结构，大量的例子证明了它们广泛的用途。特别地，我们看到栈是如何用来记录过程和函数调用的，以及递归实际上是如何实现的。理解这些过程是非常重要的，不只因为它使得过程语言成为可能，而且还因为知道递归的实现从而消除了围绕其使用的大量谜团。虽然递归非常强大，但是它并不是完全随意的操作；递归的误用和乱用可能导致程序崩溃。