【数据结构与算法】详解什么是队列，并用代码手动实现一个队列结构

刺骨的言语ヽ痛彻心扉 2023-02-28 12:54 46阅读 0赞

本系列文章【数据结构与算法】所有完整代码已上传 **github**，想要**完整代码**的小伙伴可以直接去那获取，可以的话欢迎点个**Star**哦~下面放上跳转链接

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

**队列结构**也是平时非常常见的一种**受限**的**线性**数据结构。它跟栈结构一样都是受限的数据结构，区别就是队列结构是遵循着**先进先出**的原则，本文将对此进行详细的讲解。  
![在这里插入图片描述][20200721165000507.png_x-oss-process_image]

>  *  公众号：**前端印象**
>  *  不定时有送书活动，记得关注~
>  *  关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

### 数据结构——队列 ###

*  一、什么是队列
 *  二、队列结构的方法
 *  三、用代码实现一个队列结构
 *   *  （1）创建一个构造函数
     *  （2）实现enqueue()方法
     *  （3）实现dequeue()方法
     *  （4）实现front()方法
     *  （5）实现isEmpty()方法
     *  （6）实现size()方法
     *  （7）实现toString()方法
 *  四、队列结构的实战应用
 *  五、总结

# 一、什么是队列 #

**队列**的限制到底是什么呢？我们先用一个形象的例子来了解一下队列的定义

我们可以把**队列**想象成我们排队买票的队伍，每个排队的人就相当于一个元素  
![在这里插入图片描述][20200721163023620.png_x-oss-process_image]  
队伍的前面叫做**前端**；  
队伍的后面叫做**后端**；

此时，有一个人进入队伍来买票，此时相当于向队列中添加一个新的元素  
![在这里插入图片描述][20200721163240263.png_x-oss-process_image]  
紧接着后面又来了一个人，也要排队买票，但按照排队的规则，这个新来的人只能排在上一个人的后面，所以此时的队伍是这样的

![在这里插入图片描述][2020072116340226.png_x-oss-process_image]  
此时售票员开始卖票了，这个队伍最前面的人，也就是第一个人来的人可以享受最先买票的权利，所以他买完票后，就可以离开这个队伍了，那么他后面的人就成了这个队伍最前面的人。  
![在这里插入图片描述][20200721163616875.png_x-oss-process_image]

其实这也就相当于队列删除元素的操作，队列删除元素就像是排队买票，最先来的人可以最先买到票离开队伍，并且也只能是按照先来后到的顺序买票再离开；相反，晚来的人也就只能等前面的人都买完票了以后才有资格买票再离开这个队伍了。

根据上面所讲的例子，相信大家对**队列**这个概念有了深刻的理解了吧。

所以我们总结的来说一下，**队列**就是一个受限的线性表，遵循着“**先进先出，后进后出**”的原则，即只允许在队列的前端删除元素，在队列的后端进行添加元素。

# 二、队列结构的方法 #

与其他的数据结构一样，队列结构也有自己的操作元素的方法，我们来看一下常见的队列操作元素的方法有哪些吧~

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>enqueue()</td> 
   <td>向队列后端添加元素</td> 
  </tr> 
  <tr> 
   <td>dequeue()</td> 
   <td>删除队列最前端的一个元素，并返回该元素</td> 
  </tr> 
  <tr> 
   <td>front()</td> 
   <td>返回队列前端的元素，但不会移除该元素</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>查看队列是否为空</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回队列内元素的个数</td> 
  </tr> 
  <tr> 
   <td>toString()</td> 
   <td>以字符串的形式展示队列内的所有元素</td> 
  </tr> 
 </tbody> 
</table>

# 三、用代码实现一个队列结构 #

接下来，我们就用JavaScript实现一个基于数组的线性结构的类，因为是基于数组实现的队列，所以我们可以把数组的头部看作是队列的前端，把数组的尾部看作是队列的后端

## （1）创建一个构造函数 ##

function Queue() { 
    	//属性
        this.list = []
    }

## （2）实现enqueue()方法 ##

