Queue 列隊

跟買電影票一樣，後來的人會排在隊伍後面，先買到票的人，會先離開。

特性

• 先進先出 FIFO(first in first out)，跟排隊買電影票的概念一樣。
• 元素沒有 index。
• 元素的新增只能從 queue 的後方。
• 元素的移除只能從 queue 的前方。
• enqueue 意思是新增項目進 queue，dequeue 意思是移除 queue 內的項目。

使用 Linked List 實作 Stack

在 Queue 的概念中，我們建立的 Linked List 只能使用 push, shift 方法，不能使用 shift, unshift, insertAt, removeAt。

要實作的方法： push：在隊伍後方新增元素 shift：把隊伍前方的元素移除

function Node(value) {
  return {
    value,
    next: null
  }
}

function Queue() {
  let head = null
  let length = 0
  // 在隊伍後方新增元素
  const push = (value) => {
    const newNode = Node(value)
    if (head === null) { head = newNode }
    else {
      let currentNode = head
      while (currentNode.next !== null)
        currentNode = currentNode.next

      currentNode.next = newNode
    }

    length++
  }
  // 把隊伍前方的元素移除
  const shift = () => {
    if (head === null)
      return null
    if (length === 1) {
      const node = head
      head = null
      length = 0
      return node
    }
    head = head.next
    length--
  }

  const printAll = () => {
    if (head === null) {
      console.log('Nothing in this linked list')
      return
    }

    let currentNode = head
    while (currentNode !== null) {
      console.log(currentNode.value)
      currentNode = currentNode.next
    }
  }

  return {
    head,
    length,
    push,
    shift,
    printAll
  }
}

const myQueue = Queue()
myQueue.push('Mike')
myQueue.push('Harry')
myQueue.push('James')
myQueue.shift()
myQueue.printAll()

印出結果： Harry James

Queue 觀念練習題

以下會提供一系列的運算，請試著回答問題：

1. 當題目的運算都結束後，queue 內還有幾個項目？
2. queue 的尾巴（tail）是什麼？
3. queue 的頭（head）是什麼？

enqueue pencil
enqueue pen
enqueue stapler
enqueue phone
dequeue 
dequeue 
enqueue tablet
enqueue notes
dequeue

答案

最後 stack 會剩下三個元素

(tail) notes tablet phone (head)

3 個
notes
phone

LeetCode 練習題

225. Implement Stack using Queues

補充：Dequeue 雙向佇列

也可以寫作 deque，雙向佇列（doubled-ended queue），也是 statck 與 queue 的綜合體。

特性

• 前後都可以新增元素
• 前後都可以移除元素