c++ 栈

栈（Stack）是计算机科学中一种非常重要的数据结构，它是一种遵循 后进先出（LIFO, Last In First Out）原则的数据结构，即最后放入栈中的元素最先被取出。

基本操作

• push: 将元素压入栈顶。

• pop: 从栈顶弹出元素。

• top 或 peek: 获取栈顶元素，但不弹出。

• isEmpty: 检查栈是否为空。

• size: 获取栈的大小。

栈的操作通常是基于数组或链表实现的。大多数编程语言都提供了栈的实现（如 C++ STL 中的 std::stack 类）。

栈的实现

使用数组实现一个栈

#include <iostream>
#include <stdexcept>

class Stack {
private:
    int* arr;         // 存储栈元素的数组
    int capacity;     // 栈的最大容量
    int topIndex;     // 栈顶索引

public:
    Stack(int cap) : capacity(cap), topIndex(-1) {
        arr = new int[capacity];
    }

    ~Stack() {
        delete[] arr;
    }

    // 栈是否为空
    bool isEmpty() {
        return topIndex == -1;
    }

    // 栈是否已满
    bool isFull() {
        return topIndex == capacity - 1;
    }

    // 获取栈顶元素
    int top() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        return arr[topIndex];
    }

    // 入栈操作
    void push(int value) {
        if (isFull()) {
            throw std::overflow_error("Stack overflow");
        }
        arr[++topIndex] = value;
    }

    // 出栈操作
    void pop() {
        if (isEmpty()) {
            throw std::underflow_error("Stack underflow");
        }
        --topIndex;
    }

    // 获取栈大小
    int size() {
        return topIndex + 1;
    }
};

int main() {
    Stack s(5);

    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "Top element: " << s.top() << std::endl;

    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl;

    std::cout << "Stack size: " << s.size() << std::endl;

    return 0;
}

常见应用

括号匹配问题

给定一个包含括号（(), {}, []）的字符串，判断括号是否匹配。

算法思想

遇到左括号时入栈，遇到右括号时出栈，匹配时继续，如果匹配失败或者栈为空，则不匹配。

代码实现（c++）

#include <iostream>
#include <stack>
#include <string>

bool isValid(const std::string& s) {
    std::stack<char> stack;

    for (auto c : s) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.empty()) return false;
            char top = stack.top();
            stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }

    return stack.empty();
}

int main() {
    std::string s = "{[()]}";
    if (isValid(s)) {
        std::cout << "Valid" << std::endl;
    } else {
        std::cout << "Invalid" << std::endl;
    }

    return 0;
}

逆波兰表达式求值

逆波兰表达式是一种后缀表达式，运算符位于操作数后面，利用栈来计算结果。

算法思想

通过扫描逆波兰表达式，将数字压入栈中，遇到运算符时从栈中弹出操作数，进行运算后再将结果压回栈中。

代码实现（c++）

#include <iostream>
#include <stack>
#include <sstream>
#include <string>
#include <cctype>

int evalRPN(const std::vector<std::string>& tokens) {
    std::stack<int> stack;

    for (const auto& token : tokens) {
        if (isdigit(token[0]) || (token[0] == '-' && token.size() > 1 && isdigit(token[1]))) {
            stack.push(std::stoi(token));
        } else {
            int b = stack.top(); stack.pop();
            int a = stack.top(); stack.pop();
            if (token == "+") stack.push(a + b);
            else if (token == "-") stack.push(a - b);
            else if (token == "*") stack.push(a * b);
            else if (token == "/") stack.push(a / b);
        }
    }

    return stack.top();
}

int main() {
    std::vector<std::string> tokens = {"2", "1", "+", "3", "*"};
    std::cout << "Result: " << evalRPN(tokens) << std::endl;
    return 0;
}

DFS（深度优先搜索）

在图或树的遍历中，DFS 使用栈来保存节点，以便后续访问。

算法思想

将起始节点入栈，访问节点并标记，然后将未访问的邻接节点入栈，直到没有未访问的节点。

代码实现（c++）

#include <iostream>
#include <vector>
#include <stack>

void DFS(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<bool> visited(graph.size(), false);
    std::stack<int> stack;

    stack.push(start);

    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();

        if (!visited[node]) {
            std::cout << node << " ";
            visited[node] = true;
        }

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

int main() {
    std::vector<std::vector<int>> graph = {
        {1, 2},      // Node 0 connected to nodes 1 and 2
        {0, 3, 4},   // Node 1 connected to nodes 0, 3, 4
        {0, 5},      // Node 2 connected to nodes 0, 5
        {1},         // Node 3 connected to node 1
        {1},         // Node 4 connected to node 1
        {2}          // Node 5 connected to node 2
    };

    DFS(0, graph);  // Starting from node 0

    return 0;
}

求括号表达式的结果

计算一个包含括号的表达式值，可以通过使用栈来辅助计算。

算法思想

使用栈保存操作数和运算符，在遇到括号时，处理内部表达式。

代码实现（c++）

#include <iostream>
#include <stack>
#include <string>

int calculate(const std::string& s) {
    std::stack<int> stack;
    int num = 0, result = 0, sign = 1;  // sign: 1 表示正，-1 表示负

    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '+') {
            result += sign * num;
            sign = 1;
            num = 0;
        } else if (c == '-') {
            result += sign * num;
            sign = -1;
            num = 0;
        } else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * num;
            num = 0;
            result *= stack.top(); stack.pop();  // Apply previous sign
            result += stack.top(); stack.pop();  // Add previous result
        }
    }
    result += sign * num;
    return result;
}

int main() {
    std::string expr = "1 + (2 - (3 + 4))";
    std::cout << "Result: " << calculate(expr) << std::endl;
    return 0;
}