队列
在之前的栈,是一种受限的线性结构,为先进后出,那么同为线性结构的队列,特点又是怎么样的呢?
概念
队列是一种受限的线性表,先进先出,它只允许我们在表的前端进行删除操作,在表的后端进行添加操作。
生活应用
- 在生活中最常看到的队列场景就是排队了,即我们在排队时,排头也就是我们的表头,它允许出去,无法进行插队也就是添加操作,而排尾,也就是我们的表尾,它允许有人进行排队,即添加操作
- 在火车检票的时候,我们正常的是进行排队,而军人,老人等特殊人群可以优先进行处理,这就是优先队列。
程序应用
- 就拿我们JS来说,事件队列是比较常见的,因为JS是一门单线程语言,即在我们触发我们的函数的时候,会有一个事件队列,其会按照事件的触发顺序来执行,即先触发先执行,这就是队列的一种体现
- 当然线程队列也是一种队列的体现,我们一般为了任务能够并行处理,会用到多线程,但是多个线程会占据非常多的内存,所以这个时候我们可以通过使用线程队列,按照次序来启动线程,并处理对应的任务。
队列结构
当然队列结构的实现和栈一样,可以通过数组和链表实现
首先我们先封装一下队列
function queue(){ //队列的属性 this.items = [] //队列的相关操作 } var queue = new queue() 复制代码
因为JS中的类是基于对象的所以我们封装了一个队列类,在类中我们可以定义队列的属性与方法,封装好之后我们可以去通过调用来对队列实现一些操作
常见操作及封装
- enqueue(element):在队列的尾部添加元素
- dequeue():移除队列的首个元素,并返回其值
- front():返回队列的第一个元素
- isEmpty:判断队列是否为空队列
- size:返回队列长度
- toString():转换字符串
enqueue(element):使用push方法来进行入队封装
queue.prototype.enqueue = function (element) { this.items.push(element) } 复制代码
dequeue():通过JS提供的shift的方法来进行出队操作
queue.prototype.delet = function () { return this.items.shift() } 复制代码
front():直接通过数组下标来返回队首元素
queue.prototype.front = function () { return this.items[0] } 复制代码
isEmpty():通过数组的length来进行栈的判空
queue.prototype.isEmpty = function () { return this.items.length == 0 } 复制代码
size()
queue.prototype.size = function () { return this.items.length } 复制代码
toString():通过声明字符串变量,对栈进行遍历,通过JS字符串的特性,来进行字符串拼接,最后返回其字符串,其实现原理和栈的toString一样。
queue.prototype.toString = function () { var reString = '' for (let i = 0; i < this.items.length; i++) { reString += this.items[i] + '' } return reString } 复制代码
使用
在封装好之后我们就可以开始进行调用
queue.enqueue(1) queue.enqueue(19) queue.enqueue(11) console.log(queue) 复制代码
queue.delet() console.log(queue) 复制代码
大家可以试着自己些写一下并体验队列的这几种操作
击鼓传花
相信大家都玩过击鼓传花的游戏吧,击鼓的时候传递花朵,鼓声停,花在谁手中谁就受惩罚
现在有不同的游戏规则,即同学围成一圈,按阿拉伯数字顺序进行数数,当某人数到在场人数的时候就会被淘汰
我们现在要用队列来实现这个游戏并返回来最终获胜者的姓名
- 算法原理:
现在我们将所有人按次序放入一个队列中,然后从队首开始出队入队,以此当出现在场人数的时候,其正好是队首,出队,多次操作,得到结果
- 算法实现:
- 创建队列并将所有人入队
var queue = new queue for (let i = 0; i < list.length; i++) { queue.enqueue(nameList[i]) } 复制代码
- 开始循环入队出队直到队列的长度为1
while (queue.size() > 1) { //开始数num,当不是num的时候出队后重新入队,当num是在场人数时,出队。 for (let i = 0; i < num - 1; i++) { queue.enqueue(queue.dequeue()) } //删除目标即现在的队首 queue.dequeue() }