栈

栈是遵循后进先出 (LIFO) 原则的线性数据结构。元素从同一端（称为栈顶）添加和删除。可以想象成一摞盘子 - 只能从顶部添加或移除盘子。

栈在计算机科学中是基础性的，用于函数调用、表达式求值、撤销操作和许多算法中。

栈操作

栈的主要操作有：

push(): 向栈顶添加元素
pop(): 移除栈顶元素
top()/peek(): 查看栈顶元素但不移除
empty(): 检查栈是否为空
size(): 获取元素数量

使用数组实现栈

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;
    int capacity;
    int topIndex;

public:
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        topIndex = -1;
    }
    
    ~Stack() {
        delete[] arr;
    }
    
    // Push element to top
    void push(int value) {
        if (topIndex >= capacity - 1) {
            cout << "Stack Overflow! Cannot push " << value << endl;
            return;
        }
        arr[++topIndex] = value;
        cout << "Pushed: " << value << endl;
    }
    
    // Pop element from top
    int pop() {
        if (topIndex < 0) {
            cout << "Stack Underflow! Cannot pop from empty stack" << endl;
            return -1;
        }
        return arr[topIndex--];
    }
    
    // Peek at top element
    int top() {
        if (topIndex < 0) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        return arr[topIndex];
    }
    
    // Check if stack is empty
    bool empty() {
        return topIndex < 0;
    }
    
    // Get size of stack
    int size() {
        return topIndex + 1;
    }
    
    // Display stack contents
    void display() {
        if (empty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        
        cout << "Stack contents (top to bottom): ";
        for (int i = topIndex; i >= 0; i--) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Stack stack(5);
    
    // Push elements
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    stack.display();
    cout << "Top element: " << stack.top() << endl;
    cout << "Stack size: " << stack.size() << endl;
    
    // Pop elements
    cout << "Popped: " << stack.pop() << endl;
    cout << "Popped: " << stack.pop() << endl;
    
    stack.display();
    
    // Try to pop from empty stack
    stack.pop();
    stack.pop(); // This will cause underflow
    
    return 0;
}

STL 栈

C++ 标准模板库提供了一个栈容器适配器，可以与不同的底层容器一起使用：

使用 STL 栈

#include <iostream>
#include <stack>
#include <vector>
#include <deque>
using namespace std;

int main() {
    // Default stack (uses deque as underlying container)
    stack<int> st;
    
    // Push elements
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);
    
    cout << "Stack size: " << st.size() << endl;
    cout << "Top element: " << st.top() << endl;
    
    // Display and pop all elements
    cout << "Stack contents: ";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    
    // Stack with vector as underlying container
    stack<int, vector<int>> stackWithVector;
    stackWithVector.push(1);
    stackWithVector.push(2);
    stackWithVector.push(3);
    
    cout << "Vector-based stack: ";
    while (!stackWithVector.empty()) {
        cout << stackWithVector.top() << " ";
        stackWithVector.pop();
    }
    cout << endl;
    
    // Stack of strings
    stack<string> stringStack;
    stringStack.push("First");
    stringStack.push("Second");
    stringStack.push("Third");
    
    cout << "String stack: ";
    while (!stringStack.empty()) {
        cout << stringStack.top() << " ";
        stringStack.pop();
    }
    cout << endl;
    
    return 0;
}

栈的应用

平衡括号检查

栈最常见的应用之一是检查表达式中的括号是否平衡：

平衡括号检查器

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(string expression) {
    stack<char> s;
    
    for (char ch : expression) {
        // Push opening brackets
        if (ch == '(' || ch == '[' || ch == '{') {
            s.push(ch);
        }
        // Check closing brackets
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (s.empty()) {
                return false; // No matching opening bracket
            }
            
            char top = s.top();
            s.pop();
            
            // Check if brackets match
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    // Stack should be empty for balanced expression
    return s.empty();
}

int main() {
    vector<string> expressions = {
        "()",
        "()[]{}", 
        "([{}])",
        "(((",
        "())",
        "([)]",
        "{[()()]}"
    };
    
    cout << "Checking balanced parentheses:" << endl;
    for (const string& expr : expressions) {
        cout << expr << " -> " 
             << (isBalanced(expr) ? "Balanced" : "Not Balanced") 
             << endl;
    }
    
    return 0;
}

表达式求值

栈可以用来求值后缀表达式（逆波兰表示法）：

后缀表达式求值

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

int evaluatePostfix(string expression) {
    stack<int> s;
    istringstream iss(expression);
    string token;
    
    while (iss >> token) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // Pop two operands
            int operand2 = s.top(); s.pop();
            int operand1 = s.top(); s.pop();
            
            int result;
            if (token == "+") result = operand1 + operand2;
            else if (token == "-") result = operand1 - operand2;
            else if (token == "*") result = operand1 * operand2;
            else if (token == "/") result = operand1 / operand2;
            
            s.push(result);
        } else {
            // Convert token to number and push
            s.push(stoi(token));
        }
    }
    
    return s.top();
}

int main() {
    vector<string> expressions = {
        "3 4 +",           // 3 + 4 = 7
        "5 2 * 3 +",       // 5 * 2 + 3 = 13
        "15 7 1 1 + - / 3 * 2 1 1 + + -", // Complex expression
        "2 3 1 * + 9 -"    // 2 + 3 * 1 - 9 = -4
    };
    
    cout << "Postfix Expression Evaluation:" << endl;
    for (const string& expr : expressions) {
        cout << expr << " = " << evaluatePostfix(expr) << endl;
    }
    
    return 0;
}