C++栈和队列：从底层原理到环形缓冲区与工程实战

写了好几年C++，如果让我选一个“日用而不自知”的数据结构，我第一个提名栈和队列。翻代码的时候你会发现，函数调用的返回地址要入栈，消息系统要排队，线程池的任务要排队，Undo操作要入栈，表达式求值要两个栈来回倒——它们不声不响，却在程序运行的最底层托着一切。所以当你看到"C++数据结构，栈和队列"这个题目时，别觉得是学生时代的老古董，它藏了很多工程上真正值钱的东西。

这篇文章我打算用做项目的方式来讲。不讲空概念，而是先把栈和队列的本质梳理清楚，再带你把它们从零手写一遍，接着上环形缓冲区、阻塞队列、单调栈、调用栈回溯这些进阶玩法，最后把我这些年踩过的坑摊开说。适合正在学数据结构的学生、准备面试的求职者，以及想在项目里用好STL但一直没吃透底层的开发者。

1. 先说清楚：栈和队列到底在解决什么问题

1.1 两种极其底层的“存取规则”

很多人把栈和队列当成两种容器，这个理解没问题，但不彻底。它们本质上还是线性表，物理存储上要么靠数组要么靠链表，没有发明任何新的存储方式。真正区别在于操作规则：栈是后进先出（LIFO），只在栈顶一端操作；队列是先进先出（FIFO），队尾进、队头出。

一句话概括，它们就是在“数据存取的顺序”上做了强约束。栈像食堂里摞起来的餐盘，你只能拿最上面那一个；队列像早高峰的公交站，先到的人先上车。你别小看这个“限制”，限制才是效率的来源。因为只在一端操作，栈的插入和删除时间复杂度永远是 O(1)；队列在两头固定操作，同样是 O(1)。这就给了你在写代码时一个非常明确的信号：只要业务逻辑是“后进先处理”或“先进先处理”，栈和队列就是最优解，不需要纠结用什么复杂结构。

我给你一个特别实在的例子。文本编辑器的撤销功能，你用栈就对了：每一步操作压栈，Ctrl+Z 就是出栈，撤销再重做无非是再压回去。反过来，你在外卖平台下的订单，系统不可能后下单的先处理，一定是先来的单先派送，这就得用队列。存取顺序就是业务规则，选对结构等于代码成功了一半。

1.2 为什么C++里要单独设计stack和queue

C++ STL 里有两个名字很直接的容器：std::stack和std::queue。但你去看源码会发现，它们内部并没有真正“拥有”一份存储空间，而是包装了另一个容器。官方叫法：容器适配器（Container Adapters）。这是什么意思？意思就是，STL 先提供了 vector、deque、list 这些底层容器，然后 stack 和 queue 在它们之上，裁剪接口，只暴露符合语义的操作。

举个例子：

#include <stack> #include <queue> std::stack<int> st; // 默认底层是 std::deque st.push(10); // 入栈 st.push(20); int top = st.top(); // 结果是 20，但不能访问 top 以下的元素 st.pop(); std::queue<int> q; // 默认底层也是 std::deque q.push(1); // 队尾入队 q.push(2); int front = q.front(); // 结果是 1 q.pop();

这段代码里你根本感觉不到“适配”这件事，因为接口已经被打磨得很自然了。但如果你深入了解，会发现 stack 和 queue 都可以通过第二个模板参数换底层容器：

std::stack<int, std::vector<int>> st2; // 用 vector 实现栈 std::queue<int, std::list<int>> q2; // 用 list 实现队列

这就是为什么我说 C++ 的栈和队列值得单独拿出来讲。它一方面给了你语义明确的抽象，另一方面把底层选择权留给你。你写业务代码时，不需要自己写 push/pop 的边界处理；而一旦你理解了适配器模式，面对“为什么默认 deque 而不是 vector”这种问题时，你也能一眼看穿。

2. 从零手写：用C++实现一个栈和队列

2.1 基于 vector 实现栈：两分钟就能写出来

说实话，要在工程里用栈，直接std::stack就好。但我仍然建议你动手写一遍。原因很现实：嵌入式开发很多环境没有完整的 STL；面试时人家会让你手写；更重要的是，写下这个过程，你才能真正理解“栈为什么能 O(1)”。

基于 vector 实现栈，本质上就四个操作：push对应push_back，pop对应pop_back，top对应back，empty看size是不是 0。完整代码如下：

