一、stack —— 后进先出的栈

1.1 stack 的介绍

std::stack 是一个容器适配器，它提供 后进先出（LIFO） 的数据结构。你可以把它想象成一摞盘子：最后放上去的盘子最先被取走。栈只允许在顶部进行插入（push）和删除（pop）操作，访问也只能访问顶部元素（top）。

栈的典型应用场景：

  • 函数调用栈（保存返回地址、局部变量）

  • 表达式求值（中缀转后缀、逆波兰表达式计算）

  • 括号匹配、撤销操作（Undo）等

1.2 stack 的常用接口

函数说明
push(x)将元素 x 压入栈顶
pop()弹出栈顶元素（无返回值）
top()返回栈顶元素的引用
empty()判断栈是否为空
size()返回栈中元素个数
#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);
    
    cout << st.top() << endl;   // 30
    st.pop();
    cout << st.top() << endl;   // 20
    cout << st.size() << endl;  // 2
    
    return 0;
}

1.3 经典 OJ 题：最小栈

题目要求：实现一个能在 O(1) 时间内获取栈中最小元素的栈。思路：使用两个栈，一个正常存元素，另一个存当前最小值。

class MinStack {
public:
    void push(int x) {
        _elem.push(x);
        if (_min.empty() || x <= _min.top())
            _min.push(x);
    }
    void pop() {
        if (_elem.top() == _min.top())
            _min.pop();
        _elem.pop();
    }
    int top() { return _elem.top(); }
    int getMin() { return _min.top(); }
private:
    stack<int> _elem;
    stack<int> _min;
};

1.4 栈的弹出压入序列

给定入栈序列和出栈序列，判断是否可能是同一个栈的弹出顺序。模拟入栈过程，当栈顶等于出栈当前元素时即弹出。

bool IsPopOrder(vector<int> pushV, vector<int> popV) {
    if (pushV.size() != popV.size()) return false;
    stack<int> s;
    int pushIdx = 0, popIdx = 0;
    while (popIdx < popV.size()) {
        while (s.empty() || s.top() != popV[popIdx]) {
            if (pushIdx < pushV.size())
                s.push(pushV[pushIdx++]);
            else
                return false;
        }
        s.pop();
        popIdx++;
    }
    return true;
}

1.5 逆波兰表达式求值

逆波兰表达式（后缀表达式）无需括号，运算符在操作数之后。用栈求值：遇到数字压栈，遇到运算符则弹出两个数字计算后压回。

int evalRPN(vector<string>& tokens) {
    stack<int> s;
    for (auto& str : tokens) {
        if (str == "+" || str == "-" || str == "*" || str == "/") {
            int right = s.top(); s.pop();
            int left = s.top(); s.pop();
            switch (str[0]) {
                case '+': s.push(left + right); break;
                case '-': s.push(left - right); break;
                case '*': s.push(left * right); break;
                case '/': s.push(left / right); break;
            }
        } else {
            s.push(atoi(str.c_str()));
        }
    }
    return s.top();
}

1.6 stack 的模拟实现

stack 本身不存储数据，而是封装一个底层容器（默认 deque），所有操作都转发给底层容器的相应成员。

namespace bit {
    template<class T, class Container = deque<T>>
    class stack {
    public:
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_back(); }
        T& top() { return _c.back(); }
        const T& top() const { return _c.back(); }
        size_t size() const { return _c.size(); }
        bool empty() const { return _c.empty(); }
    private:
        Container _c;
    };
}

二、queue —— 先进先出的队列

2.1 queue 的介绍

std::queue 也是一个容器适配器，提供 先进先出（FIFO） 的行为，就像排队一样：队尾入队（push），队头出队（pop），可以访问队头（front）和队尾（back）。

应用场景：

  • 任务队列（生产者-消费者模型）

  • 广度优先搜索（BFS）

  • 打印机任务缓冲等

2.2 queue 的常用接口

函数说明
push(x)在队尾插入元素 x
pop()弹出队头元素
front()返回队头元素的引用
back()返回队尾元素的引用
empty()判空
size()返回元素个数
#include <queue>
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl;  // 1
q.pop();
cout << q.front() << endl;  // 2

2.3 用队列实现栈（OJ 练习）

使用两个队列模拟栈的后进先出行为。思路：每次压入时，将新元素放入非空队列，然后把另一个队列的所有元素依次搬过来，保证新元素在队头。

2.4 queue 的模拟实现

queue 需要支持尾插和头删，因此底层容器不能是 vector（头删效率低），通常用 deque 或 list。

namespace bit {
    template<class T, class Container = deque<T>>
    class queue {
    public:
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_front(); }
        T& front() { return _c.front(); }
        const T& front() const { return _c.front(); }
        T& back() { return _c.back(); }
        const T& back() const { return _c.back(); }
        size_t size() const { return _c.size(); }
        bool empty() const { return _c.empty(); }
    private:
        Container _c;
    };
}

三、priority_queue —— 优先级队列（堆）

3.1 介绍

