佇列其資料結構用圖片來說明大概如下:

資料以一列的方式儲存每個資料，而且刪除節點時會從最前面也是最早加入佇列的資料開始刪除，新增節點從佇列尾巴開始刪除。此為佇列 先進先出（FIFO, First-In-First-Out） 的特性。

佇列只允許在後端（稱為Rear）進行插入操作，在前端（稱為Front）進行刪除操作

佇列的兩種操作函式：

• enqueue(adding, offering)：將資料放入佇列尾端
• dequeue(polling)：取出佇列前端之資料

常見範例:

• 人們排隊
• 寫入磁碟的資料先儲存在電腦的記憶體緩衝區中
• Breadth-First Search(BFS，廣度優先搜尋)

對於佇列有初步了解後，我們來實作吧!這裡使用 Linked List 當作基礎的資料結構去做實作。

先定義出Queue類別及它的節點

class QueueNode {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

class Queue {
  constructor() {
    this.front = null
    this.tail = null
  }

  // 判斷佇列是否為空，直接判斷最前面節點是否為空即可
  isEmpty() {
    return this.front === null
  }

  // 新增節點
  enqueue(value) {

  }

  // 移除節點
  dequeue() {

  }
}

完成 enqueue() 函式:

邏輯相當的簡單，記得是從尾巴新增節點喔~

enqueue(value) {
  let node = new QueueNode(value)
  if (this.isEmpty()) {
    this.front = node
    this.tail = node
  } else {
    // 讓尾巴節點先指向node新節點
    this.tail.next = node
    // 讓新節點變成新的尾巴節點
    this.tail = node
  }
}

完成 dequeue() 函式:

將原本前面第二個節點變成第一個節點即可

dequeue() {
  let result = this.front.data
  // 空佇列的狀況
  if (this.isEmpty()) {
    return null
  }

  if (this.front === this.tail) { // 變成空佇列
    this.front = null
    this.tail = null
  } else {
    // 使原本前面第二個節點變成第一個節點
    this.front = this.front.next
  }

  return result
}

最後建立 qq 物件，並使用enqueue()和dequeue()進行操作

let qq = new Queue()
qq.enqueue("A")
qq.enqueue("B")
qq.enqueue("C")
qq.enqueue("D")
qq.enqueue("E")

while (!qq.isEmpty()) {
    console.log(qq.dequeue()) // A B C D E
}

佇列的時間複雜度

可參考 Time and Space Complexity of Queue

這次文章的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day8-queue.js

以上就是這次關於佇列的介紹，明天我們將用佇列解決一個找質數問題!