跳至主要内容

用 JavaScript 實作佇列（Queue）

· 閱讀時間約 4 分鐘
阿昇
阿昇
Software Engineer

（2026/08/18 更新內容）

此篇為舊文章，我已經另外整理資料結構與演算法的筆記，可以參考資料結構與演算法。

預備知識​

了解本文內容之前需要具備的 prerequisite：

  • JavaScript 基礎知識及 ES6 語法
  • 物件導向觀念
  • Big O Notation
  • 資料結構的基礎理解
  • 資料結構 Singly Linked List

什麼是 Queue？​

資料像排隊一樣，在隊伍（Queue）中，最晚到的會排在最後面，處理資料則會從最先排入的開始進行。

先追加的數據先處理的特性是 「先進先出」，即「First In First Out」縮寫「FIFO」。

解說​

應用​

Queue 的特性就是依序處理資料，舊的資料優先處理是很直觀的事情，使用情境如：

  • 背景執行的工作
  • 上傳資料
  • 列印
  • 注重先後順序的待辦事項

實作​

JavaScript 本來就具有 Array 這個 data type，其實就可以直接拿來實現 queue，像是利用 array 的 push 放入 data 到最後一個 index，要取出資料時用 shift 就可取出之前最先加入的 data。

let queue = [];
queue.push(1);
queue.push(2);
queue.push(3);

queue.shift();

push 這個 method 的 Big O 是 O(1)，但是 shift 這個 method 會改變 array 裡其他元素的順序，因此 Big O 是 O(n)。

Object Property​

這部分用物件導向的方式來實作，一個 queue 由數個 node 組成，他們各自是一種 object。

node 具有：

  • value
  • pointer to next node（指向下一個 node 或 null）

Queue 具有：

  • first node
  • last node
  • size

因此可以用 OOP 物件導向的方式來定義他們：

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

Object Method​

Doubly Linked List 具有以下 method：

Enqueue​

enqueue 是增加 node 到 queue 的最前面

Pseudocode：

  1. function 要接收一個 value
  2. 利用 function 接收的 value 來建立一個新的 node
  3. 如果 queue 沒有 node，則把 first 與 last 都設為剛建立的新 node
  4. 如果 queue 裡有 node 的話
    • last 的 next 設為新 node
    • 把 last 設為新 node
  5. 將 queue 的 size 增加 1
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val) {
    const newNode = new Node(val);
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.size++;
  }
}

Dequeue​

dequeue 是將 queue 最前面的 node 取出

Pseudocode：

  1. 如果 queue 沒有 node，則 return null
  2. 如果 queue 有 node
    • 把 first 放入一個新變數 target node
    • 如果 first 和 last 是同一個 node，則設 last 為 null
    • 將 target node 的 next 設為新的 first
    • stack 的 size 減 1
    • return target node 的 value
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  ...

  dequeue() {
    if (this.size === 0) return null;
    const targetNode = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = targetNode.next;
    this.size--;
    return targetNode.val;
  }
}

總結​

最終關於 Queue 的定義會是這樣：

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val) {
    const newNode = new Node(val);
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.size === 0) return null;
    const targetNode = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = targetNode.next;
    this.size--;
    return targetNode.val;
  }
}

Queue 的 Big O​

  • Insertion - O(1)
  • Removal - O(1)
  • Searching - O(N)
  • Access - O(N

和 stack 一樣，queue 的追加和刪除資料 O(1)，因為這兩個 method 都只要處理兩個 node 之間的關聯。

Ref​