priority_queue 是一个优先队列，它的底层是堆（默认大顶堆）。每次 top() 返回的是优先级最高的元素（最大或最小）。它的接口与 stack、queue 类似，但内部使用了堆算法（make_heap、push_heap、pop_heap）。

3.2 使用

默认是大堆，即最大元素在堆顶。若要小堆，可以指定 greater 比较器。

#include <queue>
#include <vector>
#include <functional>  // greater

priority_queue<int> maxHeap;   // 大堆
maxHeap.push(3); maxHeap.push(1); maxHeap.push(4);
cout << maxHeap.top() << endl; // 4

// 小堆：参数3个，类型、容器、比较类
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(3); minHeap.push(1); minHeap.push(4);
cout << minHeap.top() << endl; // 1

对于自定义类型，需要重载 < 或 > 运算符（或者传入仿函数）。

3.3 priority_queue 模拟实现

底层是一个数组（如 vector），利用堆的向下调整和向上调整算法。

namespace bit {
    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue {
    public:
        void push(const T& x) {
            _c.push_back(x);
            push_heap(_c.begin(), _c.end(), Compare());
        }
        void pop() {
            pop_heap(_c.begin(), _c.end(), Compare());
            _c.pop_back();
        }
        T& top() { return _c.front(); }
        bool empty() const { return _c.empty(); }
        size_t size() const { return _c.size(); }
    private:
        Container _c;
    };
}

实际上，STL 提供了 push_heap / pop_heap 算法，我们也可以手写 adjust_up / adjust_down。

四、容器适配器与 deque

4.1 什么是适配器？

适配器是一种设计模式，它将一个类的接口转换为用户期望的另一个接口。在 STL 中，stack 和 queue 没有自己的数据结构，它们只是对已有容器（如 deque）的接口进行限制和包装，从而提供特定的行为。

4.2 为什么选择 deque 作为默认底层？

STL 中 stack 和 queue 的默认底层容器是 deque（双端队列）。deque 具有以下特点：

  • 支持 O(1) 的头尾插入/删除

  • 支持随机访问（但效率不如 vector）

  • 在内存布局上，它是分段连续的（由多个固定大小的缓冲区组成，并由一个中控数组管理）

对于 stack 只需要尾端操作，对于 queue 需要头尾操作，deque 恰好都能高效支持。为什么不直接用 vector 做 stack？因为 vector 也能做，但 deque 在扩容时不需要搬移所有元素（只需分配新的缓冲区），且 deque 提供了 push_front，通用性更好。为什么不直接用 list？list 每个节点额外占用指针空间，缓存不友好，而 deque 空间利用率更高。

4.3 deque 的原理简述

deque 逻辑上连续，物理上分段。它维护一个中控数组（map），每个元素是一个指针，指向一块固定大小的缓冲区（buffer）。当在头部或尾部插入时，如果当前缓冲区满了，就分配新的缓冲区并更新中控数组。随机访问时，通过中控数组和缓冲区偏移量计算实际地址。

deque 的迭代器非常复杂，需要维护当前缓冲区指针、缓冲区起始/结束边界，以及中控数组的位置，以实现跨缓冲区的自增/自减。

4.4 deque 的缺陷

  • 遍历效率低：因为迭代器需要频繁判断是否到达缓冲区边界，比 vector 的连续内存遍历慢。

  • 随机访问虽为 O(1)，但常数较大：需要两次解引用（中控+缓冲区）。

  • 中间插入/删除慢：需要搬移元素，不如 list 高效。

因此，除非需要头尾高效操作且偶尔随机访问，否则一般场景优先用 vector 或 list。

五、stack/queue 与 vector/list 的对比

特性stackqueuevectorlist
数据结构适配器适配器动态数组双向链表
访问方式仅顶部仅头尾随机访问双向顺序访问
插入删除仅顶部 O(1)头尾 O(1)尾部 O(1) 均摊，中间 O(n)任意位置 O(1)
底层容器deque（默认）deque（默认）自身自身
迭代器无无随机访问迭代器双向迭代器

六、总结

  • stack：后进先出，适合需要“回溯”或“撤销”的场景。

  • queue：先进先出，适合任务排队、广度优先遍历。

  • priority_queue：堆结构，适合动态获取最值的场景。

  • 适配器模式：通过限制已有容器的接口，实现新的语义，降低了代码复用成本。

  • deque 作为默认底层容器，平衡了内存连续性和头尾操作效率，是 stack 和 queue 的理想搭档。

掌握这些容器适配器，不仅能写出更清晰、高效的代码，还能深入理解 STL 的设计哲学。在接下来的学习中，你可以尝试用 stack 解决括号匹配、表达式求值，用 queue 实现层序遍历，用 priority_queue 解决 TopK 问题。下一篇我们将探讨关联式容器 map 和 set，敬请期待！

练习题推荐：

  • LeetCode 20. 有效的括号

  • LeetCode 150. 逆波兰表达式求值

  • LeetCode 232. 用栈实现队列

  • LeetCode 225. 用队列实现栈

  • LeetCode 215. 数组中的第K个最大元素（优先队列）

# c++ # 适配器模式 # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

avatar 亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

avatar 亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

avatar 亚马逊云科技技术品牌专区