前端堆棧存儲：深入理解與應用詳情 - 堆棧,深度優先搜索,Stack,JavaScript,前端開發轉角處的湯姆博客

在前端開發中，堆棧存儲（Stack Storage）是計算機科學中的一個基本概念，它在許多編程場景中都有着廣泛的應用，尤其是在處理函數調用、遞歸操作以及維護數據的順序時，堆棧起着至關重要的作用。

本文將帶你深入瞭解前端堆棧存儲的概念、實現方式，以及在實際開發中的應用。

1. 什麼是堆棧？

堆棧（Stack）是一種遵循後進先出（LIFO, Last In First Out）原則的數據結構。堆棧的基本操作包括：

Push：將元素壓入堆棧頂部
Pop：從堆棧頂部移除元素
Peek：查看堆棧頂部的元素
isEmpty：判斷堆棧是否為空

堆棧在計算機科學中應用廣泛，特別是在處理函數調用和遞歸時。你可以將堆棧想象成一個“疊盤子”的過程，每次你將一個新的盤子放在上面，而取盤子時是從上面開始取。

2. 堆棧的工作原理

堆棧是一種簡單的數據結構，主要操作是從頂部添加或刪除元素。為了理解堆棧如何工作，首先來看一個簡單的例子：

假設我們有一個空堆棧，並依次進行以下操作：

Push(1)：堆棧變為 [1]
Push(2)：堆棧變為 [1, 2]
Push(3)：堆棧變為 [1, 2, 3]
Pop()：從堆棧移除頂部元素，堆棧變為 [1, 2]
Peek()：查看堆棧頂部元素，結果是 2

在這個過程中，我們可以看到堆棧總是操作頂部的元素，最後被加入堆棧的元素會最先被移除。

3. 在前端中使用堆棧存儲

在前端開發中，堆棧經常用於以下幾種場景：

3.1 函數調用棧

每當一個函數被調用時，JavaScript 引擎會將該函數的執行上下文（函數參數、局部變量等）壓入調用棧。當函數執行完畢，棧頂的上下文會被彈出。函數調用棧是堆棧最典型的應用。

function first() {
  console.log("First");
}

function second() {
  console.log("Second");
  first();
}

second();

在這個例子中，second 函數首先被調用，接着調用 first 函數。堆棧的變化過程如下：

調用 second()，將其上下文壓入棧
調用 first()，將其上下文壓入棧
first() 執行完畢，彈出其上下文
second() 執行完畢，彈出其上下文

3.2 深度優先搜索（DFS）

堆棧還可以用來實現深度優先搜索（DFS）算法，常用於圖或樹的遍歷。

例如，假設我們有一個樹狀結構，我們可以通過堆棧來實現深度優先搜索：

function dfs(graph, startNode) {
  const stack = [startNode];
  const visited = new Set();

  while (stack.length) {
    const node = stack.pop();
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      stack.push(...graph[node]);  // 將鄰接節點壓入堆棧
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: [],
  F: []
};

dfs(graph, 'A');

在上面的例子中，我們使用堆棧來管理樹的遍歷順序，確保每次訪問的節點是最新壓入棧的節點。

3.3 瀏覽器歷史棧

瀏覽器的歷史記錄也是基於堆棧實現的。當用户訪問頁面時，瀏覽器將頁面地址壓入歷史棧。當用户點擊瀏覽器的後退按鈕時，瀏覽器會彈出歷史棧的頂部元素，並加載對應的頁面。

window.history.pushState({}, "Page 1", "/page1");
window.history.pushState({}, "Page 2", "/page2");

window.history.back(); // 瀏覽器會回到 "/page1"

4. 堆棧的常見應用

除了函數調用棧、深度優先搜索和瀏覽器歷史棧，堆棧還在以下場景中有着廣泛應用：

4.1 表達式求值

在計算機中，堆棧常用於實現四則運算的逆波蘭表達式（Postfix Expression）的計算。通過堆棧可以將運算符與操作數分開，按正確的順序計算表達式。

4.2 括號匹配

堆棧也常用於括號匹配問題。在編程語言中，括號必須配對且嵌套正確。可以利用堆棧來檢查字符串中的括號是否有效。

function isValid(s) {
  const stack = [];
  const map = { '(': ')', '{': '}', '[': ']' };

  for (const char of s) {
    if (map[char]) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (map[last] !== char) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

console.log(isValid("()")); // true
console.log(isValid("{[()]}")); // true
console.log(isValid("([)]")); // false

4.3 撤銷與重做

在許多前端應用中，比如文本編輯器或圖形設計工具，堆棧用於實現撤銷和重做功能。每當用户執行一個操作時，將當前狀態壓入堆棧中，執行撤銷時就從堆棧中彈出上一個狀態。

5. 手寫一個簡單的堆棧類

下面是一個簡單的堆棧實現，包含了常見的 push、pop、peek 和 isEmpty 操作：

class Stack {
  constructor() {
    this.items = [];
  }

  // 壓入元素
  push(element) {
    this.items.push(element);
  }

  // 彈出元素
  pop() {
    return this.items.pop();
  }

  // 查看堆棧頂部元素
  peek() {
    return this.items[this.items.length - 1];
  }

  // 判斷堆棧是否為空
  isEmpty() {
    return this.items.length === 0;
  }

  // 返回堆棧的大小
  size() {
    return this.items.length;
  }

  // 清空堆棧
  clear() {
    this.items = [];
  }

  // 輸出堆棧元素
  print() {
    console.log(this.items.toString());
  }
}

// 使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack.peek()); // 30
stack.pop();
console.log(stack.peek()); // 20
stack.print(); // 10,20