#include <vector> #include <cassert> template <typename T> class MyStack { public: void push(const T& value) { data_.push_back(value); } void pop() { assert(!data_.empty()); // 空栈禁止出栈 data_.pop_back(); } T& top() { assert(!data_.empty()); return data_.back(); } const T& top() const { assert(!data_.empty()); return data_.back(); } bool empty() const { return data_.empty(); } size_t size() const { return data_.size(); } private: std::vector<T> data_; };

我加了assert，这是手写容器时最容易忽略的细节。很多人写完栈，top()和pop()里不判空，自己用的时候心里清楚，可代码一交接，别人在空栈上调用pop，vector 的back()是未定义行为，轻则读到垃圾值，重则直接越界崩溃。任何容器类，对外暴露接口之前，先把边界条件想清楚。

还要留意扩容问题。vector 在空间不足时会申请新内存并把旧数据搬过去，均摊下来 push 还是 O(1)。但如果你做的是实时系统，怕偶发卡顿，可以先reserve一块足够大的空间，把扩容动作提前。

2.2 基于链表实现栈和队列：动态增长的另一面

链表实现的栈，思路更纯粹。入栈就在链表头插入一个新节点，出栈就删头节点，取顶就取头节点的值。队列则反过来，入队加在尾部（需要维护尾指针），出队删头部。

template <typename T> struct Node { T value; Node* next; Node(const T& v, Node* n = nullptr) : value(v), next(n) {} }; template <typename T> class LinkedQueue { public: LinkedQueue() : head_(nullptr), tail_(nullptr), size_(0) {} ~LinkedQueue() { while (head_ != nullptr) { Node<T>* cur = head_; head_ = head_->next; delete cur; } } void push(const T& value) { Node<T>* node = new Node<T>(value); if (tail_ == nullptr) { head_ = tail_ = node; } else { tail_->next = node; tail_ = node; } ++size_; } void pop() { assert(head_ != nullptr); Node<T>* old = head_; head_ = head_->next; if (head_ == nullptr) { tail_ = nullptr; } delete old; --size_; } T& front() { assert(head_ != nullptr); return head_->value; } bool empty() const { return size_ == 0; } size_t size() const { return size_; } private: Node<T>* head_; Node<T>* tail_; size_t size_; };

这段代码里我故意把pop()里的“删完后链表变空”处理写出来了。很多人写链式队列时只更新head_，忘了tail_。结果下次push时tail_->next直接空指针解引用，程序崩得莫名其妙。链表实现的队列，真正的难点是维护尾指针的状态一致性。

链表和数组的比较也要说清楚。链表优点是没有容量上限，插入即分配；缺点是每个节点多一个next指针，内存占用偏大，而且节点在堆上零散分布，CPU 缓存命中率低。数组（vector）正好相反：连续内存，遍历友好，但扩容时要拷贝。所以工程上，栈和队列绝大多数场景优先用数组形态，只有你确实不知道数据量上限、又要求动态扩容时，才选链式。

2.3 底层容器选型：一张表讲清楚

std::queue默认用 deque，是因为 deque 天然支持头部删除和尾部插入都是 O(1)，而且比 list 缓存友好。但如果你明确知道任务量有上限，自己用std::vector加头尾下标模拟环形队列，性能和可控性往往更好，这个后面第三章细说。

3. 环形缓冲区：循环队列的实现与工程价值

3.1 循环队列为什么存在

用数组实现队列时，你会碰到一个尴尬：队头元素出队后，数组前面的空间就空了，但tail下标还在往后走，后面明明还有位置，却只能继续向后扩展，直到tail超出数组长度报错。这就叫假溢出。解决办法就是把数组首尾相接，tail走到最后一块时，用取模回到开头复用空闲空间。这就是循环队列，也叫环形缓冲区。

很多数据结构教材里循环队列的经典公式我都记得：假设数组长度是 m，队尾是rear，队列元素个数是length，那么队头front = (rear - length + m) % m。你不用死记，理解一件事就行：环形结构下，所有下标增减都要取模，否则就越界了。

这里插一个面试常考的特点：环形队列的判空和判满，是整个实现里的精华。因为队列为空和队列为满时，rear和front可能指向同一个位置。如果不处理，新元素到底能不能继续塞进去就成了薛定谔的问题。

3.2 判空判满的三种方案（附完整实现）

业界常用的判空判满方案有三种：

