[译]数据结构_队列

队列这种ADT中，元素是有序的，主要操作有enqueue入队和dequeue出队。

即Fist-In-First-Out(FIFO)。最下进入队列的元素，会最后出队列。

数组实现队列问题 （一）

若使用紧凑数组来实现队列，a₀表示第一个元素,a_N-1表示最后一个元素，那么在执行dequeue出队操作是会有严重的性能问题。

因为对数组而言，在尾部添加元素是O(1)，但在头部移除元素是O(N)（需要向逐个左移动剩余所有元素）。

数组实现队列问题 （二）

另种数组实现队列的方式，记录两个索引：front记录最左元素索引，当dequeue出队时递增，和back记录最右元素索引，当enqueue入队时递增。

假设数组容量是8，当前如下：[2,4,1,7,-,-,-,-]，其front=0，back=3。

若执行dequeue()，则变为[-,4,1,7,-,-,-,-]，其中front=1，back=3。

若再执行enqueue(5)，则变为[-,4,1,7,5,-,-,-]，其中front=1，back=4。

数组实现队列问题 （三）

多次执行出入队之后，我们得到[-,-,-,-,-,6,2,3]，其front=5,back=7。尽管左端有许多空穴，但我们已经不能再执行入队操作了。

若我们允许front和back移动到M-1时绕回到索引0，这种高效循环数组又可以利用剩余的空间了。

例：

1. enqueue → [8 , -,-,-,-,6,2,3] front=5,back=0

数组实现队列问题 （四）

Yet, this does not solve the main problem of array implementation: The items of the array are stored in contiguous manner in computer memory.

假设，经过若干操作我们得到[8,10,11,12,13,6,2,3]，front=5，back=4。此时无法再执行入队操作。

那么，我们会生成一个更大的数组（扩容），使M=2*8=16，但由于要拷贝旧数组到新数组，其时间复杂度是O(N)。
[6,2,3,8,10,11,12,13,-,-,-,-,-,-,-,-,]，front = 0, and back = 7

链表的实现

在队列中，我们只需要两个参数，一个用作插入（入队），一个用作移除（出队）

插入尾部之后和从头部移除在顺序链表中非常快，是O(1)。我们使用链表中的head/tail来替换front/back，由于链表中的元素不需要连续存储它的大小可以随时增大缩小。

队列的应用

队列能解决很多实际问题。

在宽度优先搜索中有非常重要的应用。