棧的全面解析：ADT、實現與應用
一、棧的基礎概念與ADT
棧是一種先進後出（FILO, First In Last Out）的線性數據結構，它就像現實生活中堆疊的盤子，只能從頂部添加或移除元素。在計算機科學中，棧的"棧頂"是唯一可操作的位置，而"棧底"固定不動。
作為抽象數據類型（ADT），棧提供了一組標準操作：
- push：向棧頂添加元素
- pop：移除並返回棧頂元素
- peek：查看棧頂元素但不移除
- isEmpty：判斷棧是否為空
- size：獲取棧中元素數量
這些操作確保了棧的"後進先出"特性，使其在程序執行、表達式求值、括號匹配等場景中發揮着關鍵作用。
二、數組實現棧
數組是開箱即用的線性數據結構。在JavaScript中數組的相關操作：
// 在JavaScript數組的相關操作
const arr = [1,2,3];
arr.push(4); // 尾部添加
arr.unshift(0); // 頭部添加
console.log(arr); // [0,1,2,3,4]
arr.pop(); // 彈出尾部元素
arr.shift(); // 彈出頭部元素
console.log(arr); // [1,2,3]在用數組實現棧之前我們先了解以下知識：
ES6引入的class語法為實現棧提供了優雅的解決方案。通過class，我們可以創建一個類模板，封裝棧的所有屬性和方法。
es6引入的constructor（構造方法）—— 它是 ES6 class 中唯一用於初始化實例的特殊方法，當通過 new 關鍵字創建類的實例時，constructor 會自動執行，核心作用是初始化實例的屬性（尤其是私有屬性，如下面代碼中的#stack）。
es6 中，get 和 set 是用於定義訪問器屬性（Accessor Property） 的語法，訪問器屬性不直接存儲值，而是通過函數攔截對屬性的讀取（get） 和賦值（set） 操作，隱藏內部狀態（封裝性），從而實現對屬性訪問的精細化控制。
數組實現棧代碼
// 數組來實現stack
class ArrayStack {
#stack;
constructor() {
this.#stack = [];
}
get size() {
return this.#stack.length;
}
isEmpty() {
return this.size === 0;
}
push(num) {
this.#stack.push(num);
}
pop() {
if(this.isEmpty()) throw new Error("棧為空");
return this.#stack.pop();
}
peek() {
if(this.isEmpty()) throw new Error("棧為空");
return this.#stack[this.size -1];
}
toArray() {
return this.#stack;
}
}代碼相關解釋：
- 該類基於數組實現了棧的核心功能：入棧（push）、出棧（pop）、查看棧頂（peek）、獲取大小（size）、判斷為空（isEmpty）；
#stack：ES6 新增的私有字段（Private Field） ，前綴#表示該屬性只能在類內部訪問 / 修改，外部無法直接操作（比如stack.#stack會報錯），保證了棧的封裝性（避免外部隨意修改棧的底層數據）；constructor()：類的構造函數，創建ArrayStack實例時自動執行。初始化私有屬性#stack為一個空數組，作為棧的底層存儲結構（數組的 “末尾” 對應棧的 “棧頂”，因為數組的push/pop操作時間複雜度為 O (1)，效率最高）。
數組實現的棧非常直觀，利用了JavaScript數組的push和pop方法，實現了棧的核心功能。
三、鏈表實現棧
鏈表實現棧需要自定義節點和棧結構。
鏈表實現棧代碼
// 鏈表來實現棧
class ListNode {
constructor(val) {
this.val = val;
this.next = null; // 離散存儲
}
}
class LinkedListStack {
#stackPeek;
#size = 0;
constructor() {
this.#stackPeek = null;
}
push(num) {
const node = new ListNode(num);
node.next = this.#stackPeek;
this.#stackPeek = node;
this.#size++;
}
pop() {
const num = this.peek();
this.#stackPeek = this.#stackPeek.next;
this.#size--;
return num;
}
peek() {
if (!this.#stackPeek) {
throw new Error('棧為空');
}
return this.#stackPeek.val;
}
get size() {
return this.#size;
}
isEmpty() {
return this.size === 0;
}
}代碼相關解釋：
- 採用單向鏈表實現棧，核心邏輯是將鏈表頭節點作為棧頂 —— 鏈表頭增刪節點僅需修改指針（時間複雜度 O (1)），完美適配棧 “後進先出（LIFO）” 的核心操作要求。
- 節點類（ListNode）作用：定義無序列表的最小存儲單元，
val存儲棧元素值，next僅用於關聯後繼節點（離散存儲），無任何排序相關邏輯，是實現無序列表的基礎。 - 入棧方法（push）：創建新節點→新節點
next指向原棧頂→更新棧頂指針為新節點→棧大小 + 1，全程僅修改指針，無遍歷操作，效率 O (1)。 - 出棧方法（pop）：複用
peek完成空棧校驗和棧頂值獲取→棧頂指針後移（原棧頂節點被垃圾回收）→棧大小 - 1→返回棧頂值，效率 O (1)。 - 棧頂查看方法（peek）：先校驗棧是否為空（空棧拋錯），再返回棧頂節點的
val值（僅讀取，不修改棧結構），對外屏蔽無序列表的底層細節。 - 輔助屬性 / 方法：
size：通過 ES6 訪問器屬性（get）定義為只讀屬性，外部可獲取但無法賦值篡改；
isEmpty：基於size判斷棧是否為空，語義清晰且無需重複編寫空棧校驗邏輯。
鏈表實現棧的關鍵在於使用#stackPeek作為棧頂指針，通過鏈表的鏈接關係實現棧的操作。
四、數組與鏈表實現棧的優缺點比較
時間效率
數組實現：
- 入棧和出棧操作在尾部進行，時間複雜度為O(1)
- 當數組容量不足時，觸發擴容（複製所有元素到新數組），時間複雜度為O(n)
- 但擴容是低頻操作，平均時間複雜度仍為O(1)
鏈表實現：
- 入棧操作需要創建新節點，時間複雜度為O(1)
- 無需擴容，始終能保持O(1)的時間複雜度
- 但鏈表節點需要額外操作（指針設置），在入棧時略慢於數組
空間效率
數組實現：
- 可能造成空間浪費（如分配了100個元素空間，但只使用了50個）
- 但內存是連續的，緩存命中率高，訪問效率更好
鏈表實現：
- 每個節點需要額外空間存儲指針（next引用）
- 內存不連續，緩存命中率較低
- 但不會造成空間浪費，空間利用率更高
五、棧的實踐：括號匹配問題
棧在括號匹配問題中展現出了其獨特優勢。這個問題要求判斷字符串中的括號是否正確閉合。
const leftToRight = {
"(":")",
"[":"]",
"{":"}",
}
const isValid = function(s) {
if(!s) return true;
const stack = []; // 棧
const len = s.length; // 緩存長度
for(let i = 0;i < len;i++) {
const ch = s[i];
if(ch === "(" || ch === "[" || ch === "{") {
stack.push(leftToRight[ch]);
} else {
if(!stack.length || stack.pop() != ch) {
return false;
}
}
}
return stack.length === 0;
}這個實現利用了棧的FILO特性：
- 遇到左括號時，將對應的右括號壓入棧
- 遇到右括號時，彈出棧頂元素進行匹配
- 最終棧為空表示所有括號都正確閉合
例如，對於字符串"({[]})"：
(→ 壓入){→ 壓入}[→ 壓入]]→ 彈出]，匹配}→ 彈出}，匹配)→ 彈出)，匹配- 棧為空，返回
true
六、總結
棧作為計算機科學中最基礎、最常用的數據結構之一，其簡潔性和高效性使其成為解決許多編程問題的首選工具。通過ES6的類特性，我們可以更清晰、更安全地實現棧，同時理解其背後的原理和適用場景。
在實際應用中，根據具體需求選擇數組或鏈表實現棧：
- 數組實現：適合數據量相對穩定、對性能要求高且內存空間有限的場景
- 鏈表實現：適合數據量不確定、需要頻繁動態擴展的場景
棧的實踐應用遠不止括號匹配問題，它在函數調用棧、表達式求值、瀏覽器歷史記錄管理等眾多領域都有廣泛應用。理解棧的本質——"後進先出"的特性，以及如何在不同場景下選擇合適的實現方式，將使你在編程中更加得心應手。
