【JS算法与数据结构】队列的超长解析

前言

Hello大家好!在前两篇文章中介绍了数组和栈,今天一起来学习一下队列,队列遵循先进先出的原则,我们一起来看看。

队列数据结构

队列最常见的例子就是排队,排在前面的人最先享受服务,队列遵循的是FIFO原则,即先来先服务。队列在尾部添加新元素,在头部删除元素,最新添加的元素就是队尾元素。

class Queue{
    constructor(){
        this.count = 0; // {1}
        this.lowestCount = 0; // {2}
        this.items= {}; // {3}
    }
}

count属性用于控制队列的大小(行{1}),lowestCount变量用于辅助我们追踪第一个元素(最早的元素),此外我们还需要以下方法:

  • enqueue(element(s)):向队列尾部添加一个(或多个)新的项。
  • dequeue():移除队列的第一项(即排在队列最前面的项)并返回被移除的元素。
  • peek():返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与Stack类的peek方法非常类似)。该方法在其他语言中也可以叫作front方法。
  • isEmpty():如果队列中不包含任何元素,返回true,否则返回false。
  • size():返回队列包含的元素个数,与数组的length属性类似。

队列添加元素

根据先进先出原则,根据count来给items赋值,赋值后count+1来增加键的值:

enqueue(element){
    this.items[this.count] = element;
    this.count++;
}

队列移除元素

移除元素需要将最早的元素移除,需要用到我们定义的lowestCount:

dequeue(){
    if(this.isEmpty()){
        return undefined
    }
    const result = this.items[this.lowestCount] // {1}
    delete this.items[this.lowestCount] // {2}
    this.lowestCount++ // {3}
    return result // {4}
}

如果队列为空则返回undefined,否则获取该值(行{1})后删除(行{2}),lowestCount+1。

查看队列头元素

该方法返回队列最前面的项(把lowestCount作为键名获取元素)

peek(){
    if(this.isEmpty){
        return undefined
    }
    return this.items[this.lowestCount]
}

判断是否为空并获取长度

isEmpty(){
    return this.count - this.lowestCount ===0
}
size() { 
  return this.count - this.lowestCount; 
}

要计算队列有多少元素,只需要计算count和lowestCount的差值即可,因为lowestCount代表最早元素的键,count代表下一个最新的键。假设队列中count值为2,lowestCount值为0,这表示队列有两个元素,此时删除一个元素,lowestCount变为1,此时队列就只剩2-1个元素了。isEmpty也可改成下述方式:

isEmpty() { 
  return this.size() === 0; 
}

清空队列

清空可以用两种方式,一种是调用dequeue直到返回undefined即可,也可以重置队列的属性值。

clear(){
    this.items = {}
    this.count = 0
    this.lowestCount =0
}

toString方法

这个方法和之前栈的方法基本类似:

toString(){
    if(this.isEmpty()){
        return ''
    }
    let objString = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount +1 ;i<this.count;i++){
        objString = `${objString},${this.items[i]}`
    }
    return objString
}

完整代码

class Queue{
    constructor(){
        this.count = 0; // {1}
        this.lowestCount = 0; // {2}
        this.items= {}; // {3}
    }
enqueue(element){
this.items[this.count] = element;
this.count++;
}
dequeue(){
if(this.isEmpty()){
return undefined
}
const result = this.items[this.lowestCount] // {1}
delete this.items[this.lowestCount] // {2}
this.lowestCount++ // {3}
return result // {4}
}
peek(){
if(this.isEmpty){
return undefined
}
return this.items[this.lowestCount]
}
isEmpty(){
    return this.count - this.lowestCount ===0
}
size() { 
  return this.count - this.lowestCount; 
}
clear(){
this.items = {}
this.count = 0
this.lowestCount =0
}
toString(){
if(this.isEmpty()){
return ''
}
let objString = `${this.items[this.lowestCount]}`
for (let i = this.lowestCount +1 ;i<this.count;i++){
objString = `${objString},${this.items[i]}`
}
return objString
}
}

使用队列

const queue = new Queue(); 
console.log(queue.isEmpty()); // 输出 true
queue.enqueue('John'); 
queue.enqueue('Jack'); 
console.log(queue.toString()); // John,Jack
queue.enqueue('Camila');
console.log(queue.toString()); // John, Jack, Camila 
console.log(queue.size()); // 输出 3 
console.log(queue.isEmpty()); // 输出 false 
queue.dequeue(); // 移除 John 
queue.dequeue(); // 移除 Jack 
console.log(queue.toString()); // Camila

我们来看看这个过程都发生了什么事情,首先我们增加了三个元素:

之后出列两个元素:

最后打印就只剩Camila了。

双端队列数据结构

双端队列(deque,double-ended queue)是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

双端队列最经典的例子比如电影院买票,一个人买了票可能又回来问一下座位在哪?此时又会回到队伍头部,而我们如果等不及了,也可以离开队伍,不需要到我们了才离开。

