C++基础：（十四）stack的深度解析与模拟实现

_OP_CHEN

发布于 2026-01-14 09:58:11

1250

文章被收录于专栏：C++C++

前言

在 C++ STL（标准模板库）中，stack（栈）、queue（队列）和 priority_queue（优先队列）是三种常用的容器适配器。它们并非独立的容器，而是基于底层容器封装而来，提供了特定场景下的高效数据操作接口。本文将先从stack入手，从基础概念、核心接口、模拟实现、实战应用到底层原理，全方位解析，帮助大家深入理解其设计思想与使用场景，提升 C++ 编程效率。下面就让我们正式开始吧！

一、容器适配器概述

在正式讲解 stack 之前，我们首先需要明确 “容器适配器” 的概念。

1.1 什么是容器适配器

适配器（Adapter）是一种设计模式，其核心思想是将一个类的接口转换成客户期望的另一个接口，使得原本因接口不兼容而无法协同工作的类能够一起工作。

在 STL 中，容器适配器并非直接实现数据存储，而是通过封装底层容器（如 vector、list、deque），并提供一组特定的成员函数来访问元素。这种设计的优势在于：

复用现有容器的底层实现，减少代码冗余；
屏蔽底层容器的复杂细节，提供简洁、直观的操作接口；
针对特定使用场景优化接口设计，提升开发效率。

stack、queue 和 priority_queue 均属于容器适配器，它们分别对应 “后进先出”“先进先出” 和 “优先级排序” 三种数据访问模式，适用于不同的业务场景。

1.2 STL 容器适配器的底层容器选择

STL 中每种容器适配器都支持指定底层容器（默认提供了默认实现），选择底层容器的核心原则是：底层容器必须支持适配器所需的所有操作接口。

后续章节将详细介绍 stack、queue 和 priority_queue 的默认底层容器及选择原因，此处先给出三者的底层容器要求：

容器适配器	核心操作需求	支持的底层容器	默认底层容器
stack	尾插、尾删、访问尾元素	vector、list、deque	deque
queue	尾插、头删、访问头 / 尾元素	list、deque	deque
priority_queue	尾插、尾删、随机访问、堆排序	vector、deque	vector

二、stack 深度解析

2.1 stack 的概念与特性

stack（栈）是一种遵循 “后进先出”（LIFO，Last In First Out）原则的线性数据结构。想象一下日常生活中的叠盘子：最后放上去的盘子，会被最先拿下来，这就是栈的核心特性。

stack 的核心操作集中在 “栈顶”（即数据的尾部）：

只能在栈顶插入元素（压栈，push）；
只能从栈顶删除元素（出栈，pop）；
只能访问栈顶元素（top）。

这种受限的操作方式使得 stack 特别适用于需要 “回溯” 或 “临时存储” 的场景，例如函数调用栈、表达式求值、括号匹配等。

2.2 stack 的核心接口与使用示例

STL 为 stack 提供了简洁易用的接口，下表列出了 stack 的常用成员函数：

函数声明	接口说明
stack()	构造一个空的栈
empty()	检测栈是否为空，为空返回 true，否则返回 false
size()	返回栈中有效元素的个数
top()	返回栈顶元素的引用（非 const 对象调用）
const T& top() const	返回栈顶元素的 const 引用（const 对象调用）
push(const T& x)	将元素 x 压入栈顶
pop()	删除栈顶元素（不返回元素值）

2.2.1 基本使用示例

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

int main() {
    // 构造空栈
    stack<int> st;
    
    // 压栈操作
    st.push(10);
    st.push(20);
    st.push(30);
    
    cout << "栈的大小：" << st.size() << endl;  // 输出：3
    cout << "栈顶元素：" << st.top() << endl;    // 输出：30
    
    // 出栈操作
    st.pop();
    cout << "出栈后栈顶元素：" << st.top() << endl;  // 输出：20
    cout << "出栈后栈的大小：" << st.size() << endl;  // 输出：2
    
    // 检测栈是否为空
    while (!st.empty()) {
        cout << "出栈元素：" << st.top() << endl;
        st.pop();
    }
    cout << "栈是否为空：" << (st.empty() ? "是" : "否") << endl;  // 输出：是
    
    return 0;
}

2.2.2 注意事项

