📚 C++ 栈 (std::stack) 数据结构笔记

1. 什么是栈？

栈是一种后进先出（LIFO, Last In First Out）的线性数据结构。
可以把栈想象成一摞盘子：最后放上去的，最先被拿走。

核心特点：

• 只允许在一端（栈顶）进行插入和删除操作。
• 访问元素只能访问栈顶元素。
• 不支持随机访问。

2. STL 中的 std::stack

2.1 头文件与定义

#include <stack>

std::stack<int> s;  // 默认底层容器是 deque

2.2 常用操作

⚠️ 注意： pop() 不返回值，若需要获取并移除栈顶，应先用 top() 取值，再 pop()。

2.3 示例代码

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stk;
    stk.push(10);
    stk.push(20);
    stk.push(30);

    std::cout << "栈顶元素: " << stk.top() << std::endl; // 30
    stk.pop();
    std::cout << "pop后栈顶: " << stk.top() << std::endl; // 20
    std::cout << "栈大小: " << stk.size() << std::endl;   // 2
    std::cout << "是否为空: " << (stk.empty() ? "是" : "否") << std::endl;
    return 0;
}

3. 底层容器选择

std::stack 是一个容器适配器，默认使用 std::deque 作为底层容器，也可以根据需要指定为 std::vector 或 std::list。

#include <stack>
#include <vector>
#include <list>

std::stack<int, std::vector<int>> vecStack;   // 使用 vector
std::stack<int, std::list<int>>   listStack;  // 使用 list

容器选择建议：

• deque（默认）：在多数情况下性能最优，支持高效的两端插入删除。
• vector：尾部插入/删除快，但可能发生扩容重分配。内存连续，缓存友好。
• list：不会发生重分配，每个元素额外占用指针内存。

4. 手动实现栈

理解底层实现有助于掌握细节，以下基于动态数组和链表给出两种简单实现。

4.1 基于数组（动态扩容）

#include <stdexcept>

template <typename T>
class ArrayStack {
private:
    T* data;
    size_t capacity;
    size_t topIndex;
    void resize() {
        capacity *= 2;
        T* newData = new T[capacity];
        for (size_t i = 0; i < topIndex; ++i)
            newData[i] = data[i];
        delete[] data;
        data = newData;
    }
public:
    ArrayStack(size_t initCap = 8) : capacity(initCap), topIndex(0) {
        data = new T[capacity];
    }
    ~ArrayStack() { delete[] data; }

    void push(const T& val) {
        if (topIndex == capacity) resize();
        data[topIndex++] = val;
    }
    void pop() {
        if (topIndex == 0) throw std::underflow_error("栈为空");
        --topIndex;
    }
    T& top() {
        if (topIndex == 0) throw std::underflow_error("栈为空");
        return data[topIndex - 1];
    }
    bool empty() const { return topIndex == 0; }
    size_t size() const { return topIndex; }
};

4.2 基于单向链表

template <typename T>
class ListStack {
private:
    struct Node {
        T value;
        Node* next;
        Node(const T& val, Node* nxt = nullptr) : value(val), next(nxt) {}
    };
    Node* head;
    size_t count;
public:
    ListStack() : head(nullptr), count(0) {}
    ~ListStack() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
    void push(const T& val) {
        head = new Node(val, head);
        ++count;
    }
    void pop() {
        if (!head) throw std::underflow_error("栈为空");
        Node* temp = head;
        head = head->next;
        delete temp;
        --count;
    }
    T& top() {
        if (!head) throw std::underflow_error("栈为空");
        return head->value;
    }
    bool empty() const { return head == nullptr; }
    size_t size() const { return count; }
};

5. 经典应用场景

5.1 示例：括号匹配（C++）

#include <stack>
#include <string>
#include <unordered_map>

bool isValid(const std::string& s) {
    std::stack<char> stk;
    std::unordered_map<char, char> pairs = {{')','('}, {']','['}, {'}','{'}};
    for (char ch : s) {
        if (pairs.count(ch)) {
            if (stk.empty() || stk.top() != pairs[ch]) return false;
            stk.pop();
        } else {
            stk.push(ch);
        }
    }
    return stk.empty();
}

6. 复杂度总结

7. 注意事项 & 小贴士

• 遍历陷阱：栈本身不支持迭代器。若需要遍历，通常意味着选错了数据结构，考虑使用 vector 或 deque。
• 线程安全：std::stack 的单个操作不是线程安全的，多线程访问需加锁。
• 异常安全：push 操作可能因内存分配失败抛出 std::bad_alloc，自定义类型还应考虑拷贝/移动可能抛出的异常。
• 拷贝后元素顺序不变：stack 的拷贝与底层容器行为一致。
• 性能优化：如果知道最大容量，优先使用定长数组实现；STL 中默认 deque 已足够高效。

📘 记住： 栈是逻辑结构，std::stack 是适配器，它包装了具体容器并限制接口，让你只看到栈的操作。