用 JavaScript 實作佇列(Queue)

2021-12-11 · 5 min read

如先前文章所言,本系列文章會以 JavaScript 學習演算法與資料結構為主題來撰寫。

本系列主要參考自以下資料:

  • 石田保輝宮崎修一演算法圖鑑
  • Colt SteeleJavaScript Algorithms and Data Structures Masterclass

此外,如果想以圖像的方式了解資料結構及演算法,也很推薦參考 VisuAlgo

預備知識

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

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

以上內容不會在本文說明,如果想了解可以參考以下外部連結

另外我有寫過 Singly Linked List 的文章,可以參考

什麼是 Queue?

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

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

Queue source: http://www.fgchen.com


解說

應用

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
資料結構 樹 (Tree)用 JavaScript 實作堆疊(Stack)

Comment