在实际应用中,双端队列常用于存储一系列撤销操作。每当我们在网页进行了一个操作,操作被存储在双端队列中,当用户点击撤销按钮是,这个操作会从双端队列中弹出(从后面删除了),双端队列可看作栈和队列的结合,同时遵守了先进先出和后进先出原则。

创建Deque类

class Deque{
constructor(){
this.count = 0 
this.lowestCount = 0
this.items = {}
}
}

构造函数和一些方法如:isEmpty、clear、size和toString队列一样,区别在于移除元素和添加元素。

双端队列的方法:

  • addFront(element):该方法在双端队列前端添加新的元素。
  • addBack(element):该方法在双端队列后端添加新的元素(实现方法和 Queue类中的enqueue方法相同)。
  • removeFront():该方法会从双端队列前端移除第一个元素(实现方法和Queue类中的dequeue方法相同)。
  • removeBack():该方法会从双端队列后端移除第一个元素(实现方法和Stack类中的pop方法一样)。
  • peekFront():该方法返回双端队列前端的第一个元素(实现方法和Queue类中的peek方法一样)。
  • peekBack():该方法返回双端队列后端的第一个元素(实现方法和Stack类中的peek方法一样)。
addFront(element){
if(this.empty()){
this.addBack(element)
}else if(this.lowestCount>0){
this.lowestCount--
this.items[this.lowestCount] = element
}else{
for(let i=this.count;i>0;i--){
this.items[i] = this.items[i-1]
}
this.count++
this.items[0] = element
}
}

基本逻辑:首先判断队列是否为空,为空则count+1然后赋值即可,若不为空且lowestCount大于0,只需lowestCount-1,然后重新赋值即可,因为lowestCount减小了,count-lowestCount(队列的元素+1)。最后一种情况即lowestCount为0的时候,需要将所有元素后移一位,然后将首位的值设置为element,count+1。

完整代码

