前端如何实现队列
前言
队列对于我们来说再简单不过了,就是排队呀,咱们今天看看怎么使用js 实现队列的思想,简单容易理解,可以看看偶
1.定义
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列 先进先出
2.队列的实现
2.1 对列的方法
- enqueue 从队列尾部添加一个元素
- dequeue 从队列头部删除一个元素
- head 返回头部的元素 不是删除
- size 返回队列的大小
- clear 清空队列
- isEmpty 判断队列是否为空
- tail 返回队列尾节点
2.2 实现一个队列
上次在栈的时候我们使用函数创建对象,这次用es6 的class 来实现
class Queue{ constructor(){ this.items = [] } // 向队列尾部添加一个元素 enqueue(item) { this.items.push(item) } // 移除队列头部的元素 dequeue(){ return this.items.shift() } // 返回队列头部的元素 head(){ return this.items[0] } // 返回队列尾部的元素 tail(){ return this.items[this.items.length-1]; } // 返回队列大小 size(){ return this.items.length } // clear clear(){ this.items=[] } // isEmpty 判断是否为空队列 isEmpty(){ return this.items.length === 0 }} let queue = new Queue()queue.enqueue(111)queue.enqueue(222) exports.Queue = Queue; console.log(queue.tail()) console.log(queue.head()) console.log(queue.size()) 复制代码
3. 队列的应用
3.1 存在一个数组 a[100]存放0-99,要求每隔两个数删除掉一个数,到末尾时候循环至开头继续进行,求最后一个被删掉的数。
3.2 思路
1. 从队列头部删除一个元素, index+1
2. 如果index%3 ===0 就说明这个元素是需要删除的元素,如果不等于0,就不是需要被删除的元素,则把它添加到队列的尾部
不停地有元素被删除,最终队列里只有一个元素,此时while 循环终止,队列的所剩的元素就是最后一个被删除的元素
function del_ring(arr_list){ // 把数组里的元素都放入到队列中 var queue = new Queue.Queue(); for(var i=0;i< arr_list.length;i++){ queue.enqueue(arr_list[i]); } var index = 0; while(queue.size() != 1){ // 弹出一个元素,判断是否需要删除 var item = queue.dequeue(); index += 1; // 每隔两个就要删除掉一个,那么不是被删除的元素就放回到队列尾部 if(index %3 != 0){ queue.enqueue(item); } } return queue.head();}; var arr_list = []; for(var i=0;i< 100;i++){ arr_list.push(i); } console.log(del_ring(arr_list)); 复制代码
3.3 用队列输出杨辉三角的前n行 n >= 1
Queue = require('./myqueue') function print_yanghui(n){ var queue = new Queue.Queue(); queue.enqueue(1); // 第一层for循环控制打印几层 for(var i=1; i<=n; i++){ var line = ""; var pre = 0; // 第二层for循环控制打印第 i 层 for(var j=0; j<i; j++){ var item = queue.dequeue(); line += item + " " // 计算下一行的内容 var value = item + pre; pre = item; queue.enqueue(value); } // 每一层最后一个数字是1,上面的for循环没有计算最后一个数 queue.enqueue(1); console.log(line); } }; function print_yanghui_2(n){ var queue = new Queue.Queue(); queue.enqueue(1); queue.enqueue(0); for(var i=1; i<=n; i++){ var line = ""; var pre = 0; while(true){ var item = queue.dequeue(); // 用一个0把每一行的数据分割开,遇到0不输出, if(item==0){ queue.enqueue(1); queue.enqueue(0); break }else { // 计算下一行的内容 line += item + " " var value = item + pre; pre = item; queue.enqueue(value); } } console.log(line); } } print_yanghui(10); //print_yanghui_2(10);
总结:
小编是一枚前端程序员,欧而会写一些前端的东西,希望能帮助你偶,大家一起学习,一起进步,加油!