![Java程序员面试算法宝典](https://wfqqreader-1252317822.image.myqcloud.com/cover/248/26268248/b_26268248.jpg)
2.2 如何实现队列
【出自XL面试题】
难度系数:★★★☆☆
被考察系数:★★★★☆
题目描述:
实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。
分析与解答:
与实现栈的方法类似,队列的实现也有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
方法一:数组实现
下图给出了一种最简单的实现方式,用front来记录队列首元素的位置,用rear来记录队列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置,同时执行rear++,出队列的时候只需要执行front++即可。
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/71_01.jpg?sign=1734456046-sIEJFHQ5EFxGVIv56V4qJTgJKWXX8sLX-0-030c7388bed7d9e250dceff873747850)
实现代码如下:
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/71_02.jpg?sign=1734456046-eNqOVA7Efnf6Yqu4VB1FhjnNvsERl7U2-0-64814768c53cc1671f3192d230d2f8a1)
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/72_01.jpg?sign=1734456046-TT2INfSaOvrqVONVJKcoBlvFt1NHX4BW-0-25e4a7b073250aa63ad7da7211a35189)
程序的运行结果为
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/72_02.jpg?sign=1734456046-vxQCW7UKXiXAoTy6AaSTHhGc2lxdhigj-0-3104b18d535c4e6363593221298e2fd7)
以上这种实现方法最大的缺点:出队列后数组前半部分的空间不能够充分地利用,解决这个问题的方法为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后,可以从数组首位置开始循环利用,具体实现方法可以参考数据结构的课本。
方法二:链表实现
采用链表实现队列的方法与实现栈的方法类似,分别用两个指针指向队列的首元素与尾元素,如下图所示。用pHead来指向队列的首元素,用pEnd来指向队列的尾元素。
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/73_01.jpg?sign=1734456046-q43QbsJYEMgbJiyzC2e6VhRDVk9BpF21-0-3a04e3eafa879467f44430bd9e9cfdb8)
在上图中,刚开始队列中只有元素1、2和3,当新元素4要进队列的时候,只需要上图中(1)和(2)两步,就可以把新结点连接到链表的尾部,同时修改pEnd指针指向新增加的结点。出队列的时候只需要(3)这一步,改变pHead指针使其指向pHead→next,此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊操作,实现代码如下:
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/73_02.jpg?sign=1734456046-1S7AbapsodvNRppE8OHkDhBiTLIJp4In-0-188a5ec9cd8e5c154c40966cbf5e8dd9)
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/74_01.jpg?sign=1734456046-AJQrHcgHWdX0S37EgcBFDnp2ijrTWiXq-0-9288bcd7a704e25e0042739b8b74cea3)
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/75_01.jpg?sign=1734456046-gKTKZPoAmmDC0K3QLHvcjH44a6DN2L4K-0-3e7195ad92575d21a211d2ccd8b82e32)
程序的运行结果为
![](https://epubservercos.yuewen.com/71257F/14700476205665206/epubprivate/OEBPS/Images/75_02.jpg?sign=1734456046-wGARmKCiWL1Zvb3Mbf6Ro4TM0uQgr4Pc-0-f1fc8a0131caf459281970de0ad8702f)
显然用链表来实现队列有更好的灵活性,与数组的实现方法相比,它多了用来存储结点关系的指针空间。此外,也可以用循环链表来实现队列,这样只需要一个指向链表最后一个元素的指针即可,因为通过指向链表尾元素可以非常容易地找到链表的首结点。