C++ STL 栈详解：stack 的使用、经典题目与简单模拟实现

🔥 星恒随风： 个人主页 ❄️ 个人专栏： 《指针合集》 ｜ 《C语言基础》 ｜ 《数据结构》 ｜ 《机器学习导论》 ｜ 《前端基础》 ｜ 《python基础》 ｜ 《C++从入门到入土》 ✨ 数据即知识，压缩即智能

---

前言

在数据结构中，栈算是比较容易理解的一种结构。

它的规则很简单：最后放进去的元素，最先被取出来。

这种特点通常称为：

后进先出
Last In First Out
LIFO

C++ STL 已经提供了 stack，使用起来并不复杂。但只记住 push() 和 pop() 还不够，我们还需要理解：

• 栈为什么只能访问栈顶？
• pop() 为什么不返回被删除的元素？
• stack 为什么没有迭代器？
• 什么是容器适配器？
• 为什么 STL 默认使用 deque 作为底层容器？
• 如何用已有容器简单模拟一个栈？

---

一、什么是栈？

栈是一种操作受限的线性数据结构。

假设依次把下面三个元素压入栈中：

1
2
3

栈中的状态可以画成：

      栈顶
       ↓
     ┌───┐
     │ 3 │
     ├───┤
     │ 2 │
     ├───┤
     │ 1 │
     └───┘

此时最先弹出的元素是 3，然后是 2，最后才是 1。

整个过程是：

入栈顺序：1 2 3
出栈顺序：3 2 1

栈只允许在同一端插入和删除元素，这一端称为栈顶。

常见操作包括：

push：压栈
pop ：出栈
top ：访问栈顶

---

二、stack 是容器适配器

在 STL 中，stack 严格来说并不是一个独立的序列容器，而是一个容器适配器。

容器适配器可以简单理解为：

在已有容器外面包一层，只开放符合某种数据结构规则的接口。

例如，deque 本身支持头尾插入、头尾删除和随机访问，但把它封装成 stack 后，只允许使用：

push()
pop()
top()
empty()
size()

这样就把一个功能较多的容器，限制成了“后进先出”的栈。

其大致结构可以理解成：

stack 对外接口
      ↓
push / pop / top
      ↓
底层容器 deque

默认情况下，std::stack 的底层容器是 deque：

std::stack<int>

近似于：

std::stack<int, std::deque<int>>

也可以显式指定其他容器：

std::stack<int, std::vector<int>> s1;
std::stack<int, std::list<int>> s2;

只要底层容器支持：

back()
push_back()
pop_back()

就可以用来封装栈。

---

三、stack 的常用接口

使用 stack 需要包含头文件：

#include <stack>

常用接口如下：

接口	作用
stack()	构造一个空栈
empty()	判断栈是否为空
size()	返回栈中元素个数
top()	返回栈顶元素的引用
push(x)	将元素压入栈中
pop()	删除栈顶元素
emplace(...)	在栈顶直接构造元素
swap()	交换两个栈

一个最基本的例子：

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

int main()
{
    stack<int> st;

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

    cout << "栈顶元素：" << st.top() << '\n';
    cout << "元素个数：" << st.size() << '\n';

    st.pop();

    cout << "出栈后的栈顶：" << st.top() << '\n';

    return 0;
}

---

四、pop 为什么不返回被删除的元素？

很多初学者会写出下面的代码：

int value = st.pop();

但这段代码无法通过编译。

原因是：

pop()

只负责删除栈顶元素，返回类型是 void。

如果需要获取栈顶元素，应该先调用 top()，再调用 pop()：

int value = st.top();
st.pop();

完整写法：

if (!st.empty())
{
    int value = st.top();
    st.pop();

    cout << value << '\n';
}

这种接口设计把“读取”和“删除”分成了两个操作：

top()：读取栈顶
pop()：删除栈顶

代码的行为也会更加明确。

---

五、访问栈顶前先判断 empty

空栈中没有栈顶元素，因此不要直接对空栈调用：

st.top();
st.pop();

更稳妥的写法是：

if (!st.empty())
{
    cout << st.top() << '\n';
    st.pop();
}

遍历并清空整个栈时，可以这样写：

