JavaScript实现队列结构（Queue）

刘震宇 發表於 2020-3-6 09:50:00

<h2 id="javascript实现队列结构queue">JavaScript实现队列结构（Queue）</h2>
<h3 id="一队列简介">一、队列简介</h3>
队列是是一种受限的线性表，特点为先进先出（FIFO：first in first out）。
<ul>
<li>受限之处在于它只允许在表的前端（front）进行删除操作；</li>
<li>在表的后端（rear）进行插入操作；</li>
</ul>
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%98%9F%E5%88%97/1.png" alt="image-20200226171659886" loading="lazy">
相当于排队买票，先来的先买票，后来的后买票。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%98%9F%E5%88%97/2.png" alt="image-20200226171449228" loading="lazy">
队列的应用：
<ul>
<li>打印队列：计算机打印多个文件的时候，需要排队打印；</li>
<li>线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待CPU处理；</li>
</ul>
队列类的实现：
队列的实现和栈一样，有两种方案：
<ul>
<li>基于数组实现；</li>
<li>基于链表实现；</li>
</ul>
队列的常见操作：
<ul>
<li>enqueue（element）：向队列尾部添加一个（或多个）新的项；</li>
<li>dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；</li>
<li>front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与Stack类的peek方法非常类似）；</li>
<li>isEmpty（）：如果队列中不包含任何元素，返回true，否则返回false；</li>
<li>size（）：返回队列包含的元素个数，与数组的length属性类似；</li>
<li>toString（）：将队列中的内容，转成字符串形式；</li>
</ul>
<h3 id="二封装队列类">二、封装队列类</h3>
<h4 id="21代码实现">2.1.代码实现</h4>
<pre><code> // 基于数组封装队列类
function Queue() {
// 属性
 this.items = []

// 方法
// 1.enqueue():将元素加入到队列中
Queue.prototype.enqueue = element => {
 this.items.push(element)
}

// 2.dequeue():从队列中删除前端元素
Queue.prototype.dequeue = () => {
 return this.items.shift()
}

// 3.front():查看前端的元素
Queue.prototype.front = () => {
 return this.items
}

// 4.isEmpty:查看队列是否为空
Queue.prototype.isEmpty = () => {
 return this.items.length == 0;
}

// 5.size():查看队列中元素的个数
Queue.prototype.size = () => {
 return this.items.length
}

// 6.toString():将队列中元素以字符串形式输出
Queue.prototype.toString = () => {
 let resultString = ''
 for (let i of this.items){
 resultString += i + ' '
 }
 return resultString
 }
}
</code></pre>
测试代码：
<pre><code> // 创建队列
let queue = newQueue()

// 将元素加入到队列中
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue); //58

// 从队列中删除元素
queue.dequeue()
console.log(queue); //62
queue.dequeue()
console.log(queue); //64

//front
console.log(queue.front()); //67

// 验证其他方法
console.log(queue.isEmpty()); //70
console.log(queue.size()); //71
console.log(queue.toString()); //72
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%98%9F%E5%88%97/3.png" alt="image-20200305211334015" loading="lazy">
<h4 id="22队列的应用">2.2.队列的应用</h4>
使用队列实现小游戏：击鼓传花，传入一组数据和设定的数字num，循环遍历数组内元素，遍历到的元素为指定数字num时将该元素删除，直至数组剩下一个元素。
代码实现：
<pre><code> // 队列应用：面试题：击鼓传花
let passGame = (nameList, num) => {
 //1.创建队列结构
 let queue = new Queue()

 //2.将所有人依次加入队列
 // 这是ES6的for循环写法，i相当于nameList
 for(let i of nameList){
 queue.enqueue(i)
 }


 // 3.开始数数
while(queue.size() > 1){//队列中只剩1个人就停止数数
 // 不是num的时候，重新加入队列末尾
 // 是num的时候，将其从队列中删除
 // 3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后)
 for(let i = 0; i< num-1; i++ ){
 queue.enqueue(queue.dequeue())
 }
 // 3.2.num对应这个人，直接从队列中删除
 /*
 思路是这样的，由于队列没有像数组一样的下标值不能直接取到某一元素，所以采用，把num前面的num-1个元素先删除后添加到队列末尾，这样第num个元素就排到了队列的最前面，可以直接使用dequeue方法进行删除
 */
 queue.dequeue()
}

 //4.获取剩下的那个人
 console.log(queue.size()); //104
 let endName = queue.front()
 console.log('最终剩下的人：' + endName); //106

 return nameList.indexOf(endName);
}