pop()函数只删除栈顶元素，不返回该元素的值。如果需要获取栈顶元素并删除，需先调用top()获取值，再调用pop()删除；
访问top()前，必须确保栈不为空（可通过empty()检测），否则会导致未定义行为；
stack 不支持遍历操作（没有迭代器），这是由其 “后进先出” 的特性决定的，只能通过不断出栈来访问所有元素。

2.3 stack 的模拟实现

从 stack 的接口需求来看，只要底层容器支持push_back()（尾插）、pop_back()（尾删）、back()（访问尾元素）、size()（获取大小）和empty()（检测为空）这几个操作，就可以作为 stack 的底层容器。

STL 中 stack 的默认底层容器是 deque，也可以指定 vector 或 list 作为底层容器。下面我们分别基于 vector 和 deque 实现 stack，帮助理解其封装逻辑。

2.3.1 基于 vector 的 stack 模拟实现

#include <vector>
#include <cassert>
namespace bite {
    template <class T, class Container = std::vector<T>>
    class stack {
    public:
        // 构造函数：默认构造，依赖底层容器的默认构造
        stack() {}
        
        // 压栈：调用底层容器的push_back
        void push(const T& x) {
            _container.push_back(x);
        }
        
        // 出栈：调用底层容器的pop_back，需确保栈不为空
        void pop() {
            assert(!empty());
            _container.pop_back();
        }
        
        // 访问栈顶元素：调用底层容器的back，需确保栈不为空
        T& top() {
            assert(!empty());
            return _container.back();
        }
        
        // const版本的top，支持const对象调用
        const T& top() const {
            assert(!empty());
            return _container.back();
        }
        
        // 获取栈的大小：调用底层容器的size
        size_t size() const {
            return _container.size();
        }
        
        // 检测栈是否为空：调用底层容器的empty
        bool empty() const {
            return _container.empty();
        }
        
    private:
        Container _container;  // 底层容器，封装具体的存储与操作
    };
}

2.3.2 基于 deque 的 stack 模拟实现

deque（双端队列）是 STL 中专门为两端操作优化的数据结构，作为 stack 的底层容器时，扩容效率比 vector 更高（无需搬移大量元素）。模拟实现如下：

#include <deque>
#include <cassert>
namespace bite {
    template <class T, class Container = std::deque<T>>
    class stack {
    public:
        stack() {}
        
        void push(const T& x) {
            _container.push_back(x);
        }
        
        void pop() {
            assert(!empty());
            _container.pop_back();
        }
        
        T& top() {
            assert(!empty());
            return _container.back();
        }
        
        const T& top() const {
            assert(!empty());
            return _container.back();
        }
        
        size_t size() const {
            return _container.size();
        }
        
        bool empty() const {
            return _container.empty();
        }
        
    private:
        Container _container;
    };
}

2.3.3 模拟实现的测试

#include <iostream>
#include "stack.hpp"  // 包含上面的模拟实现
using namespace std;
using namespace bite;

int main() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    
    cout << "size: " << st.size() << endl;  // 3
    cout << "top: " << st.top() << endl;    // 3
    
    st.pop();
    cout << "after pop, top: " << st.top() << endl;  // 2
    
    const stack<int> cst = st;
    cout << "const stack top: " << cst.top() << endl;  // 2
    
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    // 输出：2 1
    
    return 0;
}

2.4 stack 的经典实战场景

stack 的 “后进先出” 特性使其在多个算法场景中发挥重要作用，以下我为大家提供了几个典型的 OJ 题目及其解析。

2.4.1 最小栈（LeetCode 155）

题目描述：设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

解题思路：

核心需求：在 O (1) 时间内获取最小值，常规栈无法直接满足，需额外维护一个 “最小栈”；
设计思路：
1. 用一个主栈_elem存储所有元素；
2. 用一个辅助栈_min存储当前栈中的最小值，_min的栈顶始终是主栈中当前的最小元素；
3. 压栈时：若新元素小于等于_min的栈顶元素（或_min为空），则同时压入_min；
4. 出栈时：若主栈出栈的元素等于_min的栈顶元素，则_min也出栈；
5. 获取最小值时：直接返回_min的栈顶元素。

代码实现：

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

class MinStack {
public:
    MinStack() {}
    
    void push(int x) {
        // 主栈压入元素
        _elem.push(x);
        // 辅助栈压入当前最小值
        if (_min.empty() || x <= _min.top()) {
            _min.push(x);
        }
    }
    
