JavaScript队列、优先队列与循环队列
payson_tsung 人气:0队列是一种遵从先进先出(FIFO)原则的有序集合
队列在尾部添加新元素,从顶部移除元素
队列的理解
队列在我们生活中最常见的场景就是排队了
队列这个名字也已经很通俗易懂了
和栈很像,这不过队列是先入先出的数据结构
队列的前面是队头
队列的后面是队尾
出队从队头出
入队从队尾入
队列的创建
和栈类似,这里我就不就不啰嗦了
同样需要实现一些功能
这里我类比生活中的排队上厕所
- 向队列中添加元素(进入排队的队伍中)
- 移除队头元素(队伍最前面的人出队进入厕所)
- 查看队头元素(查看队伍最前面的人)
- 判断队列是否为空(看看队伍中有没有人)
- 移除队伍全部元素(厕所炸了,都散了吧)
- 查看栈里元素个数(查看排队的有多少人)
于是我们可以创建一个完整队列实现,同样是利用我们的数组实现
数组头就是队列头
function Queue() { var items = []; this.enqueue = function (ele) { items.push(ele); };//入队 this.dequeue = function () { return items.shift(); };//出队 this.front = function () { return items[0]; };//查看队头元素 this.isEmpty = function () { return items.length === 0; };//判断队列是否为空 this.size = function () { return items.length; };//队列大小 this.clear = function () { items = []; };//清空队列 this.print = function () { console.log(items.toString()); };//打印队列 } var queue = new Queue(); //声明队列的实例
队列的使用
下面我们就用这个队列简单模拟排队
var queue = new Queue(); console.log("队列是否为空: " + queue.isEmpty()); queue.enqueue('Mr.A'); queue.enqueue('Mr.B'); queue.enqueue('Mr.C'); console.log("当前队列:"); queue.print(); console.log("出队的人: " + queue.dequeue()); console.log("当前队列:"); queue.print();
控制台打印:
优先队列
在我们排队上厕所的时候,来了一位拥有VIP会员卡的朋友,插到了队伍的最前面
过了一会儿又来了一位拥有SVIP会员卡的朋友,插到了VIP的前面
虽然这个比喻可能不恰当,但是生活中可能存在有优先级的队列
优先级高的人可以查到优先级低的人前面
这就是循环队列
如果优先值小的元素放到队列的前面,这叫做最小优先队列
反之优先值大的元素放到队列的前面,这叫做最大优先队列
但其实他们两个仅仅是一个判断的改变,实现方式是一样的
优先队列较普通队列的区别也就是入队要判断优先级,并且需要对我们的元素进行处理,其他方法不变
这处理也就是把元素包装为一个拥有优先级的对象
既然所有对象都有着同样的属性,那我们毫无疑问就应该使用工厂构建
我们可以稍微修改一下我们的队列类
来实现一个最小优先队列
function PriorityQueue() { var items = []; function QueEle(ele, priority){ //封装我们的元素为一个对象 this.ele = ele; //元素 this.priority = priority; //优先级 } this.enqueue = function (ele, priority) { var queObj = new QueEle(ele, priority); //创建队列元素对象 if(this.isEmpty()){ //如果队列是空的,直接插入 this.push(queObj); }else{ var bAdded = false; for(var i = 0, len = items.length; i < len; i++){ if(priority < items[i].priority){ items.splice(i, 0, queObj); // 循环队列,如果优先级小于这个位置元素的优先级,插入 bAdded = true; break; } } if(!bAdded){ items.push(queObj); // 如果循环一圈都没有找到能插队的位置,直接插入队列尾部 } } }; this.dequeue = function () { return items.shift(); }; this.front = function () { return items[0]; }; this.isEmpty = function () { return items.length === 0; }; this.size = function () { return items.length; }; this.clear = function () { items = []; }; this.print = function () { //这个地方稍微修改一下下 var temp = []; for(var i = 0, len = items.length; i < len; i++){ temp.push(items[i].ele); } console.log(temp.toString()); }; }
解释我已经在代码里说的很明白
下面我们就用这个优先队列同样来模拟排队上WC
var pQueue = new PriorityQueue(); pQueue.enqueue('Mr.A', 3); pQueue.enqueue('Mr.B', 3); pQueue.enqueue('Mr.C', 3); console.log("原队列:"); pQueue.print(); pQueue.enqueue('VIP', 2); pQueue.enqueue('SVIP', 1); console.log("新队列:"); pQueue.print();
控制台打印:
循环队列
循环队列典型的例子击鼓传花
还记得在我上高中的时候我们晚自习一停电就玩这个
拿一个东西当“花”,轮着传,“鼓”一停,拿到花的同学就要站起来唱歌
可以把循环队列当作是队列的应用
下面我们来模拟实现循环队列击鼓传花
function hotPotato(pepoleList, frequency){ //参数:表示人的数组,传花的频率 var queue = new Queue(); for(var i = 0, len = pepoleList.length; i < len; i++){ queue.enqueue(pepoleList[i]); //初始化,进入队列 } var eliminated;//被淘汰的同学 while(queue.size() > 1){ //只要队列至少还有两个人,就一直循环 for(var i = 0; i < frequency; i++){//出队入队,模拟循环效果 queue.enqueue(queue.dequeue()); } eliminated = queue.dequeue();//清算 console.log(eliminated + '被淘汰'); } return queue.dequeue();//返回队列中的最后一人 } var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F']; var gameWinner = hotPotato(pepole, 12); console.log('全场最佳:' + gameWinner);
控制台输出:
以上就是JavaScript下的队列实现。
我们还简单理解了两个特殊的队列:优先队列与循环队列。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
加载全部内容