while (!st.empty())
{
    cout << st.top() << " ";
    st.pop();
}

需要注意，这种遍历会删除栈中的所有元素。

如果不想修改原栈，可以先复制一份：

stack<int> copy = st;

while (!copy.empty())
{
    cout << copy.top() << " ";
    copy.pop();
}

---

六、stack 为什么没有迭代器？

vector、list 这些容器都能使用迭代器遍历：

for (auto it = v.begin(); it != v.end(); ++it)
{
    cout << *it << " ";
}

但 stack 没有提供：

begin()
end()

这是刻意设计的结果。

栈的核心规则是：

只能从栈顶访问元素。

如果允许我们直接遍历、修改中间元素，栈的约束就失去了意义。

因此，stack 只公开栈顶相关接口，不公开底层容器的迭代器。

这也是容器适配器的重要特点：它不是把底层容器的所有功能原样暴露出来，而是主动隐藏不符合当前数据结构规则的接口。

---

七、用栈实现数据逆序

栈天然适合处理逆序问题。

例如，将数组中的元素反向输出：

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

int main()
{
    vector<int> nums{1, 2, 3, 4, 5};
    stack<int> st;

    for (int value : nums)
    {
        st.push(value);
    }

    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }

    return 0;
}

输出：

5 4 3 2 1

---

八、经典应用：括号匹配

给定一个只包含下面几种字符的字符串：

()
[]
{}

判断括号是否正确匹配。

例如：

()[]{}    正确
([{}])    正确
([)]      错误
((        错误

基本思路是：

1. 遇到左括号就入栈；
2. 遇到右括号，检查它是否和栈顶左括号匹配；
3. 匹配成功就弹出栈顶；
4. 最后栈必须为空。

代码如下：

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

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

    for (char ch : s)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            st.push(ch);
        }
        else
        {
            if (st.empty())
            {
                return false;
            }

            char top = st.top();

            bool matched =
                (top == '(' && ch == ')') ||
                (top == '[' && ch == ']') ||
                (top == '{' && ch == '}');

            if (!matched)
            {
                return false;
            }

            st.pop();
        }
    }

    return st.empty();
}

为什么要检查最后的栈是否为空？

因为字符串可能是：