class Deque{
constructor(){
this.count = 0 
this.lowestCount = 0
this.items = {}
}
addFront(element){
if(this.isEmpty()){
this.addBack(element)
}else if(this.lowestCount>0){
this.lowestCount--
this.items[this.lowestCount] = element
}else{
for(let i=this.count;i>0;i--){
this.items[i] = this.items[i-1]
}
this.count++
this.items[0] = element
}
}
addBack(element){
this.items[this.count] = element
this.count++
}
removeFront(){
if(this.isEmpty()){
return undefined
}
const result = this.items[this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount++
return result
}
removeBack(){
if(this.isEmpty()){
return undefined
}
this.count--
const result = this.items[this.count]
delete this.items[this.count]
return result
}
peekFront(){
if(this.isEmpty()){
return undefined
}
return this.items[this.lowestCount]
}
peekBack(){
if(this.isEmpty()){
return undefined
}
return this.items[this.count-1]
}
isEmpty(){
    return this.count - this.lowestCount ===0
}
size() { 
  return this.count - this.lowestCount; 
}
clear(){
this.items = {}
this.count = 0
this.lowestCount =0
}
toString(){
if(this.isEmpty()){
return ''
}
let objString = `${this.items[this.lowestCount]}`
for (let i = this.lowestCount +1 ;i<this.count;i++){
objString = `${objString},${this.items[i]}`
}
return objString
}
}

使用双端队列

const deque = new Deque(); 
console.log(deque.isEmpty()); // 输出 true 
deque.addBack('John'); 
deque.addBack('Jack'); 
console.log(deque.toString()); // John, Jack 
deque.addBack('Camila'); 
console.log(deque.toString()); // John, Jack, Camila 
console.log(deque.size()); // 输出 3 
console.log(deque.isEmpty()); // 输出 false 
deque.removeFront(); // 移除 John 
console.log(deque.toString()); // Jack, Camila 
deque.removeBack(); // Camila 决定离开 
console.log(deque.toString()); // Jack 
deque.addFront('John'); // John 回来询问一些信息 
console.log(deque.toString()); // John, Jack

这里有一空队列,此时队列为空,John, Jack 分别加入队列,此时队列打印为John, Jack ;不久Camila也加入队列买票,John买完票离开,此时队伍不为空,Camila等着太久了所以决定离开,队伍只剩Jack;John买完票后回来询问问题,队伍变为:John, Jack。

实际应用

我们已经了解了队列和双端队列,现在来试着解决一些现实生活中的问题。

击鼓传花

不知道大家有没有玩过击鼓传花,GIS宇宙之前参加支教经常会玩这个,可以加深和小朋友的互动。击鼓传花的规则很简单,就是所有人都围成一个圈,把手里的花,某一时刻鼓声停止,花在谁那就退出游戏,重复游戏直到只剩一个人成为胜者。

function hotPotato(elementsList, num) { 
  const queue = new Queue(); // {1} 
  const elimitatedList = []; 
 
  for (let i = 0; i < elementsList.length; i++) { 
    queue.enqueue(elementsList[i]); // {2} 
  } 
 
  while (queue.size() > 1) { 
    for (let i = 0; i < num; i++) { 
      queue.enqueue(queue.dequeue()); // {3} 
    } 
    elimitatedList.push(queue.dequeue()); // {4} 
  } 
 
  return { 
    eliminated: elimitatedList, 
    winner: queue.dequeue() // {5} 
  }; 
}

构建hotPotato函数,这里我们简化了击鼓传花的流程,用elementsList, num参数分别表示记录玩家姓名的数组和传花的次数(行{1});函数中新建一个队列和一个数组elimitatedList记录淘汰的元素,首先循环将玩家加入队列中,首先循环传花次数,每次传花则把头部元素添加到尾部(行{3}),完成传花后,此时花在头部元素手中,将此时的头部元素移除并添加进淘汰数组中,继续循环直到决出胜者(行{4}),最后函数返回淘汰数组和胜者。

const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']; 
const result = hotPotato(names, 7);
result.eliminated.forEach(name => { 
  console.log(`${name}在击鼓传花游戏中被淘汰。`); 
}); 
 
console.log(`胜利者: ${result.winner}`);

以上算法的输出如下。
Camila 在击鼓传花游戏中被淘汰。
Jack 在击鼓传花游戏中被淘汰。
Carl 在击鼓传花游戏中被淘汰。
Ingrid 在击鼓传花游戏中被淘汰。
胜利者:John
具体流程图:
红色的数字代表第几次传递,因为传花的次数大于玩家人数,每传完当前所有玩家记为一轮,蓝色数字代表第二轮传递,在传递完第七次时,Camila拿到了花,因此Camila被淘汰,剩下的人继续游玩,重复上述操作到只剩一人即为胜者。

回文检查器

下面是维基百科对回文的解释。

回文是正反都能读通的单词、词组、数或一系列字符的序列,例如 madam 或 racecar。

基本思路就是判断头部元素和尾部元素是否相同,相投则头尾去掉,重复判断,下面看具体代码:

function palindromeChecker(aString) { 
  if (aString === undefined || aString === null || 
    (aString !== null && aString.length === 0)) { // {1} 
    return false; 
  } 
  const deque = new Deque(); // {2} 
  const lowerString = aString.toLocaleLowerCase().split(' ').join(''); // {3} 
  let isEqual = true; 
  let firstChar, lastChar; 
 
  for (let i = 0; i < lowerString.length; i++) { // {4} 
    deque.addBack(lowerString.charAt(i)); 
  } 
 
  while (deque.size() > 1 && isEqual) { // {5} 
    firstChar = deque.removeFront(); // {6} 
    lastChar = deque.removeBack(); // {7} 
    if (firstChar !== lastChar) { 
      isEqual = false; // {8} 
    } 
  } 
 
  return isEqual; 
}

首先我们需要对字符串输入进行判断,必须是非空字符串才行(行{1})。然后新建一个双端队列,将字符串转化成小写的字符串(行{2});isEqual表示firstChar,lastChar是否相同,轮换字符串添加进双端队列中,当队列只有一个字符的时候满足回文返回true,当大于2个字符时,我们分别取firstChar,lastChar进行判断,如果相同则继续直到只剩一个中间字符则判断是回文,期间不相同则退出循环,判断不是回文。

console.log('a', palindromeChecker('a')); 
console.log('aa', palindromeChecker('aa')); 
console.log('kayak', palindromeChecker('kayak')); 
console.log('level', palindromeChecker('level')); 
console.log('Was it a car or a cat I saw',palindromeChecker('Was it a car or a cat I saw')); 
console.log('Step on no pets', palindromeChecker('Step on no pets'));

返回结果:
a true
aa true
kayak true
level true
Was it a car or a cat I saw true
Step on no pets true

JavaScript事件循环

如果继续下去,本文写的太长啦,SO这一块就放在下次再说吧(其实是自己还没有深入学习)

总结

通过本文,你可以对队列有一个很清晰的了解,相比栈来说,队列遵守的是先进先出,类比排队买票,总有人会回到队伍的前面问问题;然后是双端队列,它类似栈和队列的结合,可以先进先出,也可先进后出。

学习自书籍:

学习JavaScript数据结构与算法第三版 Learning JavaScript Data Structures and Algorithms 3rd Edition ([巴西]格罗纳(LoianeGroner), 孙晓博, 邓钢, 吴双, 陈迪, 袁源) (z-lib.org)

本人其他平台账号:

  • 微信公众号:GIS宇宙
  • CSDN:GIS_宇宙
  • 知乎:GIS宇宙
  • 掘金:GIS宇宙
© 版权声明
THE END
喜欢就支持一下吧
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容