C++ 堆疊與堆積數據結構實戰：LIFO 原理、陣列實現與 STL 容器適配器

概念釐清：Stack vs Heap

本文聚焦資料結構 Stack (堆疊)。

堆疊核心操作

• Push (入堆疊/壓入)： 在頂端插入元素。
• Pop (出堆疊/彈出)： 移除並返回頂端元素。
• Top/Peek (查看頂端)： 僅讀取頂端元素不移除。
• Empty/Size： 狀態查詢。

陣列實現固定容量堆疊

#include <iostream>
#include <stdexcept>

template <typename T, size_t MAX_SIZE>
class FixedStack {
    T data[MAX_SIZE];
    size_t top_idx = 0; // 指向下一個可寫入位置，0 表空
public:
    bool empty() const { return top_idx == 0; }
    size_t size() const { return top_idx; }
    
    void push(const T& value) {
        if (top_idx >= MAX_SIZE) throw std::overflow_error("Stack full");
        data[top_idx++] = value;
    }
    
    void pop() {
        if (empty()) throw std::underflow_error("Stack empty");
        --top_idx;
    }
    
    T& top() {
        if (empty()) throw std::underflow_error("Stack empty");
        return data[top_idx - 1];
    }
    
    const T& top() const { return const_cast<FixedStack*>(this)->top(); }
};

int main() {
    FixedStack<int, 10> st;
    for (int i = 0; i < 5; ++i) st.push(i * 10);
    while (!st.empty()) { std::cout << st.top() << ' '; st.pop(); }
    // 輸出: 40 30 20 10 0 (LIFO)
}

動態陣列實現 (可擴容)

template <typename T>
class DynamicStack {
    std::vector<T> data;
public:
    void push(const T& v) { data.push_back(v); }
    void pop() { if (data.empty()) throw ...; data.pop_back(); }
    T& top() { if (data.empty()) throw ...; return data.back(); }
    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

STL 容器適配器：std::stack

#include <stack>
#include <vector>
#include <deque> // 底層預設容器
#include <list>

std::stack<int> s1;                    // 底層 deque
std::stack<int, std::vector<int>> s2; // 底層 vector
std::stack<int, std::list<int>> s3;   // 底層 list

s1.push(1); s1.push(2);
std::cout << s1.top(); // 2
s1.pop();

注意： std::stack 無迭代器、無遍歷、無 clear() (C++11 前)，僅暴露堆疊核心介面。

經典應用場景

1. 運算式求值/語法分析： 中序轉後序、括號匹配、遞歸下降解析器。
2. 函數呼叫堆疊模擬： 遞歸轉迭代、協程實現。
3. 回溯演算法： 迷宮走迷、八皇后、DFS 非遞歸實現。
4. 編輯器撤銷/重做： 命令模式 + 兩個堆疊。
5. 瀏覽器前進/後退： 兩個堆疊協作。

效能特徵總結

1. 上一篇文章： C++ 複製建構子深度解析：淺拷貝陷阱、深拷貝實現與三/五法則實戰
2. 下一篇文章： C++ 物件模型深度解析：記憶體佈局、虛函數表與建構/解構語義

C++ 入門

AJAX 基礎：DOM 文檔對象模型核心概念與節點操作

DOM 定義 DOM (Document Object Mo

POJ 3155 Hard Life：最大密度子圖與二分查找最大權閉合圖

問題定義 無向圖 n≤100, m≤1000。子圖密度 =

歸併排序算法深度解析 - 分治法與雙路歸併實現

算法思想：分治法 歸併排序是典型的分治法： 分解：將長

simpleCut：免費高效的 C++ 一維下料優化軟件

什麼是下料優化？ 在製造業中，將原材料（如鋼材、木材、管材）