JavaScript实现队列结构
bear*6 人气:0一、认识队列
前面的博客已经讲了受限的数据结构—栈,现在,我们再来看看队列(Queue
)。
- 它是受限的线性表,先进先出(
FIFO
),即first in first out
。 - 受限之处在于它只允许在表的前端(front)进行删除操作。
- 而在表的后端(
rear
)进行插入操作。
其结构图可以表示为:
生活中类似于队列的:例如:当我们在排队买东西的时候,先到先买一样。
二、封装队列
这里也采用数组的方式实现队列结构,首先,创建一个类。
function Queue(){ }
在其内部添加属性和方法,将数组通过属性的方法添加给该类。然后采用原型的方法添加常用的操作。
队列常用的操作有:
enqueue
(element):向队列尾部添加一个(或多个)新的项dequeue()
:移除队列的第一(即排在队列最前面的)项,并且返回被移除的元素front()
:返回队列中第一个元素----最先被添加,也将是最先被移除的元素isEmpty()
:如果队列中不包含任何元素,返回true,否则,返回falsesize()
:返回队列包含的元素个数toString()
:将队列中的内容,转化成字符串形式
现在就来具体实现:
function Queue(){ this.items = []; //向队列尾部添加一个(或多个)新的项 enqueue() Queue.prototype.enqueue = function(element){ this.items.push(element); } //移除队列的第一(即排在队列最前面的)项dequeue() Queue.prototype.dequeue = function(){ return this.items.shift(); } //返回队列中第一个元素 front() Queue.prototype.front = function() { return this.items[0]; } //判断栈是否空isEmpty() Queue.prototype.isEmpty = function(){ return this.items.length == 0; } //返回队列包含的元素个数 size() Queue.prototype.size = function(){ return this.items.length; } //将队列中的内容,转化成字符串形式 toString() Queue.prototype.toString = function(){ var str = ''; for(var i =0;i<this.items.length;i++){ str += this.items[i] + ' '; } return str; } }
以上就是队列的封装,现在进行验证:
var queue = new Queue(); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); queue.enqueue(50); console.log(queue); console.log('移除的第一项是:'+queue.dequeue()); console.log('队列中的第一个元素是:'+queue.front()); console.log('栈是否为空:'+queue.isEmpty()); console.log('栈结构的内容为:'); console.log(queue.toString());
输出的结果为:
构建成功。
来看一个击鼓传花的案例吧!
三、击鼓传花案列
原游戏规则:
- 班级中玩一个游戏,所有学生围成一圈,从某位同学手里开始像旁边的同学传一束花
- 此时一个人在击鼓,当鼓声停下的时候,花落在谁手里,谁就被惩罚。
修改游戏规则:
- 几个朋友一起玩游戏,围成一圈,开始数数,数到某个数字的人自动淘汰
- 最后剩下的这个人获得胜利,判断最后剩下的是原来在哪一个位置上的人?
封装一个基于队列的函数:
- 参数:所有参与人的姓名,基于的数字
- 结果:最终剩下的人的姓名
代码如下:
// 封装队列 function Queue(){ this.items = []; //末尾添加元素 Queue.prototype.enqueue = function(element){ this.items.push(element); } //移除第一个元素 Queue.prototype.dequeue = function(){ return this.items.shift(); } //返回第一个元素 Queue.prototype.front = function(){ return this.items[0]; } //返回队列包含的元素个数 Queue.prototype.size = function(){ return this.items.length; } } function passGame(nameList,num){ // 创建队列 var queue = new Queue(); //将所有的人添加到队列 for(var i = 0;i<nameList.length;i++){ queue.enqueue(nameList[i]); } //进行游戏 while(queue.size() > 1){ //num数字之前的人重新添加到队列末尾 for(var i =1;i<num;i++){ queue.enqueue(queue.dequeue()); } //num数字的人直接移除 queue.dequeue(); } //获取获胜者信息 var endName = queue.front(); console.log('最终剩下的人是:'+endName); return nameList.indexOf(endName); } //进行测试 var nameList = ['a','b','c','d','e']; var g = passGame(nameList,5); console.log('这个人的位置是:'+g);
输出结果为:
加载全部内容