(((

整个过程中没有出现错误的右括号，但左括号始终没有被匹配，因此结果仍然应该是 false。

---

九、经典应用：最小栈

普通栈只能快速得到栈顶元素。

现在增加一个要求：

在 O(1) 时间内得到栈中的最小值

最直接的思路是每次遍历整个栈，但这样查询最小值需要 O(N)。

更合适的办法是使用两个栈：

_elem：保存所有元素
_min ：保存当前阶段的最小值

实现如下：

#include <stack>
using namespace std;

class MinStack
{
public:
    void push(int value)
    {
        _elem.push(value);

        if (_min.empty() || value <= _min.top())
        {
            _min.push(value);
        }
    }

    void pop()
    {
        if (_elem.empty())
        {
            return;
        }

        if (_elem.top() == _min.top())
        {
            _min.pop();
        }

        _elem.pop();
    }

    int top() const
    {
        return _elem.top();
    }

    int getMin() const
    {
        return _min.top();
    }

    bool empty() const
    {
        return _elem.empty();
    }

private:
    stack<int> _elem;
    stack<int> _min;
};

这里需要注意：

value <= _min.top()

不能只写成：

value < _min.top()

因为栈里可能存在重复的最小值。

例如依次压入：

3 1 1

两个 1 都应该记录到 _min 中。否则弹出一个 1 后，程序会误以为栈中已经没有最小值 1。

---

十、经典应用：逆波兰表达式求值

逆波兰表达式也叫后缀表达式。

普通中缀表达式：

(2 + 1) * 3

对应的逆波兰表达式是：

2 1 + 3 *

求值规则：

• 遇到数字就入栈；
• 遇到运算符，就弹出两个数字；
• 计算结果重新入栈；
• 最后栈顶就是答案。

代码如下：

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

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

    for (const string& token : tokens)
    {
        if (token != "+" &&
            token != "-" &&
            token != "*" &&
            token != "/")
        {
            st.push(stoi(token));
            continue;
        }

        int right = st.top();
        st.pop();

        int left = st.top();
        st.pop();

        if (token == "+")
        {
            st.push(left + right);
        }
        else if (token == "-")
        {
            st.push(left - right);
        }
        else if (token == "*")
        {
            st.push(left * right);
        }
        else
        {
            st.push(left / right);
        }
    }

    return st.top();
}

这里取数顺序不能写反。

对于减法和除法：

left - right
left / right

先弹出的元素是右操作数，后弹出的元素才是左操作数。

---

十一、简单模拟实现 stack

从接口可以看出，栈需要的底层操作并不多：

尾插
尾删
访问尾部元素
判断是否为空
获取元素个数

因此可以用 vector、deque 或 list 进行封装。

下面实现一个简单版本：

#include <cassert>
#include <cstddef>
#include <deque>

namespace bit
{
    template<class T, class Container = std::deque<T>>
    class stack
    {
    public:
        stack() = default;

        void push(const T& value)
        {
            _container.push_back(value);
        }

        void pop()
        {
            assert(!_container.empty());
            _container.pop_back();
        }

        T& top()
        {
            assert(!_container.empty());
            return _container.back();
        }

        const T& top() const
        {
            assert(!_container.empty());
            return _container.back();
        }

        std::size_t size() const
        {
            return _container.size();
        }

        bool empty() const
        {
            return _container.empty();
        }

    private:
        Container _container;
    };
}

测试代码：

#include <iostream>

int main()
{
    bit::stack<int> st;

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

    while (!st.empty())
    {
        std::cout << st.top() << " ";
        st.pop();
    }

    return 0;
}

输出：

30 20 10

模拟实现的核心并不复杂：

push()  -> push_back()
pop()   -> pop_back()
top()   -> back()

这正是容器适配器的基本思想。

---

十二、为什么默认底层容器是 deque？

既然 vector 也能实现栈，为什么 STL 默认选择 deque？

可以从几个方面理解。

1. 栈不需要连续存储

栈只操作尾部，不需要依赖连续内存，也不需要随机访问。

2. vector 扩容时可能搬移元素

当 vector 容量不足时，通常需要：

申请新空间
搬移原有元素
释放旧空间

而 deque 使用分段存储，增长时通常不需要把全部元素整体搬到另一块连续空间。

3. deque 支持高效尾插和尾删

栈需要的核心操作正好是：

push_back()
pop_back()
back()

这些都是 deque 擅长的操作。

因此，deque 能满足栈的操作需求，也能避开 vector 扩容时大规模搬移数据的问题。

---

十三、常见错误整理

1. 对空栈调用 top 或 pop

错误：

stack<int> st;
cout << st.top();

应先判断：

if (!st.empty())
{
    cout << st.top();
}

2. 认为 pop 会返回元素

错误：

int value = st.pop();

正确：

int value = st.top();
st.pop();

3. 最小栈没有处理重复最小值

错误：

if (value < _min.top())

更稳妥：

if (_min.empty() || value <= _min.top())

4. 逆波兰表达式操作数顺序写反

正确顺序：

int right = st.top();
st.pop();

int left = st.top();
st.pop();

5. 试图直接遍历 stack

stack 没有公开迭代器。需要查看全部元素时，可以复制一份栈，然后不断读取和弹出。

---

十四、stack 的常见使用场景

栈适合处理“最近状态优先”的问题，例如：

函数调用栈
递归过程
括号匹配
表达式求值
浏览器返回
撤销操作
深度优先搜索
单调栈
字符串和数据逆序

判断一个问题是否适合栈，可以先问一句：

当前处理是否依赖最近加入、但尚未完成的元素？

如果答案是肯定的，通常可以考虑栈。

---

总结

stack 的接口不多，但应用范围很广。

学习时需要重点掌握：

1. 栈遵循后进先出规则
2. push、pop 和 top 都操作栈顶
3. pop 只删除元素，不返回元素
4. 空栈不能直接调用 top 和 pop
5. stack 是容器适配器，没有公开迭代器
6. 默认底层容器是 deque
7. 栈适合处理逆序、匹配、回退和最近状态问题

从模拟实现中也能看到，stack 并没有重新实现一套复杂的数据存储结构，而是把底层容器已有的几个接口重新组合起来。