• 方案一：额外记录 size 或 length。队列里到底有多少个元素是明确知道的，空就是 size == 0，满就是 size == capacity。最简单，最不容易错。
• 方案二：牺牲一个存储单元。当(rear + 1) % capacity == front时认为队满。数组里永远留一个空位，用来区分空和满，因为空时front == rear。
• 方案三：加 tag 标记位。每次入队置 tag=1，出队置 tag=0，当front == rear时靠 tag 判断是空还是满。

工程上我用得最多的是方案一，因为代价只是多一个 size_t 变量，换来的是代码逻辑直白。下面用方案一写一个完整的环形队列：

template <typename T> class RingQueue { public: explicit RingQueue(size_t capacity) : data_(capacity), capacity_(capacity), front_(0), rear_(0), size_(0) {} bool push(const T& value) { if (size_ >= capacity_) { return false; // 队满，入队失败 } data_[rear_] = value; rear_ = (rear_ + 1) % capacity_; ++size_; return true; } bool pop(T& out) { if (size_ == 0) { return false; // 队空，出队失败 } out = data_[front_]; front_ = (front_ + 1) % capacity_; --size_; return true; } bool empty() const { return size_ == 0; } bool full() const { return size_ >= capacity_; } size_t size() const { return size_; } private: std::vector<T> data_; size_t capacity_; size_t front_; size_t rear_; size_t size_; };

这个实现已经把最关键的点写出来了：push里先判满，再写数据，然后rear_用(rear_ + 1) % capacity_回绕；pop里先判空，再取数据，然后front_同样做模运算。两个操作的返回值可以直接代表成不成功，调用方因此不用靠异常。

这里我要特别强调一个容易踩的坑：capacity 必须大于 0，而且底层数组真正的容器大小就是 capacity，别再画蛇添足多分配一格。如果你把数组初始化为capacity + 1，但逻辑容量又是 capacity，那按取模算出来的 front_ 和 rear_ 永远到不了那个多余的位置，白占内存还让代码难读。

3.3 工业级环形缓冲区：阻塞队列与线程池

循环队列写出来之后，马上就能装进线程池的任务队列里。生产者往队列里提交任务，消费者从队列里取任务。问题是多线程下不能直接读写，因为有数据竞争。标准做法是用互斥锁加条件变量包一层：

#include <condition_variable> #include <mutex> template <typename T> class BlockingQueue { public: explicit BlockingQueue(size_t capacity) : capacity_(capacity) {} void push(const T& value) { { std::unique_lock<std::mutex> lock(mutex_); not_full_.wait(lock, [this]() { return queue_.size() < capacity_; }); queue_.push(value); } not_empty_.notify_one(); } T pop() { std::unique_lock<std::mutex> lock(mutex_); not_empty_.wait(lock, [this]() { return !queue_.empty(); }); T value = queue_.front(); queue_.pop(); not_full_.notify_one(); return value; } private: std::queue<T> queue_; size_t capacity_; std::mutex mutex_; std::condition_variable not_full_; std::condition_variable not_empty_; };

这段代码里两个条件变量是关键。push时如果队列满了，生产者在not_full_上挂起等待；pop后通知not_full_，唤醒等待的生产者继续塞任务。反过来，pop时如果队列空了，消费者在not_empty_上等待；新任务入队后通知not_empty_唤醒消费者。这就是线程池里“抢不到任务就睡觉，来了任务再起床”的经典模型。

如果你对性能要求更高，希望尽量减少锁竞争，那就得上无锁队列。在 C++ 里做无锁队列，离不开std::atomic和 CAS 操作。比如生产者只修改尾指针，消费者只修改头指针，把front_和rear_设计成原子变量，用 CAS 循环代替锁。这个方向 C++ 开发者值得重点研究，因为现代 CPU 的原子指令比想象中便宜，而锁的休眠唤醒成本在低延迟场景里很疼。但要提醒你，无锁编程是深水区，先精读并发内存模型，再带着压力测试去验证，不要在生产环境里拍脑袋首用。

4. 进阶玩法：单调栈、双端队列与调用栈回溯

4.1 单调栈：从“下一位更大元素”看栈的妙用

基础栈讲完了，说一个特别考验“栈思维”的进阶食物：单调栈。它指栈内元素按照从栈底到栈顶单调递增或递减排列。每次入栈前，把破坏单调性的元素全部弹出，再压入新元素。用这个操作，可以在 O(n) 时间内解决一类“找下一个更大/更小元素”的题。

经典问题是：给你一个数组，返回每个元素右边第一个比它大的元素下标，不存在就返回 -1。暴力解法是双层循环 O(n²)，数据量一大就完蛋。单调栈的做法是：

std::vector<int> nextGreaterElement(const std::vector<int>& nums) { std::vector<int> result(nums.size(), -1); std::stack<int> st; // 栈里存下标 for (int i = 0; i < nums.size(); ++i) { // 当前元素比栈顶对应元素大，说明栈顶元素的“下一个更大元素”找到了 while (!st.empty() && nums[i] > nums[st.top()]) { result[st.top()] = i; st.pop(); } st.push(i); } return result; }

你把这段代码跑一遍，就会发现一个神奇的事实：每个元素最多入栈一次、出栈一次，整体时间复杂度 O(n)。单调栈的核心思想是，利用栈维护一个“等待被解答”的候选序列。栈顶元素总是那些还没找到答案的元素中位置最靠后的那个。因此，新来的元素只需要和栈顶比较，不需要和前面的每个元素都比一遍。这也是栈“只在一端操作”这个限制带来的优势：它天然帮你剪掉了大量无效比较。

类似题目还有接雨水、柱状图中最大的矩形、每日温度。我建议你用这三种题反复练单调栈，练熟了以后遇到“下一个/前一个更大更小”的题，你会像条件反射一样想到它。

4.2 双端队列 deque：灵活的两端结构

讲完单调栈，还没法不提它的兄弟std::deque。deque 全称 double-ended queue，两边都能 O(1) 插入删除。它的经典使用场景是滑动窗口最大值。给你一个数组和一个窗口大小 k，每次窗口移动一格，要求输出当前窗口的最大值。这里如果用循环扫描，每格都要 O(k)，但用双端队列配合单调性，能把整体复杂度压到 O(n)。

思路是这样的：队列里存的是数组下标，且始终保持队头到队尾对应的元素值单调递减。每次窗口滑动时：

1. 队头下标如果滑出窗口了，先弹出；
2. 新元素从队尾入队前，把队尾所有小于等于它的元素弹出（因为它们不可能是窗口最大值了）；
3. 队头始终是当前窗口最大值。

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) { std::vector<int> result; std::deque<int> dq; // 存下标 for (int i = 0; i < nums.size(); ++i) { // 1. 淘汰滑出窗口的下标 if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); } // 2. 维护队列单调递减 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); // 3. 窗口满 k 个元素后开始收结果 if (i >= k - 1) { result.push_back(nums[dq.front()]); } } return result; }

这里 deque 的“双端”才能做干净：队头负责丢弃滑出窗口的旧下标，队尾负责淘汰不可能成为最大值的矮个子元素。如果换成普通队列，你要么得额外维护一个优先级队列（其实是 O(n log n)），要么就得退回去扫描。所以选对结构，不只是常数级别的优化，可能直接改变算法复杂度。

4.3 函数调用栈与backtrace栈回溯

栈不只是你代码里的一个std::stack，它还是程序运行时内存区的基石。每次函数调用，操作系统都会往调用栈里压入一帧（stack frame），保存返回地址、局部变量、参数等内容；函数返回时再弹出这一帧。这就是为什么 C++ 里递归太深会栈溢出——你申请的函数调用帧太多，把栈内存耗光了。

在实际开发中，程序崩溃时最重要的诊断手段之一就是栈回溯，也就是常说的 backtrace。在 Linux 上，backtrace()函数可以打印出从当前位置往外的所有函数调用序列，帮你精准定位崩溃点在哪个调用链上。

#include <execinfo.h> #include <cstdio> #include <cstdlib> void print_backtrace() { void* frames[32]; int size = backtrace(frames, 32); char** symbols = backtrace_symbols(frames, size); for (int i = 0; i < size; ++i) { printf("%s\n", symbols[i]); } free(symbols); } void foo() { print_backtrace(); } int main() { foo(); return 0; }

打印结果会是一串形如./a.out(func+0x1a)[0x401234]的行，从当前栈帧一直回溯到 main。如果你在崩溃处理器里调用这个函数，能让你在程序挂掉前拿到最后一段调用路径。这是排查线上 C++ 崩溃问题时的保命技能。在嵌入式或 ARM 环境下，对应的做法叫“ARM 调用栈回溯”，原理一致，但在编译时需要保留帧指针，使用-fno-omit-frame-pointer，否则栈回溯会拿到错误地址。

5. 常见问题与避坑记录（实操实录）

5.1 迭代器失效与引用失效

STL 容器用久了，一个隐蔽的大坑是迭代器失效。std::vector作为栈的底层时，push触发了扩容，原先保存的所有迭代器和引用全部失效。如果你此时还拿着旧迭代器去访问栈顶，读到的可能是旧内存里的陈旧数据，甚至直接段错误。

另一个容易被忽略的是引用失效。std::queue的front()返回引用，但如果你在持有该引用期间继续执行push，内部 deque 可能重新分配内存，旧引用就悬空了。我因为这个吃过一次大亏：多线程里一个线程在操作front()返回的对象，另一个线程还在往队列里塞数据，程序跑到线上突然崩溃，复制了好久才复现出来。后来统一改成auto value = q.front(); q.pop();，把值先拷出来再操作，问题根绝。

给所有 C++ 新手的建议：容器修改后，之前拿到的迭代器和引用，默认都当成无效，不要再用。

5.2 栈溢出与递归深度控制

递归函数每调用一层，就会在调用栈上分配一帧。Linux 默认用户栈大小通常是 8MB，Windows 默认主线程栈约 1MB。如果你写了一个无限递归的深度优先搜索（DFS），很快就能把栈填满，然后拿到一个Segmentation Fault，而且栈回溯在崩溃时往往也别想顺利打印出来。

我的经验是：

• 深度可能很大的遍历，优先用显式栈加循环代替递归；
• 必要时在递归函数里加一个深度计数器，比如超过 10000 层直接返回错误；
• 嵌入式开发者可以用链接脚本调整栈大小，但别调得太大，因为栈和堆共用一块内存区域；
• Windows 下可以用_beginthread创建线程时指定大一点的栈大小，或者通过编译器选项/F增加主线程栈。

记住，栈溢出不只是在“栈和队列”章节里的一道考题，它是线上 C++ 服务崩溃的高发原因之一。

5.3 STL queue 的内存堆积问题

std::queue用得爽了，你会忽略一个隐患：它默认底层是 deque，deque 内部按块分配内存，但pop频繁之后，有没有内存堆积？STL 的实现细节不同，不过比较稳妥的做法是在处理“高频入队出队、且峰值流量可控”的场景时，不要反复用 STL queue 拼系统，而是自己用环形数组包一层。这样容量固定，不会有动态扩容的偶发延迟，也不会因为 deque 中间块释放策略让你困惑。

如果你只想清空一个std::queue，不要一个个 pop，业界常用技巧是std::queue<int>().swap(q);这样直接把整个队列里控，底层内存随之释放。慢速 pop 会花费 O(n) 且不一定释放底层内存，用 swap 一句搞定。这种小技巧，写代码时想不到，真到排查内存才知道它的好。

5.4 栈和队列的手写边界条件自查清单

手写栈和队列时，我总结了一个 5 条自查表，写完代码立刻对着过一遍：

• 空结构执行 pop / top / front，结果是否安全？
• 满结构执行 push，是报错、覆盖、还是扩容？行为是否符合接口约定？
• 环形队列的 front 和 rear 回绕后，size 是否正确更新？
• 链表队列删除最后一个节点后，tail 是否同步为空？
• 异常路径下，内存会不会泄漏？持有的锁会不会释放？

不要小看这个清单。面试时考官反复追问，其实就是想看你在边界条件下会不会崩。工程上，出 bug 的往往也是这些地方。写容器代码，先把空、满、回绕、悬空这四个状态写到测试用例里，再谈功能。

说到这，忍不住再分享一个我的习惯。每次写完一个跟栈、队列相关的模块，我都会打印一份“状态变更日志”，记录 push/pop 前后的 size、front、rear。别看这个动作土，排查循环队列“数据追尾”和“读空队列”这类问题时，它是最快锁定现场的方式。C++ 的栈和队列看起来简单，但用得好的人，靠的从来不是背接口，而是真正理解它们背后的顺序约束和边界条件。你手头如果正好有一个项目需要任务排队、撤销回退或者函数调用定位，试着先把这篇文章里的最小实现跑起来，再一步步往上叠需求，会比直接抄一堆大而全的库更像一个成熟开发者。