//5.测试击鼓传花
let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony']
console.log(passGame(names, 3)); //113
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%98%9F%E5%88%97/4.png" alt="image-20200305212021550" loading="lazy">
<h3 id="三优先队列">三、优先队列</h3>
优先级队列主要考虑的问题为：
<ul>
<li>每个元素不再只是一个数据，还包含数据的优先级；</li>
<li>在添加数据过程中，根据优先级放入到正确位置；</li>
</ul>
<h4 id="31优先级队列的实现">3.1.优先级队列的实现</h4>
代码实现：
<pre><code> // 封装优先级队列
function PriorityQueue() {

 //内部类：在类里面再封装一个类;表示带优先级的数据
 function QueueElement(element, priority) {
 this.element = element;
 this.priority = priority;
 }

 // 封装属性
 this.items = []

 // 1.实现按照优先级插入方法
 PriorityQueue.prototype.enqueue = (element, priority) => {
 // 1.1.创建QueueElement对象
 let queueElement = new QueueElement(element, priority)

 // 1.2.判断队列是否为空
 if(this.items.length == 0){
 this.items.push(queueElement)
 }else{
 // 定义一个变量记录是否成功添加了新元素
 let added = false
 for(let i of this.items){
 // 让新插入的元素与原有元素进行优先级比较(priority越小，优先级越大)
 if(queueElement.priority < i.priority){
 this.items.splice(i, 0, queueElement)
 added = true
 // 新元素已经找到插入位置了可以使用break停止循环
 break
 }
 }
 // 新元素没有成功插入，就把它放在队列的最前面
 if(!added){
 this.items.push(queueElement)
 }
 }
 }

 // 2.dequeue():从队列中删除前端元素
 PriorityQueue.prototype.dequeue = () => {
 return this.items.shift()
 }

 // 3.front():查看前端的元素
 PriorityQueue.prototype.front = () => {
 return this.items
 }

 // 4.isEmpty():查看队列是否为空
 PriorityQueue.prototype.isEmpty = () => {
 return this.items.length == 0;
 }

 // 5.size():查看队列中元素的个数
 PriorityQueue.prototype.size = () => {
 return this.items.length
 }

 // 6.toString():以字符串形式输出队列中的元素
 PriorityQueue.prototype.toString = () => {
 let resultString = ''
 for (let i of this.items){
 resultString += i.element + '-' + i.priority + ' '
 }
 return resultString
 }
}
</code></pre>
测试代码：
<pre><code> // 测试代码
let pq = new PriorityQueue();
pq.enqueue('Tom',111);
pq.enqueue('Hellen',200);
pq.enqueue('Mary',30);
pq.enqueue('Gogo',27);
// 打印修改过后的优先队列对象
console.log(pq);
</code></pre>
测试结果：
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%98%9F%E5%88%97/5.png" alt="image-20200226223314535" loading="lazy">
<h4 id="32注意点">3.2.注意点</h4>
关于数组方法splice用法：
<ul>
<li>
splice（1，0，'Tom'）：表示在索引为1的元素前面插入元素’Tom‘（也可以理解为从索引为1的元素开始删除，删除0个元素，再在索引为1的元素前面添加元素'Tom'）；
</li>
<li>
splice（1，1，'Tom'）：表示从索引为1的元素开始删除（包括索引为1的元素），共删除1个元素，并添加元素'Tom'。即把索引为1的元素替换为元素'Tom'。
</li>
</ul>
数组的push方法在数组、栈和队列中的形式：
<ul>
<li>数组：在数组中，pop(3)，结果为；</li>
<li>栈：执行pop(0)，pop(1)，pop(2)，pop(3)，从栈底到栈顶的元素分别为：0，1，2，3；如果看成数组，可写为，但是索引为3的元素3其实是栈顶元素；所以说栈的push方法是向栈顶添加元素（但在数组的视角下为向数组尾部添加元素）；</li>
<li>队列：enqueue方法可以由数组的push方法实现，与数组相同，相当于在数组尾部添加元素。</li>
</ul>
可以这样想：栈结构是头朝下（索引值由下往上增大）的数组结构。
<img src="https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%98%9F%E5%88%97/6.png" alt="image-20200226231025462" loading="lazy">
<blockquote>
参考资料:JavaScript数据结构与算法
</blockquote>

</div>
<div id="MySignature" role="contentinfo">
多抽出1分钟来学习，让你的生命更加精彩！ 
来源：https://www.cnblogs.com/AhuntSun-blog/p/12424949.html

頁: [1]

琼殿技术论坛's Archiver

JavaScript实现队列结构（Queue）