用 JavaScript 實作堆疊（Stack）

（2026/08/18 更新內容）

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

---

預備知識

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

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

什麼是 Stack？

資料像紙本文件由下往上堆疊一樣，只能從最新追加的資料開始存取。

後追加的數據先取出的特性是 「後進先出」，即「Last In First Out」縮寫「LIFO」。

source: Stack (abstract data type) - Wikipedia

---

解說

應用

Stack 的特性就是取得最新的資料，所以有這種需求的應用會適合用 stack 來處理，例如：

• 瀏覽器的 call stack
• Undo / Redo 功能
• 歷史紀錄

實作

JavaScript 本來就具有 Array 這個 data type，其實就可以直接拿來實現 stack，像是利用 array 的 push 放入 data 到最後一個 index，要取出時用 pop 就可取出最新的 data。

let stack = [];
stack.push(0);
stack.push(1);
stack.push(2);

stack.pop();

由於 push 和 pop 兩個 method 都是變動 array 最後面的元素，不會改變 array 裡其他元素的順序，因此 Big O 是 O(1)。

---

Object Property

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

node 具有：

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

Stack 具有：

• first node
• last node
• size

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

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

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

Object Method

Doubly Linked List 具有以下 method：

• Pushing
• Popping

Pushing

push 即增加一個 node 到 stack 的最前面的位置

Pseudocode：

1. function 要接收一個 value
2. 利用 function 接收的 value 來建立一個新的 node
3. 如果 stack 沒有 node，則把 first 與 last 都設為剛建立的新 node
4. 如果 stack 裡有 node 的話
   • 新 node 的 next 設為 first
   • 把 first 設為新 node
5. 將 stack 的 size 增加 1

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

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

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

Popping

pop 是將 stack 最後一個加入的 node 拿出來

Pseudocode：

1. 如果 stack 沒有 node，則 return null
2. 如果 stack 有 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 Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  ...

  pop() {
    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;
  }
}

---

總結

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

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

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

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

  pop() {
    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;
  }
}

Stack 的 Big O

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

Stack 的追加和刪除資料都是從 first 開始處理，只要處理兩個 node 之間的關聯即可，效率很高是 O(1)。

但存取資料就不是 stack 的強項，如果要搜尋某個 node，就需要像 Singly Linked List 從頭開始一個接一個的 next 下去，所以若有這種功能的需求，應該優先考慮其他種資料結構。

Ref

• JavaScript (JS) Algorithms and Data Structures Masterclass | Udemy
• Stack (abstract data type) - Wikipedia