佇列的定義

佇列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行洗掉操作，而在表的后端（rear）進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行洗掉操作的端稱為隊頭，

佇列的方法

1. enqueue(element):向佇列尾部添加一個(或多個)新的項，
2. dequeue()︰移除佇列的第一（即排在佇列最前面的）項，并回傳被移除的元素，
3. front():回傳佇列中第一個元素__最先被添加，也將是最先被移除的元素， 佇列不做任何變動(不移除元素只回傳元素資訊-與Stack類的peek方法非常類似)，
4. isEmpty():如果佇列中不包含任何元素，回傳true，否則回傳false，
5. size():回傳佇列包含的元素個數，與陣列的length屬性類似，
6. toString():將佇列中的內容,轉成字串形式

佇列的簡單封裝

    // 佇列的封裝 先進先出 
    function Queue (element) {
      // 屬性
      this.items = []
      // 方法     
      // 1. 將元素加入佇列
      Queue.prototype.enqueue = function (element) {
        this.items.push(element)
      }
      // 2. 從佇列取出前端元素并洗掉
      Queue.prototype.dequeue = function () {
        return this.items.shift()
      }
      // 3. 查看一下前端元素
      Queue.prototype.front = function () {
        return this.items[0]
      }
      // 4. 判斷佇列是否為空
      Queue.prototype.isEmpty = function () {
        return this.items.length === 0
      }
      // 5. 獲取佇列中元素的個數
      Queue.prototype.size = function () {
        return this.items.length
      }
      // 6. toString 方法
      Queue.prototype.toString = function () {
        return this.items.join(' ')
      }
    }

呼叫

	let q = new Queue()
	q.enqueue('地區烏當區')
	q.enqueue('地區烏')
	q.enqueue('地區烏23')
	q.enqueue(123)
	q.enqueue(1)
	alert(q)
	alert(q.dequeue())
	alert(q.front())
	alert(q.isEmpty())
	alert(q.size())
	alert(q.toString()) 

面試題 --> 擊鼓傳花

  // 擊鼓傳花
    function passGame (nameList, num) {
      // 1. 創建一個佇列
      let queue = new Queue()
      // 2. 把所有人依次添加到佇列
      for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
      }
      /* 3. 開始數數字
            不是nam的時候,重新添加到佇列的末尾
            是num數字的時候,將其在佇列中洗掉
         3.1 num數字之前的重新放入到佇列的末尾
      */
     while (queue.size() > 1) { 
      for (let i = 0; i < num - 1; i++) {
        queue.enqueue(queue.dequeue())
      }
      // 3.2 num對于的數字洗掉
      queue.dequeue()
     }
      // 4. 獲取剩下的那個人
      // alert(queue.size())
      let endName = queue.front()
      alert('最后剩下的人是: ' + endName)
      return nameList.indexOf(endName)
    }
    let arr = ['Lily', 'Lucy', 'Tom', 'Lilei', 'Why']
    alert(passGame(arr, 3))

圖解

優先佇列的實作

      // 封裝優先級佇列
      function ProorityQueue () {
        // PriorityQueue里創建一個類: 內部類
        function QueueElement (element, priority) {
          this.element = element
          this.priority = priority
        }
        // 封裝屬性
        this.items = []

        ProorityQueue.prototype.enqueue = function (element, priority) {
          // 創建QueueElement物件
          let queueElement = new QueueElement(element, priority)
          // 陣列沒有元素時不用比較直接添加
          if (this.items.length === 0) {
            this.items.push(queueElement)
          } else {
            let added = false
            // 遍歷元素進行比較
            for (let i = 0 ; i < this.items.length ; i++) {
              // 判斷優先級
              if (queueElement.priority < this.items[i].priority) {
                this.items.splice(i, 0, queueElement)
                added = true
                break;
              }
            }
            if (!added) {
              this.items.push(queueElement)
            }
          }
        }
        // 2. 從佇列取出前端元素并洗掉
        ProorityQueue.prototype.dequeue = function () {
          return this.items.shift()
        }
        // 3. 查看一下前端元素
        ProorityQueue.prototype.front = function () {
          return this.items[0]
        }
        // 4. 判斷佇列是否為空
        ProorityQueue.prototype.isEmpty = function () {
          return this.items.length === 0
        }
        // 5. 獲取佇列中元素的個數
        ProorityQueue.prototype.size = function () {
          return this.items.length
        }
        // 6. toString 方法
        ProorityQueue.prototype.toString = function () {
          // return this.items.join(' ')
          let str = ''
          this.items.forEach((item, i) => {
            str += item.element + ' ' + item.priority + '--  '
          })
          return str
        }
      }