学C学到一定程度数据结构这块儿是绕不过去的坎儿。很多人把栈Stack和队列Queue当成两个“入门级”结构草草掠过觉得无非就是后进先出、先进先出背个定义就完事了。但真正到了写项目、刷题、准备面试的时候才发现这两兄弟无处不在——函数调用栈、浏览器的前进后退、编译器表达式求值、消息中间件、线程池、操作系统缓冲区全都跟它俩挂钩。这篇文章我不打算念教科书式的定义而是从C实现的角度把栈和队列的原理、代码、工程应用、刷题要点一次说透。适合刚入门数据结构的学生也适合准备校招或者想把C基础打扎实的开发者。1. 先搞清楚栈和队列到底在解决什么问题1.1 栈是“后进先出”它的气质是“回溯”栈的操作只有三个核心动作push压栈、pop出栈、top看栈顶任何操作都只能在栈顶这一端发生。这就像一个收纳罐你先放进去的东西在最底下后放进去的在最上面要取只能从最上层一个个拿。C里用std::stack就是这种语义。这种“后进先出”的气质非常适合两类场景一类是需要“撤销”的操作另一类是需要“嵌套”才能描述的问题。浏览器返回上一页用的就是栈——每访问一个页面就压栈每点一次返回就出栈。编辑器里的CtrlZ本质上也是一个操作栈最后一次操作总是最先被撤销。递归函数的调用过程更是如此每一层函数调用都会被压入系统调用栈返回时才逐层弹出。所以栈天然跟“深度优先”绑定深搜、括号匹配、表达式求值这些经典问题都是栈的拿手好戏。1.2 队列是“先进先出”它的气质是“公平”队列就一个规矩谁先来谁先走。队尾入队enqueue队头出队dequeue。你到银行取号排队、食堂打饭排队、买奶茶排队全是队列。它的关键词是“顺序公平”和“按序处理”。凡是讲“先后顺序”的系统几乎都离不开队列。操作系统里的进程调度先来的进程先上CPU打印任务按提交顺序排队执行网络数据包按到达顺序被路由转发。消息队列这个技术产品取名的根源也在这里——它就是一个分布式环境下的“排队缓冲区”生产者把消息放进队尾消费者从队头按顺序消费。队列跟“广度优先”绑定BFS遍历二叉树、层序遍历、拓扑排序的待处理节点集合用的都是队列。1.3 栈和队列是一体两面不是对立关系两个结构明明都建立在“线性存放”这个前提上唯一的区别就是“哪个方向能操作”。栈只开放一头队列开放两头但方向固定。这个差异看起来小带来的应用场景却完全不同。我自己的理解方式是把它们当成“顺序约束的两种极端”栈是“最近的最优先”队列是“最先的最优先”。所以学习的时候不要孤立地背定义而是从“这个场景需要什么样的顺序约束”反推应该用哪个结构。需要回溯、撤销、嵌套处理选栈需要按到达顺序处理、削峰填谷、公平调度选队列。这个思维一旦建立后面看单调栈、消息队列、阻塞队列这些高级变体就容易串成一条线。2. C数组栈和链表栈怎么写我建议把两种都过一遍2.1 先看教科书风格的顺序栈实现数组栈也叫顺序栈是数据结构实验报告里最常见的模板。它的核心思路是用一块连续内存保存栈元素用一个整型下标top标记栈顶位置。空的数组栈里top -1压栈时先top再写入出栈时先取值再--top。template typename T class SeqStack { private: T* base; int top; int capacity; public: SeqStack(int cap 128) : top(-1), capacity(cap) { base new T[capacity]; } ~SeqStack() { delete[] base; } bool empty() const { return top -1; } bool full() const { return top capacity - 1; } bool push(const T val) { if (full()) return false; base[top] val; return true; } // 教科书写法pop返回弹出的元素 T pop() { if (empty()) throw std::runtime_error(stack underflow); return base[top--]; } T peek() const { if (empty()) throw std::runtime_error(stack underflow); return base[top]; } };这里有几个细节新手最容易卡住。top初始化的值决定了判空逻辑初始化为-1压入第一个元素后变成0栈顶永远指向“最后一个有效元素”也有人习惯初始化为0那push变成base[top] val判空用top 0逻辑不同但都能跑关键是别混。full()这个判断要先于赋值执行否则越界写入是典型的未定义行为崩溃都是轻的更怕的是数据悄悄被改写等到出问题已经查不出是哪一行干的。2.2 链表栈用头插法模拟栈顶链表栈的思路是用单链表保存元素规定“链表的头结点就是栈顶”。插入用头插法删除也从头结点下手时间复杂度都是O(1)完美贴合栈的操作模型。struct LinkNode { int val; LinkNode* next; LinkNode(int v) : val(v), next(nullptr) {} }; class LinkedStack { private: LinkNode* head; // 栈顶 int size; public: LinkedStack() : head(nullptr), size(0) {} ~LinkedStack() { while (head) { LinkNode* tmp head; head head-next; delete tmp; } } void push(int val) { LinkNode* node new LinkNode(val); node-next head; head node; size; } int pop() { if (!head) throw std::runtime_error(stack underflow); int val head-val; LinkNode* tmp head; head head-next; delete tmp; --size; return val; } };用链表有一个好处不用预先知道容量数据再多也不存在“栈满”的问题。坏处也很明显每个节点都要new/delete频繁申请释放小块内存实际性能比连续内存的数组栈差不少。C工程里我更推荐数组栈但链栈的实现思路一定要理解很多面试官喜欢让候选人现场手写考察的就是指针操作的熟练度。2.3 数组和链表怎么选我给一个实用标准对比维度数组栈顺序栈链表栈链栈空间分配一次性连续分配逐个节点动态分配容量固定或动态扩容理论无上限访问性能缓存友好速度快每次跳指针慢实现难度简单指针操作易出错适用场景工程、刷题、竞赛教学、面试手写如果只是做题和日常开发我会直接用std::stack或者std::vector加back()操作根本不需要自己造轮子。但自己手写过一遍最大的价值不是“造轮子”而是把内存布局、边界条件、判空判满分寸这些底层细节吃透以后遇到std::stack的报错你能直接脑补出背后发生了什么。面试手写栈的时候我建议先写数组版本代码短、思路清楚不容易翻车如果面试官追问容量扩容再聊动态扩容的策略也不迟。3. 循环队列的C实现为什么一定要预留一个空位3.1 先搞清楚顺序队列为什么有“假溢出”很多初学者第一次写顺序队列照着顺序栈的思路来一个数组、一个front下标、一个rear下标front指向队头rear指向队尾的下一个位置。入队时data[rear] val出队时取data[front]。看起来没啥问题但跑一阵子就傻眼了队头不断后移队尾也在后移前面出队留下的空位永远用不上。当rear到达数组末尾即使数组前面空着一大片队列也提示“满了”。这就是经典的“假溢出”——数组空间确实还有但逻辑上队列已经没法继续入队。解决办法有两个允许动态扩容或者把数组掰成环让rear从末尾自动绕回开头这就是循环队列。3.2 循环队列的核心写法取模运算空位法循环队列的关键是把下标用(index 1) % capacity来维护让队尾越过数组末尾后回到开头。判空和判满的条件特别容易搞混这里我建议用“预留一个空位”的做法来避免歧义队列最多只存capacity - 1个元素让rear永远不直接越过front。template typename T class CircularQueue { private: T* data; int front; // 指向队头元素 int rear; // 指向队尾的下一个空位 int capacity; public: CircularQueue(int cap 128) : front(0), rear(0), capacity(cap) { data new T[capacity]; } ~CircularQueue() { delete[] data; } bool empty() const { return front rear; } bool full() const { return (rear 1) % capacity front; } bool enqueue(const T val) { if (full()) return false; data[rear] val; rear (rear 1) % capacity; return true; } bool dequeue(T out) { if (empty()) return false; out data[front]; front (front 1) % capacity; return true; } };这段代码值得反复看几遍。full()判断用(rear 1) % capacity front意思就是“rear再往后走一步就到front了”此时必须拒绝入队。空位法牺牲一个数组元素换来一个非常干净的判满条件不需要额外记录元素个数。empty()依然是front rear这个条件在循环队列中永恒成立。有人会问能不能不浪费那一个空位用size计数来判断满/空当然可以代码也简单但每次入队出队都要维护size而且所有操作的判断逻辑都多一层状态。我自己写代码偏爱空位法因为逻辑更贴近“纯下标”思维不容易在并发或复杂调试时出隐藏bug。刷题时也建议优先套这个模板代码短、边界清楚、不会漏判。3.3 链队列如果完全不想纠结容量链队列就是单链表头尾两个指针队尾插入、队头删除。实现起来比较直接最关键的点是处理“队列为空”和“队列只有一个元素”的情况出队时要判断链表是否只剩一个节点如果是删除后要把尾指针也置空否则尾指针就成野指针了。class LinkedQueue { private: struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} }; Node* head; Node* tail; public: LinkedQueue() : head(nullptr), tail(nullptr) {} void enqueue(int val) { Node* node new Node(val); if (tail) { tail-next node; tail node; } else { head tail node; } } int dequeue() { if (!head) throw std::runtime_error(queue underflow); int val head-val; Node* tmp head; head head-next; if (!head) tail nullptr; // 别忘了把尾指针也置空 delete tmp; return val; } };我在写这段代码时踩过坑具体就是dequeue里漏了那句if (!head) tail nullptr。队列里最后一个元素出队后head变空了但tail还指着那个已经被摘除的节点下一次enqueue就会往一个悬空指针上挂节点程序直接段错误。这个细节教科书不一定会反复强调但实际写的时候特别容易翻车所以单独拿出来说。3.4 工程里常用的队列变体deque、priority_queue、blocking_queueC标准库里日常用得更多的是std::deque和std::priority_queue。std::deque是双端队列头尾都能进出底层通常是一段段连续块拼接而成很多场景下比std::queue更灵活std::priority_queue是优先队列底层实现是堆每次弹出的不是最早进来的而是优先级最高的元素适合任务调度和TopK问题。至于阻塞队列C标准库没有直接给出实现需要自己用std::mutex和std::condition_variable封装我在后面第5章会给出一个完整可用的版本。理解循环队列后再看这些变体很容易它们只是改变了进出约束或队内排序规则底层逻辑依然是“线性排队”这个地基。4. 栈的进阶用法括号匹配、中缀转后缀和单调栈4.1 括号匹配面试手写频率最高的基础题括号匹配是栈最经典的应用题目一般是这样给定一个只包含()[]{}的字符串判断括号是否合法。核心思路遇到左括号就压栈遇到右括号就检查栈顶是否匹配匹配就弹出不匹配或栈为空直接返回false。最后栈为空才是合法串。bool isBalanced(const std::string s) { std::stackchar st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else { if (st.empty()) return false; char top st.top(); if ((ch ) top ! () || (ch ] top ! [) || (ch } top ! {)) { return false; } st.pop(); } } return st.empty(); }这个解法本身不难但有个细节想提醒不开匹配函数直接用if判断配对关系代码能短很多但要非常小心三个右括号分支的排他性写错一个等于把问题放跑。我用top ! (这种“不匹配就失败”的写法好处是逻辑对称面试时不容易被绕进去。4.2 表达式求值中缀转后缀其实是个栈的过程写计算器是另一个高频考察点。中缀表达式1 2 * 3人一眼看懂但程序更好处理的是后缀表达式1 2 3 * 。中缀转后缀的过程就用栈保存运算符数字直接输出遇到运算符则把栈中优先级不低于当前运算符的都弹出再压入当前运算符左括号直接进栈右括号则弹到左括号为止。后缀表达式求值再用一个数字栈遇到数字压栈遇到运算符弹出两个数字计算结果压回栈。整个过程两个阶段两个栈逻辑连贯。强烈建议自己手写一遍这是理解栈“嵌套优先级”双重能力的好题目。我面试时被问过“为什么不能用普通队列做中缀转后缀”当时第一反应没答全后来想明白了队列无法回退处理之前压入的运算符而栈天然支持“先压入的后处理”这个“回退能力”正是栈的不可替代性。4.3 单调栈一道题吃透“下一个更大元素”单调栈是一种优化套路本质是“让栈内元素保持单调递增或单调递减”。最经典的题目是“下一个更大元素”给定数组对每个元素求右边第一个比它大的数。暴力解法是两层循环O(n²)单调栈可以做到O(n)。std::vectorint nextGreaterElement(const std::vectorint nums) { int n nums.size(); std::vectorint res(n, -1); std::stackint st; for (int i n - 1; i 0; --i) { while (!st.empty() nums[st.top()] nums[i]) { st.pop(); // 所有比当前元素小的都不可能成为“下一个更大” } res[i] st.empty() ? -1 : nums[st.top()]; st.push(i); } return res; }理解单调栈的关键是回答“为什么栈里的元素可以扔掉”。从右往左遍历时栈里保存的是当前位置右侧的元素如果栈顶元素比当前元素小那么对当前位置更靠左的元素来说这个栈顶元素既不够大又夹在中间永远不可能成为答案留着纯属浪费。每次把这种“没希望”的元素弹出栈内剩下的是一个从栈底到栈顶严格递增的序列栈顶就是当前能看到的、离得最近的更大元素。这个“过期淘汰”的思路和滑动窗口里的双端队列很像掌握一个另一类题也顺手了。4.4 函数栈帧与递归深度栈溢出是怎么发生的除了数据结构考试里的栈C程序运行时还有一套系统栈。每次调用函数都会在调用栈上压入一个“栈帧”里面存返回地址、参数、局部变量。递归函数没写终止条件时栈帧一层层压下去最终把操作系统分配给线程的栈空间耗尽程序抛stack overflow。这不是数组栈那种“装满就返回false”的温和错误而是直接崩溃。排查递归栈溢出时我一般先看递归深度是否有明确上界——比如递归树深度等于数组长度十万元素压十万层栈帧几乎必爆再看有没有该写成循环却写成递归的地方。C里方案也很多改成显式栈模拟、尾递归优化、或者把递归函数改写成循环。理解栈帧之后看崩溃日志里那一长串调用链条目就知道那是系统帮我们把整个“栈的轨迹”打印了出来这也解释了为什么第1章说栈和“回溯”深度绑定。5. 队列的工程价值从消息队列到线程池5.1 消息队列为什么叫“队列”解耦、削峰、顺序聊到消息队列很多初学者会想RabbitMQ、Kafka这些中间件跟数据结构的队列有什么关系关系非常大。消息队列本质上是一个分布式的FIFO容器生产者发消息进队列消费者从队列取消息消息的消费顺序大体遵循到达顺序。它的三个核心价值——解耦、削峰、异步——全都建立在“排队”这个语义上。解耦是生产者和消费者互不感知生产者只往队列里放不关心谁消费削峰是当流量瞬间暴涨时队列充当缓冲区消费者按自己的速率慢慢处理不至于把下游压垮顺序则是队列天然保持消息先后关系消费者按序拉取保证同一业务的消息处理顺序不颠倒。热搜词里提到的“消息队列重复消费问题”本质是分布式环境下消费端宕机后重新拉取消息可能出现同一条消息被处理多次这跟队列数据结构本身无关而是消费确认机制的问题。但理解了“FIFO缓冲区”这个底层模型再去理解这些分布式问题会容易很多。5.2 生产者消费者模型和阻塞队列阻塞队列是工程中用得最多的队列变体。它的核心能力是队列满时生产者被阻塞住等待空间队列空时消费者被阻塞住等待数据。这种“等待”不是自旋空转而是通过条件变量让出CPU效率高得多。下面是我实际项目里经常用的简易版本用mutex condition_variable实现#include queue #include mutex #include condition_variable template typename T class BlockingQueue { private: std::queueT q_; std::mutex mtx_; std::condition_variable not_empty_; std::condition_variable not_full_; size_t cap_; public: explicit BlockingQueue(size_t cap) : cap_(cap) {} void push(T val) { std::unique_lockstd::mutex lock(mtx_); not_full_.wait(lock, [] { return q_.size() cap_; }); q_.push(std::move(val)); not_empty_.notify_one(); } T pop() { std::unique_lockstd::mutex lock(mtx_); not_empty_.wait(lock, [] { return !q_.empty(); }); T val std::move(q_.front()); q_.pop(); not_full_.notify_one(); return val; } };写这段代码有个很容易忽略的细节wait()的第二个参数是谓词不能省。如果只用wait(lock)可能会被意外唤醒spurious wakeup导致在条件不满足时继续执行引发空队列pop或满队列push。加上谓词后每次唤醒都会重新检查条件不满足就继续睡代码才真正可靠。这也是为什么很多线程池的底层“任务队列”本质上就是一个阻塞队列——线程池里空闲的worker线程阻塞在pop()上有任务来了被唤醒取一个任务执行做完继续阻塞等待。热搜词里的“线程池的阻塞队列选择”讨论的就是该用std::queue配合条件变量还是用无锁队列核心都在“阻塞”两个字上。5.3 循环队列在底层系统里叫“环形缓冲区”循环队列在操作系统、嵌入式系统里有个更常见的名字——环形缓冲区。日志库要连续写入大量日志网络库要暂存收发的数据包音频设备要缓冲采样数据这些场景都用环形缓冲区。为什么底层偏爱环形缓冲区而不是链表队列因为底层的核心诉求是“不动态分配内存”。操作系统内核在很多路径上不允许执行new/malloc一旦内存分配触发缺页中断整个系统的实时性就崩了。环形缓冲区用预分配的一块连续内存通过读写下标循环复用完全规避了动态内存分配。理解了这一点再回头看第3章循环队列那几十行代码它的价值就不是一个练习题而是一种真实系统里每天运行的工程机制。5.4 C工程里的实践建议优先复用标准库在C工程里自己实现队列的情况其实很少。生产代码我基本直接用std::queue底层默认是std::deque性能足够语义清晰需要阻塞语义时用上面的BlockingQueue封装需要按优先级处理时用std::priority_queue需要双端操作时用std::deque。自己从零写循环队列更多出现在实验报告、刷题、面试手写和底层嵌入式中。不过我还是建议每个人都亲手写一遍循环队列和阻塞队列。原因很简单面试考的是你是否理解“队列”这个抽象在硬件和系统层面是如何落地的手写一遍能让你真正理解为什么判空是front rear、为什么判满要留一个空位、为什么condition_variable要配谓词。这些理解靠背八股是得不到的。实测下来能流畅手写阻塞队列的候选人对C并发模型的理解通常明显高一个档次。6. 常见错误与排查这些坑我替你踩过了6.1 忘判空直接访问top、front、rear这是栈和队列入门阶段最高频的崩溃原因。对空栈调用pop()或top()对空队列调用dequeue()在黑盒测试里可能恰好不崩但一旦数组越界读出来的就是脏数据程序行为随机漂移排查起来非常痛苦。我的习惯是封装成一个内部方法比如assertNotEmpty()在pop和top的第一行调用生产代码则抛std::runtime_error或返回std::optional明确把“空操作失败”暴露给调用方。刷题时顺手加上判空分支面试官对这个细节往往很敏感。6.2 顺序队列出队后面临假溢出前面提到的假溢出问题我当年写课程设计时踩得结结实实。用数组front/rear下标实现了一个普通队列跑了半天突然发现队列容量越来越小死活入不了队。排查时先怀疑内存泄漏后怀疑指针迁移错误最后把front和rear的下标打印出来才明白是假溢出。从那以后我写顺序队列只用循环队列或者干脆用std::queue。查这类问题最快的方法就是打印front和rear的当前值再打印每次入队、出队后这两个值的移动轨迹当场就能定位。6.3 递归太多导致系统栈溢出不是数组栈的锅很多同学在递归深度较大的DFS题目里遇到stack overflow第一反应是“我数组栈不够大吗”其实这里爆的是系统调用栈和数据结构实验里手写的数组栈没有关系。Windows系统默认栈大小在1MB到8MB之间取决于编译器设置Linux默认8MB。你可以用ulimit -s查看修改也可以用#pragma comment(linker, /STACK:...)在Windows下调整。但更务实的做法是减少递归深度或把DFS改成显式栈迭代。C不像Java那样限制线程栈小到容易触发但深度几十万的递归在C里照样会爆这点要心里有数。6.4 调试栈和队列的小技巧打印下标比盯代码有效我自己调试数据结构代码最有效的一招是“可视化状态打印”。栈的话把top下标、栈内元素逐个打印出来队列的话把front、rear下标和数组里从front到rear之间的所有元素打印出来。很多人调试时喜欢在脑子里模拟指针移动但人的大脑在几层循环、多次出入队后就不可靠了机器打印的原始数据最真实。配合一小段断言比如出队后检查size是否符合预期绝大多数边界bug在几分钟内就能定位。这个习惯我一直保留到现在写复杂算法题时也经常临时加打印做完再删。7. 面试、竞赛和期末考试怎么复习7.1 考点清单速查表我根据自己参加校招面试和辅导他人的经验整理了一张栈和队列的核心考点表按出现频率排了优先级考点数据结构核心思路优先级用两个栈实现队列栈一个负责入一个负责出出栈为空才搬运必考用两个队列实现栈队列入栈时把元素放入非空队列出栈时把前n-1个移到另一个队列高频最小栈栈辅助栈同步保存当前最小值O(1)取min高频括号匹配栈左括号入栈右括号匹配弹栈必考中缀转后缀栈运算符优先级栈暂存高频单调栈-下一个更大元素栈单调递增栈过期元素出栈高频循环队列队列取模预留空位判满必考滑动窗口最大值双端队列单调双端队列头部过期即出高频层序遍历二叉树队列BFS按层迭代必考阻塞队列/生产者消费者队列条件变量互斥量高频7.2 复习节奏和实战建议准备时间紧张的话我建议按“基础实现→经典题→进阶套路”三步走。第一步亲手写一遍数组栈、链表栈、循环队列、链队列不需要追求一次对重点是跑通第二步刷上面表格里的经典十题每一道都要求自己20分钟内写出来第三步再集中练单调栈、双端队列这类进阶题目标是理解套路本身而不只是背代码。数据结构期末复习和实验报告其实最重要的是把“每个操作的时间复杂度”和“判空判满条件”写清楚老师打分主要看这两块。竞赛层面C里std::stack和std::queue可以直接用但明白底层原理能帮你更稳地用对emplace、move等C新特性。最后想提醒一句栈和队列的题看着简单实际手写时边界条件最容易翻车练习时务必把“空”、“满”、“只有一个元素”这三个边界场景都亲手跑一遍。我个人在实际操作中最大的体会是栈和队列作为数据结构里最基础的两个结构恰恰是最能拉开代码功底差距的地方。背下定义的人只能写出能跑的demo真正理解“回溯”和“按序排队”这两个抽象的人才能轻松驾驭递归栈、单调栈、消息队列、线程池任务队列这些工程概念。最后再分享一个小技巧调试循环队列时不要用眼睛扫代码一定要把front和rear的实时值打出来我因为这一个小习惯少走了很多排查冤枉路的弯路。