`enqueue()`方法就是向一个队列的后端（数组的尾部）添加新的元素的方法

接下来我们来单独实现一下该方法

function Queue() { 
    	//属性
        this.list = []
        
        //enqueue()方法的实现
        Queue.prototype.enqueue = function (e) { 
            this.list.push(e)
        }
    }

我们来使用一下该方法

let queue = new Queue()
    queue.enqueue(4)
    queue.enqueue(8)

此时的队列是这样的  
![在这里插入图片描述][20200721165546536.png_x-oss-process_image]

## （3）实现dequeue()方法 ##

`dequeue()`方法就是删除队列中最前端（数组的前面）的一个元素，并返回该元素

接下来我们来单独实现一下该方法

function Queue() { 
    	//属性
        this.list = []
        
        //dequeue()方法的实现
        Queue.prototype.dequeue = function () { 
            return this.list.shift()
        }
    }

我们来使用一下该方法

let queue = new Queue()
    //先按 4 8 的顺序向队列添加元素
    queue.enqueue(4)
    queue.enqueue(8)
    
    queue.dequeue()              // 返回 4，同时队列中的元素4被删除

先添加了元素4，再添加了元素8，所以使用`dequeue()`方法时，删除的是最先添加的元素4，此时队列的情况是这样的  
![在这里插入图片描述][20200721165907783.png_x-oss-process_image]

## （4）实现front()方法 ##

`front()`方法就是返回队列最前端（数组的前面）的第一个元素，并且不会对队列里的数组进行任何的操作

我们来实现一下该方法

function Queue() { 
    	//属性
        this.list = []
        
        //front()方法的实现
        Queue.prototype.front = function () { 
            return this.list[0]
        }
    }

我们来使用一下该方法

let queue = new Queue()
    //先按 4 8 的顺序向队列添加元素
    queue.enqueue(4)
    queue.enqueue(8)
    
    queue.front()          // 返回 4,但没有对队列中的元素进行任何操作

此时队列中的情况是这样的  
![在这里插入图片描述][20200721170203151.png_x-oss-process_image]

## （5）实现isEmpty()方法 ##

`isEmpty()`方法就是判断队列是否为空（数组内是否有元素），若为空，则返回 `true`；否则，返回 `false`

我们来实现一下该方法

function Queue() { 
    	//属性
        this.list = []
        
        //isEmpty()方法的实现
        Queue.prototype.isEmpty = function() { 
            if(this.list.length === 0) { 
                return true
            }
            else { 
                return false
            }
        }
    }

我们来使用一下该方法

let queue = new Queue()
    
    queue.isEmpty()        //返回 true,因为此时并没有向队列添加过元素
    
    queue.enqueue(3)
    
    queue.isEmpty()       //返回 false,因为上一行代码向队列里添加了元素3,此时队列不为空

## （6）实现size()方法 ##

`size()`方法就是查询并返回队列中的元素个数（数组的长度）

我们来实现一下该方法

function Queue() { 
    	//属性
        this.list = []
        
        //size()方法的实现
        Queue.prototype.size = function () { 
            return this.list.length
        }
    }

我们来使用一下该方法

let queue = new Queue()
    
    queue.size()        //返回 0,因为还未向队列添加过元素
    
    queue.enqueue(4)
    queue.enqueue(8)
    
    queue.size()       //返回 2,因为上面两行代码分别向队列添加了一个元素

## （7）实现toString()方法 ##

`toString()`方法就是将队列内的元素用字符串的方式展示出来（将数组转化成字符串）并返回

我们来实现一下该方法

function Queue() { 
    	//属性
        this.list = []
        
        //toString()方法的实现
        Queue.prototype.toString = function () { 
            let string = ''
            for(let i in this.list) { 
                string += `${ this.list[i]} `
            }
            return string
        }
    }

我们来使用一下该方法

let queue = new Queue()
    
    queue.enqueue(4)
    queue.enqueue(8)
    queue.enqueue(12)
    
    queue.toString()     //返回 4 8 12

# 四、队列结构的实战应用 #

