2.2 如何实现队列

【出自XL面试题】

难度系数：★★★☆☆

被考察系数：★★★★☆

题目描述：

实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。

分析与解答：

与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。

方法一：数组实现

下图给出了一种最简单的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置，同时执行rear++，出队列的时候只需要执行front++即可。

实现代码如下：

程序的运行结果为

以上这种实现方法最大的缺点：出队列后数组前半部分的空间不能够充分地利用，解决这个问题的方法为把数组看成一个环状的空间（循环队列）。当数组最后一个位置被占用后，可以从数组首位置开始循环利用，具体实现方法可以参考数据结构的课本。

方法二：链表实现

采用链表实现队列的方法与实现栈的方法类似，分别用两个指针指向队列的首元素与尾元素，如下图所示。用pHead来指向队列的首元素，用pEnd来指向队列的尾元素。

在上图中，刚开始队列中只有元素1、2和3，当新元素4要进队列的时候，只需要上图中（1）和（2）两步，就可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要（3）这一步，改变pHead指针使其指向pHead→next，此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊操作，实现代码如下：

程序的运行结果为

显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多了用来存储结点关系的指针空间。此外，也可以用循环链表来实现队列，这样只需要一个指向链表最后一个元素的指针即可，因为通过指向链表尾元素可以非常容易地找到链表的首结点。