JS数据结构与算法之队列结构

﹏ヽ暗。殇╰゛Y 2024-03-25 07:06 63阅读 0赞

### 认识队列结构 ###

队列结构它是一种受限的线性表，队列结构先进先出first in first out

![202859378098e34ecfdf7cb76dcf7435.png][]

#### 程序中对队列的使用 ####

*  打印队列：计算机打印多个文件的时候，需要排队打印；

*  线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待CPU处理；

#### **队列类的实现** ####

队列的实现和栈一样，有两种方案：

*  基于数组实现；

*  基于链表实现；

#### **队列的常见操作** ####

*  enqueue（element）：向队列尾部添加一个（或多个）新的项；

*  dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；

*  front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与Stack类的peek方法非常类似）；

*  isEmpty（）：如果队列中不包含任何元素，返回true，否则返回false；

*  size（）：返回队列包含的元素个数，与数组的length属性类似；

*  toString（）：将队列中的内容，转成字符串形式；

### js队列结构的封装 ###

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

### 队列结构解决击鼓传花面试题 ###

传入一组数据和设定的数字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());                                    
          let endName = queue.front()
          console.log('最终剩下的人：' + endName);                             
          
          return nameList.indexOf(endName);
        }
    
        //5.测试击鼓传花
        let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony']
        console.log(passGame(names, 3));

### 优先级队列 ###

特点：普通队列插入一个元素数据会被放在后端并且需要前面所有的元素都处理完成后才会处理前面的数据，但是优先级队列在插入一个元素的时候会考虑该数据的优先级，和其他数据优先级进行比较，比较完成后可以得到这个元素在队列中正确的位置，其他处理方式和基本队列的处理方式一样。

#### 程序中对优先级队列的使用 ####

每个线程处理的任务重要性不同，我们可以通过优先级的大小来决定该线程在队列中被处理的次序

### js优先级队列的封装 ###

实现优先级队列主要考虑两方面：封装元素和优先级应该绑定；添加元素时要将新插入元素的优先级和队列中已经存在的元素优先级进行比较从而获得自己正确的位置

// 封装优先级队列
        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);

**关于数组方法splice用法**：

*  splice（1，0，'Tom'）：表示在索引为1的元素前面插入元素’Tom‘（也可以理解为从索引为1的元素开始删除，删除0个元素，再在索引为1的元素前面添加元素'Tom'）；

*  splice（1，1，'Tom'）：表示从索引为1的元素开始删除（包括索引为1的元素），共删除1个元素，并添加元素'Tom'。即把索引为1的元素替换为元素'Tom'。

[202859378098e34ecfdf7cb76dcf7435.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ff3f934c1e2c4a538cbf80bc859565c5.png