![Scala程序员面试算法宝典](https://wfqqreader-1252317822.image.myqcloud.com/cover/940/36922940/b_36922940.jpg)
2.2 如何实现队列
【出自XL面试题】
难度系数:★★★☆☆ 被考察系数:★★★★☆
题目描述:
实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。
分析与解答:
与实现栈的方法类似,队列的实现也有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
方法一:数组实现
下图给出了一种最简单的实现方式,用front来记录队列首元素的位置,用rear来记录队列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置,同时执行rear++,出队列的时候只需要执行front++即可。
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_67_01.jpg?sign=1739532460-fR5ghzNWhnTf18KgiZVAqlbcUfkiTzyk-0-8023ca583e26c490cd70dead7501e5be)
实现代码如下:
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_67_02.jpg?sign=1739532460-Q4W709o5d4nfhdffkS3xRuVhdrPqlw5j-0-2b53f81b7993d302c1832fe9f709e149)
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_68_01.jpg?sign=1739532460-EkJxIrxHUF7PPqjmrrK4twwaEQTIuVe7-0-7a310d18f5ea0b9ed71f6aac4c047241)
程序的运行结果为
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_68_02.jpg?sign=1739532460-1S1musAzvI9fGsJ8EBRKkU0DMx5YpAGm-0-6b157a179c9e10a3b19365d09f00ccd1)
以上这种实现方法最大的缺点:出队列后数组前半部分的空间不能够充分地利用,解决这个问题的方法为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后,可以从数组首位置开始循环利用,具体实现方法可以参考数据结构相关图书。
方法二:链表实现
采用链表实现队列的方法与实现栈的方法类似,分别用两个指针指向队列的首元素与尾元素,如下图所示。用pHead来指向队列的首元素,用pEnd来指向队列的尾元素。
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_68_03.jpg?sign=1739532460-eKWDEYs4cyZQWkwJPk32UqK4mC6GoZ6s-0-96b0c2bb2c59082b63e755b76b0a11bf)
在上图中,刚开始队列中只有元素1、2和3,当新元素4要进队列的时候,只需要上图中(1)和(2)两步,就可以把新结点连接到链表的尾部,同时修改pEnd指针指向新增加的结点。出队列的时候只需要(3)这一步,改变pHead指针使其指向pHead→next,此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊操作,实现代码如下:
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_69_01.jpg?sign=1739532460-6r4c5K8umSJTHfeDzIooRZiqFeoBbvwe-0-e86bd8242e21b559cd661648806de8f2)
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_70_01.jpg?sign=1739532460-Z78dRlCv8cFRVExRQauTs76EOt9U2xKx-0-2aa107de301501896e28b63060ceca5d)
程序的运行结果为
![](https://epubservercos.yuewen.com/F0C373/19573973301151206/epubprivate/OEBPS/Images/978-7-111-65029-4_70_02.jpg?sign=1739532460-yw1Mv40Zfp6qL79XfsEcCKd8TCOFHSz7-0-e5cefc8df8826dff618dd4e4095c5fcd)
显然用链表来实现队列有更好的灵活性,与数组的实现方法相比,它多了用来存储结点关系的指针空间。此外,也可以用循环链表来实现队列,这样只需要一个指向链表最后一个元素的指针即可,因为通过指向链表尾元素可以非常容易地找到链表的首结点。