JavaScript队列结构Queue实现过程解析

来自:互联网
时间:2020-03-07
阅读:

一、队列简介

队列是是一种受限的线性表,特点为先进先出(FIFO:first in first out)。

受限之处在于它只允许在表的前端(front)进行删除操作;在表的后端(rear)进行插入操作;

相当于排队买票,先来的先买票,后来的后买票。

队列的应用:

打印队列:计算机打印多个文件的时候,需要排队打印;线程队列:当开启多线程时,当新开启的线程所需的资源不足时就先放入线程队列,等待CPU处理;

队列类的实现:

队列的实现和栈一样,有两种方案:

基于数组实现;基于链表实现;

队列的常见操作:

  • enqueue(element):向队列尾部添加一个(或多个)新的项;
  • dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素;
  • front():返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与Stack类的peek方法非常类似);
  • isEmpty():如果队列中不包含任何元素,返回true,否则返回false;
  • size():返回队列包含的元素个数,与数组的length属性类似;
  • toString():将队列中的内容,转成字符串形式;

二、封装队列类

2.1.代码实现

  // 基于数组封装队列类
  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[0]
  }

  // 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
   }
  }

测试代码:

  // 创建队列
  let queue = new Queue()

  // 将元素加入到队列中
  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

测试结果:

2.2.队列的应用

使用队列实现小游戏:击鼓传花,传入一组数据和设定的数字num,循环遍历数组内元素,遍历到的元素为指定数字num时将该元素删除,直至数组剩下一个元素。

代码实现:

  // 队列应用:面试题:击鼓传花
  let passGame = (nameList, num) => {
   //1.创建队列结构
   let queue = new Queue()

   //2.将所有人依次加入队列
   // 这是ES6的for循环写法,i相当于nameList[i]
   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

测试结果:

三、优先队列

优先级队列主要考虑的问题为:

每个元素不再只是一个数据,还包含数据的优先级;在添加数据过程中,根据优先级放入到正确位置;3.1.优先级队列的实现

代码实现:

  // 封装优先级队列
  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[0]
   }

   // 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
    }
  }

测试代码:

  // 测试代码
  let pq = new PriorityQueue();
  pq.enqueue('Tom',111);
  pq.enqueue('Hellen',200);
  pq.enqueue('Mary',30);
  pq.enqueue('Gogo',27);
  // 打印修改过后的优先队列对象
  console.log(pq);

测试结果:

3.2.注意点

关于数组方法splice用法:

splice(1,0,'Tom'):表示在索引为1的元素前面插入元素'Tom‘(也可以理解为从索引为1的元素开始删除,删除0个元素,再在索引为1的元素前面添加元素'Tom');

splice(1,1,'Tom'):表示从索引为1的元素开始删除(包括索引为1的元素),共删除1个元素,并添加元素'Tom'。即把索引为1的元素替换为元素'Tom'。

数组的push方法在数组、栈和队列中的形式:

  • 数组:在数组[0,1,2]中,pop(3),结果为[0,1,2,3];
  • 栈:执行pop(0),pop(1),pop(2),pop(3),从栈底到栈顶的元素分别为:0,1,2,3;如果看成数组,可写为[0,1,2,3],但是索引为3的元素3其实是栈顶元素;所以说栈的push方法是向栈顶添加元素(但在数组的视角下为向数组尾部添加元素);
  • 队列:enqueue方法可以由数组的push方法实现,与数组相同,相当于在数组尾部添加元素。

可以这样想:栈结构是头朝下(索引值由下往上增大)的数组结构。

返回顶部
顶部