喜欢看之前，养成习惯:P俗话说，“时刻准备着”。算法和数据结构对工程师来说非常重要。而这部分是很难通过短期的冲刺学习来掌握的。只有刻意学习和不断练习才能掌握。今天我们将回顾队列。了解队列的用法队列是很常见的数据结构，在面试中经常出现。今天我们就来说说这个数据结构，然后看两个问题。本文可能涉及到链表。我在之前的文章中写过链表。参考链接：【第28期】常见链表操作回顾【第29期】熟悉链表的几个经典话题队列是一种线性数据结构，先进先出，FIFO。生活中典型的场景就是排队，从后面插入新的元素，取出最旧的元素：下面我们用两种姿势来实现一个队列：栈链表leetcode#232栈实现队列使用栈实现以下操作在队列上：push(x)——将一个元素推到队列的尾部。pop()——从队列头部移除一个元素。peek()--返回队列头部的元素。empty()--返回队列是否为空。示例：MyQueuequeue=newMyQueue();queue.push(1);queue.push(2);queue.peek();//返回1queue.pop();//返回1queue.empty();//返回false1。用栈实现队列Stack是先进后出的数据结构，queue是先进先出的数据结构，那么如何用栈来模拟队列呢？很简单，倒两次就可以了。使用两个堆栈，一个用于入队，一个用于出队：Diagram:Codeimplementation:/***在这里初始化你的数据结构。*/varMyQueue=function(){this.input=[];这。output=[];};/***将元素x推到队列的后面。*@param{number}x*@return{void}*/MyQueue.prototype.push=function(x){this.input.push(x);};/***从队列前面移除元素并返回该元素。*@return{number}从队列头部移除元素*/MyQueue.prototype.pop=function(){while(this.input.length){this.output.push(this.input.pop());}varfirst=this.output.pop();while(this.output.length){this.input.push(this.output.pop());}returnfirst;};/***获取最前面的元素。返回队列头部的元素。*@return{number}*/MyQueue.prototype.peek=function(){returnthis.input[0];};/***返回队列是否为空。*@return{boolean}返回队列是否为空*/MyQueue.prototype.empty=function(){return!this.input.length&&!this.output.length;};varobj=newMyQueue();obj.push(1);obj.push(2);obj.push(3);varparam_2=obj.pop();console.log(param_2);//leader出来了，1varparam_3=obj.peek();console.log(param_3);//返回队列第一个元素：2varparam_4=obj.empty();console.log('isEmpty:',param_4);//错误2。我们都很熟悉用链表实现队列链表。前面两期都是关于链表的：xxx,xxx首先看一下基础设施，包括我们要实现的功能有哪些：//QueueusinglinkedlistfunctionQueueUsingLinkList(){letNode=function(elm){this.element=elm;这个.下一个=空；};//跟踪大小letlength=0;//跟踪列表lethead=null;//将数据入队this.enqueue=function(elm){};//从队列中移除项目this.出队=功能（）{};//返回q中的第一个元素ueuethis.peek=function(){};//返回队列中的最后一个元素this.rear=function(){};//检查队列是否为空this.isEmpty=function(){};//返回队列的大小this.size=function(){};//清空队列this.clear=function(){};}enqueue，向队列中添加元素首先检查队列是否为空，如果为空，则将新元素作为头节点，否则，添加新元素到最后代码实现：//Enqueuedatainthequeuethis.enqueue=function(elm){letnode=newNode(elm),current;//Ifheadisemptythen//在开头添加节点if(head===null){head=node;}else{//否则将节点添加为//现有列表的下一个元素current=head;while(current.next){current=current.next;}current.next=节点；}//增加长度length++;};dequeue，删除队列中的元素队列是先进先出的数据结构，所以dequeue时，要移除并返回头部元素，长度减少一，指针向后移动一位。代码实现：//从队列中取出元素this.dequeue=function(){letcurrent=head;//如果有项目则删除它//并使下一个元素成为第一个if(current){letelm=current.element;当前=当前.下一个；头部=当前；长度-;返回榆树；}返回空值；我们已经实现了其他辅助方法的核心入队和出队。几个辅助函数：peek查看头部元素rear查看尾部元素转数组size查看大小isEmpty检查是否为空emptythequeueisEmpty//检查队列是否为空this.isEmpty=function(){returnlength===0;}size//返回队列的大小this.size=function(){returnlength;}Viewasarray://将队列转换为数组this.toArray=function(){letarr=[];让电流=头；while(current){arr.push(current.element);当前=当前.下一个；}returnarr;}rear查看后面的元素//返回队列中的最后一个元素this.rear=function(){letcurrent=head;//如果头是empty//返回nullif(current===null){returnnull;}//返回最后一个元素while(current.next){current=current.next;}returncurrent.element;}peek//返回队列中的第一个元素this.peek=function(){if(head){returnhead.element;}returnnull;}clear//清空队列this.clear=function(){head=null;length=0;}测试letqueue=newQueueUsingLinkList();console.log(queue.isEmpty());//truequeue.enqueue('pranav');queue.enqueue('sachin');queue.enqueue('yogesh');console.log(queue.toArray());//["pranav","sachin","yogesh"]queue.dequeue();queue.dequeue();console.log(queue.toArray());//["yogesh"]queue.enqueue('prashant');queue.enqueue('yadav');queue.dequeue();console.log(queue.toArray());//["prashant","yadav"]console.log(queue.size());//2console.log(queue.peek());//"prashant"console.log(queue.rear());//"yadav"完整代码//队列使用链表函数QueueUsingLinkList(){//NodeletNode=function(elm){this.element=elm;这个.下一个=空；}//跟踪大小letlength=0;//跟踪列表lethead=null;//在队列中入队数据this.enqueue=function(elm){letnode=newNode(elm),current;//Ifheadisemptythen//在开头添加节点if(head===null){head=node;}else{//否则将节点添加为//现有列表的下一个元素current=head;while(current.next){current=current.next;}current.next=节点；}//增加长度length++;}//从队列中移除元素this.dequeue=function(){letcurrent=head;//如果有项目则删除它//并使下一个元素成为第一个if(current){让elm=current.element;当前=当前.下一个；头部=当前；长度-;返回榆树；}返回空值；}//返回队列中的第一个元素this.peek=function(){if(head){returnhead.element;}返回空值；}//返回队列中的最后一个元素this.rear=function(){letcurrent=head;//如果head为空//返回nullif(current===null){returnnull;}//返回最后一个元素while(current.next){current=current.next;}返回当前元素；}//将队列转换为数组this.toArray=function(){letarr=[];让电流=头；while(current){arr.push(current.element);当前=当前.下一个；}返回arr;}//检查是否队列为空this.isEmpty=function(){returnlength===0;}//返回队列的大小this.size=function(){returnlength;}//清空队列this.clear=function(){head=null;长度=0；}}总结掌握这些常用数据结的基本操作，对我们的日常工作也大有裨益。学好数据结构和算法，三分理论，七分实践。希望今天的内容能对你有所启发，谢谢:)最后，如果你觉得内容有帮助，可以关注我的公众号《前端e进阶》，一起学习，:)
