写了好几年C如果让我选一个“日用而不自知”的数据结构我第一个提名栈和队列。翻代码的时候你会发现函数调用的返回地址要入栈消息系统要排队线程池的任务要排队Undo操作要入栈表达式求值要两个栈来回倒——它们不声不响却在程序运行的最底层托着一切。所以当你看到C数据结构栈和队列这个题目时别觉得是学生时代的老古董它藏了很多工程上真正值钱的东西。这篇文章我打算用做项目的方式来讲。不讲空概念而是先把栈和队列的本质梳理清楚再带你把它们从零手写一遍接着上环形缓冲区、阻塞队列、单调栈、调用栈回溯这些进阶玩法最后把我这些年踩过的坑摊开说。适合正在学数据结构的学生、准备面试的求职者以及想在项目里用好STL但一直没吃透底层的开发者。1. 先说清楚栈和队列到底在解决什么问题1.1 两种极其底层的“存取规则”很多人把栈和队列当成两种容器这个理解没问题但不彻底。它们本质上还是线性表物理存储上要么靠数组要么靠链表没有发明任何新的存储方式。真正区别在于操作规则栈是后进先出LIFO只在栈顶一端操作队列是先进先出FIFO队尾进、队头出。一句话概括它们就是在“数据存取的顺序”上做了强约束。栈像食堂里摞起来的餐盘你只能拿最上面那一个队列像早高峰的公交站先到的人先上车。你别小看这个“限制”限制才是效率的来源。因为只在一端操作栈的插入和删除时间复杂度永远是 O(1)队列在两头固定操作同样是 O(1)。这就给了你在写代码时一个非常明确的信号只要业务逻辑是“后进先处理”或“先进先处理”栈和队列就是最优解不需要纠结用什么复杂结构。我给你一个特别实在的例子。文本编辑器的撤销功能你用栈就对了每一步操作压栈CtrlZ 就是出栈撤销再重做无非是再压回去。反过来你在外卖平台下的订单系统不可能后下单的先处理一定是先来的单先派送这就得用队列。存取顺序就是业务规则选对结构等于代码成功了一半。1.2 为什么C里要单独设计stack和queueC STL 里有两个名字很直接的容器std::stack和std::queue。但你去看源码会发现它们内部并没有真正“拥有”一份存储空间而是包装了另一个容器。官方叫法容器适配器Container Adapters。这是什么意思意思就是STL 先提供了 vector、deque、list 这些底层容器然后 stack 和 queue 在它们之上裁剪接口只暴露符合语义的操作。举个例子#include stack #include queue std::stackint st; // 默认底层是 std::deque st.push(10); // 入栈 st.push(20); int top st.top(); // 结果是 20但不能访问 top 以下的元素 st.pop(); std::queueint q; // 默认底层也是 std::deque q.push(1); // 队尾入队 q.push(2); int front q.front(); // 结果是 1 q.pop();这段代码里你根本感觉不到“适配”这件事因为接口已经被打磨得很自然了。但如果你深入了解会发现 stack 和 queue 都可以通过第二个模板参数换底层容器std::stackint, std::vectorint st2; // 用 vector 实现栈 std::queueint, std::listint q2; // 用 list 实现队列这就是为什么我说 C 的栈和队列值得单独拿出来讲。它一方面给了你语义明确的抽象另一方面把底层选择权留给你。你写业务代码时不需要自己写 push/pop 的边界处理而一旦你理解了适配器模式面对“为什么默认 deque 而不是 vector”这种问题时你也能一眼看穿。2. 从零手写用C实现一个栈和队列2.1 基于 vector 实现栈两分钟就能写出来说实话要在工程里用栈直接std::stack就好。但我仍然建议你动手写一遍。原因很现实嵌入式开发很多环境没有完整的 STL面试时人家会让你手写更重要的是写下这个过程你才能真正理解“栈为什么能 O(1)”。基于 vector 实现栈本质上就四个操作push对应push_backpop对应pop_backtop对应backempty看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::vectorT data_; };我加了assert这是手写容器时最容易忽略的细节。很多人写完栈top()和pop()里不判空自己用的时候心里清楚可代码一交接别人在空栈上调用popvector 的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) { NodeT* cur head_; head_ head_-next; delete cur; } } void push(const T value) { NodeT* node new NodeT(value); if (tail_ nullptr) { head_ tail_ node; } else { tail_-next node; tail_ node; } size_; } void pop() { assert(head_ ! nullptr); NodeT* 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: NodeT* head_; NodeT* tail_; size_t size_; };这段代码里我故意把pop()里的“删完后链表变空”处理写出来了。很多人写链式队列时只更新head_忘了tail_。结果下次push时tail_-next直接空指针解引用程序崩得莫名其妙。链表实现的队列真正的难点是维护尾指针的状态一致性。链表和数组的比较也要说清楚。链表优点是没有容量上限插入即分配缺点是每个节点多一个next指针内存占用偏大而且节点在堆上零散分布CPU 缓存命中率低。数组vector正好相反连续内存遍历友好但扩容时要拷贝。所以工程上栈和队列绝大多数场景优先用数组形态只有你确实不知道数据量上限、又要求动态扩容时才选链式。2.3 底层容器选型一张表讲清楚底层容器栈顶/队尾操作队头操作随机访问内存布局适用场景vectorO(1) 尾插尾删不支持支持连续栈首选容量可控dequeO(1)O(1) 头插头删支持分段连续队列默认底层listO(1) 但需遍历到尾部O(1)不支持离散节点需要频繁中间插入时自定义环形数组O(1)O(1)支持连续固定大小无锁队列、音频缓冲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 标记位。每次入队置 tag1出队置 tag0当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::vectorT 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_lockstd::mutex lock(mutex_); not_full_.wait(lock, [this]() { return queue_.size() capacity_; }); queue_.push(value); } not_empty_.notify_one(); } T pop() { std::unique_lockstd::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::queueT 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::vectorint nextGreaterElement(const std::vectorint nums) { std::vectorint result(nums.size(), -1); std::stackint 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)。思路是这样的队列里存的是数组下标且始终保持队头到队尾对应的元素值单调递减。每次窗口滑动时队头下标如果滑出窗口了先弹出新元素从队尾入队前把队尾所有小于等于它的元素弹出因为它们不可能是窗口最大值了队头始终是当前窗口最大值。std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { std::vectorint result; std::dequeint 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(func0x1a)[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 默认用户栈大小通常是 8MBWindows 默认主线程栈约 1MB。如果你写了一个无限递归的深度优先搜索DFS很快就能把栈填满然后拿到一个Segmentation Fault而且栈回溯在崩溃时往往也别想顺利打印出来。我的经验是深度可能很大的遍历优先用显式栈加循环代替递归必要时在递归函数里加一个深度计数器比如超过 10000 层直接返回错误嵌入式开发者可以用链接脚本调整栈大小但别调得太大因为栈和堆共用一块内存区域Windows 下可以用_beginthread创建线程时指定大一点的栈大小或者通过编译器选项/F增加主线程栈。记住栈溢出不只是在“栈和队列”章节里的一道考题它是线上 C 服务崩溃的高发原因之一。5.3 STL queue 的内存堆积问题std::queue用得爽了你会忽略一个隐患它默认底层是 dequedeque 内部按块分配内存但pop频繁之后有没有内存堆积STL 的实现细节不同不过比较稳妥的做法是在处理“高频入队出队、且峰值流量可控”的场景时不要反复用 STL queue 拼系统而是自己用环形数组包一层。这样容量固定不会有动态扩容的偶发延迟也不会因为 deque 中间块释放策略让你困惑。如果你只想清空一个std::queue不要一个个 pop业界常用技巧是std::queueint().swap(q);这样直接把整个队列里控底层内存随之释放。慢速 pop 会花费 O(n) 且不一定释放底层内存用 swap 一句搞定。这种小技巧写代码时想不到真到排查内存才知道它的好。5.4 栈和队列的手写边界条件自查清单手写栈和队列时我总结了一个 5 条自查表写完代码立刻对着过一遍空结构执行 pop / top / front结果是否安全满结构执行 push是报错、覆盖、还是扩容行为是否符合接口约定环形队列的 front 和 rear 回绕后size 是否正确更新链表队列删除最后一个节点后tail 是否同步为空异常路径下内存会不会泄漏持有的锁会不会释放不要小看这个清单。面试时考官反复追问其实就是想看你在边界条件下会不会崩。工程上出 bug 的往往也是这些地方。写容器代码先把空、满、回绕、悬空这四个状态写到测试用例里再谈功能。说到这忍不住再分享一个我的习惯。每次写完一个跟栈、队列相关的模块我都会打印一份“状态变更日志”记录 push/pop 前后的 size、front、rear。别看这个动作土排查循环队列“数据追尾”和“读空队列”这类问题时它是最快锁定现场的方式。C 的栈和队列看起来简单但用得好的人靠的从来不是背接口而是真正理解它们背后的顺序约束和边界条件。你手头如果正好有一个项目需要任务排队、撤销回退或者函数调用定位试着先把这篇文章里的最小实现跑起来再一步步往上叠需求会比直接抄一堆大而全的库更像一个成熟开发者。