    void pop() {
        assert(!_elem.empty());
        // 若主栈出栈元素是最小值，辅助栈也出栈
        if (_elem.top() == _min.top()) {
            _min.pop();
        }
        _elem.pop();
    }
    
    int top() {
        assert(!_elem.empty());
        return _elem.top();
    }
    
    int getMin() {
        assert(!_min.empty());
        return _min.top();
    }
    
private:
    stack<int> _elem;  // 存储所有元素的主栈
    stack<int> _min;   // 存储最小值的辅助栈
};

// 测试代码
int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl;  // 输出：-3
    minStack.pop();
    cout << minStack.top() << endl;     // 输出：0
    cout << minStack.getMin() << endl;  // 输出：-2
    return 0;
}

2.4.2 栈的压入、弹出序列（剑指 Offer 31）

题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

解题思路：

模拟栈的压入和弹出过程：
1. 用一个辅助栈模拟压入操作；
2. 按压入序列依次压入元素，每压入一个元素，就检查栈顶元素是否与弹出序列的当前元素一致；
3. 若一致，则弹出栈顶元素，并移动弹出序列的指针；
4. 重复上述步骤，直到压入序列处理完毕；
5. 若辅助栈为空，则弹出序列有效；否则无效。

代码实现：

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

class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        // 压入序列和弹出序列长度不一致，直接返回false
        if (pushV.size() != popV.size()) {
            return false;
        }
        
        stack<int> st;
        int inIdx = 0;   // 压入序列的索引
        int outIdx = 0;  // 弹出序列的索引
        
        while (outIdx < popV.size()) {
            // 当栈为空或栈顶元素不等于当前弹出元素时，继续压入
            while (st.empty() || st.top() != popV[outIdx]) {
                if (inIdx < pushV.size()) {
                    st.push(pushV[inIdx++]);
                } else {
                    // 压入序列已处理完，但栈顶仍不匹配，返回false
                    return false;
                }
            }
            // 栈顶元素匹配，弹出
            st.pop();
            outIdx++;
        }
        
        // 所有弹出元素均匹配，返回true
        return true;
    }
};

// 测试代码
int main() {
    Solution sol;
    vector<int> pushV = {1,2,3,4,5};
    vector<int> popV1 = {4,5,3,2,1};
    vector<int> popV2 = {4,3,5,1,2};
    
    cout << sol.IsPopOrder(pushV, popV1) << endl;  // 输出：1（true）
    cout << sol.IsPopOrder(pushV, popV2) << endl;  // 输出：0（false）
    return 0;
}

2.4.3 逆波兰表达式求值（LeetCode 150）

题目描述：根据逆波兰表示法，求表达式的值。逆波兰表达式是一种后缀表达式，运算符位于操作数之后。

解题思路：

逆波兰表达式的求值规则：
1. 遇到数字时，压入栈；
2. 遇到运算符时，弹出栈顶的两个元素（注意顺序：后弹出的是左操作数，先弹出的是右操作数）；
3. 计算两个元素的运算结果，将结果压入栈；
4. 表达式处理完毕后，栈中剩余的唯一元素即为结果。

代码实现：

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

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        
        for (size_t i = 0; i < tokens.size(); ++i) {
            string& str = tokens[i];
            // 判断是否为运算符（题目中运算符仅为+、-、*、/）
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                // 弹出右操作数
                int right = st.top();
                st.pop();
                // 弹出左操作数
                int left = st.top();
                st.pop();
                // 计算结果并压栈
                switch (str[0]) {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        // 题目保证除数不为0，且结果为整数（截断 towards zero）
                        st.push(left / right);
                        break;
                }
            } else {
                // 数字字符串，转换为整数后压栈
                st.push(atoi(str.c_str()));
            }
        }
        
        // 栈中剩余的唯一元素即为结果
        return st.top();
    }
};

// 测试代码
int main() {
    Solution sol;
    vector<string> tokens1 = {"2", "1", "+", "3", "*"};
    vector<string> tokens2 = {"4", "13", "5", "/", "+"};
    vector<string> tokens3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    
    cout << sol.evalRPN(tokens1) << endl;  // 输出：9
    cout << sol.evalRPN(tokens2) << endl;  // 输出：6
    cout << sol.evalRPN(tokens3) << endl;  // 输出：22
    return 0;
}