C++ 棧數據結構手動實現：數組模擬壓棧出棧完整教學

棧的抽象數據類型 (ADT)

• 數據：同類型元素集合
• 操作：push(入棧)、pop(出棧)、top(取頂)、empty(判空)、size(大小)
• 特性：後進先出 (LIFO)

數組實現完整代碼

頭文件 stack.h

#ifndef STACK_H
#define STACK_H
#include 
using namespace std;

const int MAX_SIZE = 100;

class Stack {
private:
    int data[MAX_SIZE];
    int top;  // 棧頂索引，0 表示空
public:
    Stack();           // 構造函數
    void push(int x);  // 入棧
    int pop();         // 出棧
    int peek() const;  // 取頂
    bool empty() const;
    int size() const;
    void display() const;
};
#endif

實現文件 stack.cpp

#include "stack.h"

Stack::Stack() : top(0) {}

void Stack::push(int x) {
    if (top == MAX_SIZE) {
        cout << "Stack overflow!\n";
        return;
    }
    data[top++] = x;
    cout << "Pushed " << x << endl;
}

int Stack::pop() {
    if (top == 0) {
        cout << "Stack underflow!\n";
        return 0;
    }
    return data[--top];
}

int Stack::peek() const {
    if (top == 0) return 0;
    return data[top-1];
}

bool Stack::empty() const { return top == 0; }
int Stack::size() const { return top; }

void Stack::display() const {
    cout << "Stack (top to bottom): ";
    for (int i = top-1; i >= 0; --i) cout << data[i] << ' ';
    cout << endl;
}

主程序 main.cpp (交互式演示)

#include "stack.h"

int main() {
    Stack s;
    char op;
    int val;
    cout << "Commands: p=push, o=pop, t=top, s=size, d=display, q=quit\n";
    while (cin >> op) {
        switch (op) {
            case 'p': cin >> val; s.push(val); break;
            case 'o': cout << "Popped: " << s.pop() << endl; break;
            case 't': cout << "Top: " << s.peek() << endl; break;
            case 's': cout << "Size: " << s.size() << endl; break;
            case 'd': s.display(); break;
            case 'q': return 0;
            default: cout << "Unknown command\n";
        }
    }
    return 0;
}

關鍵設計點

1. 頂指針語義：`top` 指向下一個可用位置，空棧時 `top=0`
2. 邊界檢查：push 檢查滿，pop/peek 檢查空
3. 封裝性：數據私有，僅通過接口訪問
4. 固定容量：教學簡化，生產環境用 `vector` 動態擴容

STL std::stack 對比

#include 
stack s;
s.push(1); s.push(2);
cout << s.top();  // 2
s.pop();
cout << s.top();  // 1
cout << s.size(); // 1

底層默認 `deque`，也可指定 `vector`/`list`。生產代碼優先用 STL。

應用場景

• 表達式求值（中綴轉後綴）
• 括號匹配檢查
• 函數調用棧 / 遞歸消除
• 深度優先搜索 (DFS) 迭代實現
• 單調棧優化 (最近更大元素等)