相信大家都玩过击鼓传花的游戏，这里我们来改动一下击鼓传花的规则。

**规则是：** 几个人围坐成一个圈，指定一个数字，例如3，选其中一个人开始数数，数到3的那个人被淘汰，然后从刚刚被淘汰的人的下一个人重新开始数。以此类推……直到只剩一个人，那么这个剩下的人就是获胜者

规则比较复杂，我用图文来给大家演示一次

首先是五个人围坐成一圈，分别是`V` 、`W` 、`X` 、`Y` 、`Z`  
![在这里插入图片描述][20200721194439757.png_x-oss-process_image]  
然后我们指定一个数字，就比如 `3` 吧，然后从 `V` 开始数，数到 `X` 时为3，所以 `X` 被淘汰  
![在这里插入图片描述][20200721194953718.png_x-oss-process_image]  
然后接下来 `Y` 从1开始数，到 `V` 时数到了3，所以 `V` 淘汰  
![在这里插入图片描述][20200721195344412.png_x-oss-process_image]  
然后接下来 `W` 从1开始数，到 `Z` 时数到了3，所以 `Z` 淘汰  
![在这里插入图片描述][20200721195439433.png_x-oss-process_image]  
然后接下来还是 `W` 先从1开始数，然后 `Y` 数到2，最后 `W` 数到3，所以 `W` 被淘汰，场上只剩下 `Y` 了，所以 `Y` 是最终的获胜者  
![在这里插入图片描述][202007211956554.png_x-oss-process_image]  
好了，看完了上面这个游戏规则，我们来考虑一下如何用队列来实现它。

其实很简单，因为所有人坐成一个圈形成了一个循环，所以我们可以每数一个数，将队列前端的元素取出，再重新添加到队列的后端，如果是数到了刚开始规定的数字，则该被取出的元素不再被添加到队列的后端了，然后又继续重新数数，以此类推……直到队列里只有一个元素了，该元素就是最终获胜的。

接下来封装一个该游戏规则的函数，该函数需要传入 `成员列表` 和 `一个数字`

我们来使用一下这个函数，来验证一下结果是否跟刚刚上面举得例子的结果一样。

passFlower(['V', 'W', 'X', 'Y', 'Z'], 3)   // 返回 Y

可以看到，运行结果跟我们举例时看到的结果一样，这样一个队列的实战运用就讲完了，大家可以自己动手实现一遍这样的功能，可以加深一下印象

# 五、总结 #

队列结构的讲解就到这里了，希望大家对队列结构有了更深一层的理解。下一篇文章我将讲解一下另一种特殊的队列结构，叫做**优先级队列**。

大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。

然后大家可以关注一下我的微信公众号：**前端印象**，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。

或者也可以去我的github上获取**完整代码**，欢迎大家点个**Star**

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~ 带你们在Python爬虫的过程中学习Web前端

[https_github.com_Lpyexplore_structureAndAlgorithm-JS]: https://github.com/Lpyexplore/structureAndAlgorithm-JS
[20200721165000507.png_x-oss-process_image]: /images/20230209/10f168d24fd942bd9d83bf070ed1589e.png
[20200721163023620.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721163023620.png?x-oss-process=image
[20200721163240263.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721163240263.png?x-oss-process=image
[2020072116340226.png_x-oss-process_image]: https://img-blog.csdnimg.cn/2020072116340226.png?x-oss-process=image
[20200721163616875.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721163616875.png?x-oss-process=image
[20200721165546536.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721165546536.png?x-oss-process=image
[20200721165907783.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721165907783.png?x-oss-process=image
[20200721170203151.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721170203151.png?x-oss-process=image
[20200721194439757.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721194439757.png?x-oss-process=image
[20200721194953718.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721194953718.png?x-oss-process=image
[20200721195344412.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721195344412.png?x-oss-process=image
[20200721195439433.png_x-oss-process_image]: https://img-blog.csdnimg.cn/20200721195439433.png?x-oss-process=image
[202007211956554.png_x-oss-process_image]: https://img-blog.csdnimg.cn/202007211956554.png?x-oss-process=image