1.3 队列

队列是一种先进先出的数据结构（First-In-First-Out，FIFO），就像大家排队买票一样，先来的先买，没有特殊窗口，也没有VIP通道，所有人都一样。队列通常使用链表和数组来实现，并且队列只允许在尾部（tail）进行插入操作，在头部（head）进行删除操作，如图1-14所示。

1. 队列的实现方式

队列常见有两种实现方式，一种是使用链表，另一种是使用数组。使用单向链表实现队列不会出现溢出的问题，队列长度也没有限制，但删除的时间复杂度较高，当然也可以使用双向链表。使用两个指针，一个指向队列的头，一个指向队列的尾，删除的时候只能删除头（head），添加的时候只能在尾部（tail）添加，如图1-15所示。

2. 队列的链表实现

先来看一下队列的链表实现，其实它和我们前面讲的双向链表一样，唯一的区别就是不能在队列的中间进行添加和删除操作，并且在队列的两头只能一个添加一个删除。先来看一下队列的节点类。

来看一下使用链表实现队列的完整代码。

3. 队列的数组实现

除了使用链表实现队列以外，还可以使用数组来实现。使用链表是没有长度限制的，但使用数组需要给一个固定的大小，如果队列满了还会涉及队列的扩容，这里让tail指向下一个可以存放数据的位置，如图1-16所示。

使用数组实现队列的时候有一个很明显的缺点就是数组不能被重复使用。如图1-16所示，如果一个元素不停地加入队列，然后不停地从队列中移除，会导致tail和head越来越大，最后队列中无法再加入数据了，实际上由于删除之后，队列前面部分有些是空的，这就造成了空间的极大浪费。

4. 循环队列

使用数组实现队列的时候可能会造成空间的浪费，那么有没有什么方式可以优化呢？实际上是有的。它就是循环队列，我们只需要把数组看作一个首尾相连的环即可。在循环队列中，当存储空间的最后一个位置已被使用，在往队列添加数据时，只需要找到存储空间的第一个空闲位置，然后将数据添加进去，让它的下一个位置作为队尾，如图1-17所示。

5. 优先队列和双端队列

除了上面介绍的队列以外，大家可能还听说过优先队列、双端队列，其实这两个都不属于队列，虽然它们的名字中含有队列，但它们不具有队列的特性——先进先出。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先队列一般使用堆来实现，这个会在1.7节堆讲到。而双端队列和这里讲的队列类似，只不过双端队列两头都可以进行元素的添加和删除，它是一种同时具有队列和栈的性质的数据结构，如图1-18所示。