C 語言進階實戰：設計 O(1) 取最小值的棧（輔助棧法）

問題描述

實現棧資料結構，支援 push、pop、min 三操作，要求時間複雜度均為 O(1)。

核心思路：輔助最小值棧

利用棧先進後出 (LIFO) 特性，維護一個同步的「最小值棧」，其棧頂始終為主棧當前最小元素。

演算法邏輯

• Push(x)：
  • 主棧入 x。
  • 若最小值棧為空 或 x <= minStack.top()，最小值棧也入 x。
• Pop()：
  • 主棧出 y。
  • 若 y == minStack.top()，最小值棧也出棧。
• Min()：直接返回 minStack.top()。

C++ 實現（含靜態成員技巧）

struct StackNode {
    int value;
    StackNode *next;
    static StackNode *minTop;  // 靜態成員：全棧共享最小值棧頂

    StackNode* push(int v) { ... }
    StackNode* pop() { ... }
    int min() { return minTop->value; }

    // 內部輔助：最小值棧操作
    void minPush(int v) { ... }
    void minPop() { ... }
};
StackNode* StackNode::minTop = nullptr;  // 靜態成員定義

測試案例與輸出

StackNode *s = nullptr;
s = s->push2(5);  // min=5
s = s->push2(2);  // min=2
s = s->push2(4);  // min=2
s = s->push2(1);  // min=1
s = s->push2(1);  // min=1 (相等也入最小值棧，保證 pop 正確)
while (s) s = s->pop2();  // 依序輸出 pop 過程中最小值變化

輸出顯示最小值棧正確追蹤：5 → 2 → 2 → 1 → 1 → 2 → 5。

關鍵細節

1. 相等值也入最小值棧：確保重複最小值被多次 pop 時，最小值棧同步彈出，避免過早失效。
2. 靜態成員實現共享：所有節點共用同一最小值棧頂指標，無需額外結構體包裹。
3. 記憶體管理：範例簡化為單向鏈表節點動態分配，實際工程需考慮 RAII 或記憶體池。