数据结构–队列（笔记）-一一网

1，队列的简介：

队列是一种特殊的线性表，特殊之处在于它：

只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO）线性表。

queue.jfif

2，队列的一些操作方法：

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

3，封装上述方法：


 //封装上述方法：
 
     function Queue(){
        this.items = []
         // enqueue 向队尾添加元素
         Queue.prototype.enqueue = function(element){
            this.items.push(element)
         }
         //dequeue 移除队列第一个元素  
         Queue.prototype.dequeue = function(){
            return this.items.shift()
         }
         //front 返回第一个元素
         Queue.prototype.front = function(){
            return this.items[0]
         }
         //isEmpty 判断是否为空
         Queue.prototype.isEmpty = function(){
            return this.items.length==0
         }

         //size 返回元素的个数
         Queue.prototype.size = function(){
            return this.items.length
         }

         // toString 转为字符串
         Queue.prototype.toString = function(){
            this.items.join(',')
         } 
     }
     // var queue = new Queue()
     // queue.enqueue('1')
     // queue.enqueue('2')
     // queue.enqueue('3')
   
     // queue.dequeue()
     // console.log(queue.items)
	
复制代码

4，应用：

把火车站当成一个队列。火车进站的时候（同轨道的车次），先进站的火车，先发车。符合队列的先进先出的特点。
把餐厅当成一个队列。餐厅的就餐人员，先进去吃饭，先出来。

5，练习题：

ABCDEF 6个元素依次进入一个队列，以下出队列的情况是（）？

(1) ABCDEF
(2) ABDCFE
(3) BAFEDC
(4) ABCFED

6，面试题

题目要求：例如编号为A、B、C、D、E、F，6人围绕桌子（顺时针）坐着，裁判说出一个数，这个数就是ABCDEF6人需要报的数，依次报数（比如裁判说的这个数是3，那么A报数1，B报数2,…），当报到该数字时，该人淘汰，淘汰这个人的下一位,重新从1报数（按照桌子围绕），直到剩下最后一人，为获胜者。


   //需要用到上述的封装的方法。自取。
   
   function passGame(nameList,num){
        //1，建立一个队列
        var newQueue = new Queue();

         // 2，加入队列
        for(var i=0;i<nameList.length;i++){
            newQueue.enqueue(nameList[i])
        }

        // 3，如果该队列中的元素大于1，就一直进行游戏
        // 3-1，不是num的时候，重新加入到队列中(先出队列，然后加入队列的末尾)
        while(newQueue.size()>1){
            for(var i=0;i<num-1;i++){
               newQueue.enqueue(newQueue.dequeue())
           }
         
           // 3-2，是num的时候，将其从队列中删除
            newQueue.dequeue()
        }
        var endName = newQueue.front()
         console.log(endName)

        return nameList.indexOf(endName)   //返回最后一个元素的下标

    }
         // 4， 验证：
          var names =  ['tom','jack','lili','lucy','merry','zhangsan','lisi','wangwu']
          console.log(passGame(names,5))  
   

复制代码