stack（栈）详解

stack是STL中的容器适配器，基于序列式容器（默认deque，也可指定vector）封装而成，核心遵循“先进后出（LIFO，Last In First Out）”原则，仅支持在栈顶进行插入、删除和访问操作，屏蔽了原容器的其他操作，简化了使用场景。

核心特性

1. 容器适配器：非独立容器，依赖底层容器（deque/vector）实现功能；
2. 先进后出：最后插入的元素最先被删除，仅栈顶元素可访问；
3. 无迭代器：不支持随机访问，无法遍历栈中所有元素（需弹出元素才能访问）；
4. 高效操作：栈顶插入（push）、删除（pop）、访问（top）效率均为O(1)。

定义与头文件

使用stack需包含 <stack> 头文件，定义语法简洁，支持指定底层容器（默认deque）。

基本定义

#include <stack>  // stack头文件
using namespace std;

// 1. 默认底层容器（deque），存储int类型
stack<int> st;

// 2. 指定底层容器为vector
stack<int, vector<int>> st_vec;

// 3. 存储其他类型（如string）
stack<string> st_str;

常用操作（核心必记）

stack的操作非常简洁，仅围绕“栈顶”展开，以下是最常用的操作，结合代码示例说明。

完整示例代码

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

int main() {
    // 定义一个存储int类型的栈
    stack<int> st;
    
    // 1. 插入元素（push，栈顶插入）
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);  // 此时栈内元素：10（栈底）→ 20 → 30 → 40（栈顶）
    
    // 2. 访问栈顶元素（top，仅访问，不删除）
    cout << "栈顶元素：" << st.top() << endl;  // 输出：40
    
    // 3. 删除栈顶元素（pop，仅删除，不返回）
    st.pop();  // 删除40，此时栈顶为30
    cout << "pop后栈顶元素：" << st.top() << endl;  // 输出：30
    
    // 4. 判空（empty）
    if (st.empty()) {
        cout << "栈为空" << endl;
    } else {
        cout << "栈非空" << endl;  // 输出：栈非空
    }
    
    // 5. 获取栈的大小（size）
    cout << "栈中元素个数：" << st.size() << endl;  // 输出：3（元素20、30、10？不，栈内顺序：10→20→30，size=3）
    
    // 6. 清空栈（无clear()方法，需通过pop循环删除）
    while (!st.empty()) {
        st.pop();
    }
    cout << "清空后栈的大小：" << st.size() << endl;  // 输出：0
    
    return 0;
}

操作汇总表

操作	语法	说明
插入	push(元素)	在栈顶插入一个元素，效率O(1)
删除	pop()	删除栈顶元素，无返回值，效率O(1)
访问栈顶	top()	返回栈顶元素，不删除，效率O(1)
判空	empty()	栈为空返回true，否则返回false
获取大小	size()	返回栈中元素的个数
清空	无clear()	需通过循环pop()删除所有元素

底层实现与选择

stack的底层容器可指定，默认是deque，也可选择vector，两者的区别如下：

1. 默认底层容器：deque

• 优势：deque支持双端插入/删除，作为stack的底层容器，栈顶操作（push/pop）效率高，且deque的内存管理更灵活，避免vector扩容时的内存拷贝；
• 适用场景：大多数日常开发场景，无需手动指定，使用默认即可。

2. 指定底层容器：vector

• 优势：vector的内存连续，栈顶访问（top）效率略高于deque；
• 劣势：vector在栈底插入/删除效率低（但stack仅操作栈顶，不影响），扩容时会有内存拷贝；
• 适用场景：需要极致栈顶访问效率，且元素个数相对固定（避免频繁扩容）的场景。

示例：指定vector为底层容器

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

int main() {
    stack<int, vector<int>> st;
    st.push(1);
    st.push(2);
    cout << "栈顶：" << st.top() << endl;  // 输出：2
    return 0;
}

常见误区

1. 误以为stack有clear()方法：stack没有内置的clear()，需通过循环pop()删除所有元素；
2. 试图遍历stack：stack不支持迭代器，无法直接遍历，需弹出元素才能访问（弹出后元素会被删除）；
3. 混淆push和pop的作用：push仅在栈顶插入，pop仅删除栈顶元素，均不影响栈底及中间元素；
4. 访问空栈的top()：空栈调用top()会导致未定义行为，需先通过empty()判断栈是否非空。

实战场景

stack的“先进后出”特性，适合以下场景：

1. 括号匹配（算法题高频）

判断一个字符串中的括号（()、[]、{}）是否匹配，利用stack存储左括号，遇到右括号时弹出栈顶元素，判断是否匹配。

示例代码：

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

bool isMatch(string s) {
    stack<char> st;
    for (char c : s) {
        // 遇到左括号，压入栈
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            // 遇到右括号，栈为空则不匹配
            if (st.empty()) return false;
            // 弹出栈顶元素，判断是否匹配
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    // 遍历结束后，栈为空则匹配，否则不匹配
    return st.empty();
}

int main() {
    string s1 = "({[]})";
    string s2 = "({[)]}";
    cout << isMatch(s1) << endl;  // 输出：1（匹配）
    cout << isMatch(s2) << endl;  // 输出：0（不匹配）
    return 0;
}

2. 递归模拟

某些递归场景（如阶乘、斐波那契）可通过stack模拟，避免递归深度过大导致栈溢出。

3. 逆序输出

将元素依次压入栈，再依次弹出，即可实现逆序输出。

示例代码：

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    stack<int> st;
    
    // 压入栈
    for (int x : arr) {
        st.push(x);
    }
    
    // 弹出栈（逆序输出）
    cout << "逆序输出：";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;  // 输出：5 4 3 2 1
    return 0;
}

总结

stack是一种简单、高效的容器适配器，核心优势是“先进后出”的特性和O(1)的栈顶操作效率。使用时需注意：无clear()方法、不支持遍历、访问top()前需判空。日常开发和算法题中，括号匹配、递归模拟、逆序输出是其最常见的应用场景，默认使用deque作为底层容器即可满足大多数需求。