只要开始认真学C栈和队列这两个名字很快就会出现在视野里。我在初学的时候其实很不理解数组和链表明明已经能存数据了为什么还要专门抽象出这两个容器后来学到递归、表达式求值、二叉树遍历才发现栈和队列最值钱的不是“能存什么”而是那套“限制访问顺序”的规则——数据怎么进去、怎么出来直接决定了算法能不能跑得优雅。这篇文章我就把栈和队列的原理一层层剥开用纯C分别手写数组版和链表版再带着你和标准库作对比顺便把循环队列、迭代器失效这类经典坑都踩一遍。适合刚学完C基础语法准备进阶数据结构的同学也适合面试前临时抱佛脚手撕代码的朋友。1. 先搞清楚栈和队列的底层逻辑1.1 栈后进先出的“叠盘子”模型栈的核心规则就是一句话后进先出英文缩写LIFOLast In First Out。你可以想象食堂里那一摞不锈钢餐盘新洗好的盘子总是放在最上面取的时候也一定先取最上面的那个。如果柜子底部放着最早洗的盘子你不把所有上面的盘子搬走是碰不到它的。对应到C的容器操作上就是入栈往栈顶添加一个元素通常叫push。出栈把栈顶的那个元素拿走让下面的元素露出来通常叫pop。访问栈顶只看栈顶元素但不移除通常叫top或peek。判空检查栈里还有没有元素通常叫empty。这个模型在计算机世界里的投影几乎无处不在。函数调用就是最典型的栈结构你调用了一个函数AA里面又调用了BB里面再调用了C那执行完C之后一定是回到B再回到A最后回到调用点。这正好是后进先出的顺序。程序运行时每个线程都有自己的调用栈局部变量、返回地址全压在上面一旦递归太深把栈空间撑爆了就是大家都听过的“栈溢出”Stack Overflow。栈在表达式求值里也扮演着关键角色。中缀表达式转后缀表达式、计算后缀表达式、括号匹配检测这些统统靠栈来维护“等待中的运算符”和“未闭合的括号”。还包括编辑器的撤销操作你每一步操作压入栈按一次撤销就从栈顶弹出一个历史记录这个交互逻辑跟栈天然契合。1.2 队列先进先出的“排队”模型队列的规则同样简单先进先出英文缩写FIFOFirst In First Out。就是食堂打饭排队的样子先到的人先打到饭后来的人排在队伍末尾。如果一个人插队那这个数据结构就退化了所以正常实现里入队永远从队尾出队永远从队头。对应到C操作上是入队在队尾追加一个元素通常叫push或enqueue。出队把队头元素移除通常叫pop或dequeue。访问队头只看队头元素不移除通常叫front。判空检查队列里有没有元素。至少我在真实开发里最先接触队列的地方就是操作系统的任务调度。多个进程/线程排队等待CPU每个任务分到一个时间片循环完一轮再回到队尾这就是最朴素的轮转调度底层模型就是队列。网络请求的异步任务队列、消息中间件里的消费队列、BFS广度优先搜索里的节点待访问集合本质上全都是队列。BFS是个特别容易理解队列价值的例子。你从起点出发先把同一层的邻居全部加入队列然后一层一层往外扩散保证先搜到的节点离起点最近。这个“一层一层扩散”的语义用栈来实现是完全做不到的只有队列的FIFO顺序才匹配。1.3 为什么这两个结构能占领半个数据结构课很多人觉得栈和队列太简单不就是往容器上加了一层限制其实恰恰是这层限制给了它们巨大的威力。首先限制访问顺序就带来了可预测性。你用数组存一堆中间结果到底该先处理哪一个需要自己维护位置信息非常容易错。栈和队列把这些决策收编成固定的规则算法的每个状态都清晰可控代码的引擎逻辑被大大简化。其次栈和队列对应了两类最基础的问题求解范式深度优先和广度优先。递归天然就是栈驱动的DFS的显式写法就是在模拟调用栈而BFS则完全仰仗队列。掌握了这层对应关系你学树、图、动态规划时都会顺很多。再加上栈和队列在工程实践里的出场率太高。编译器、解释器、浏览器的前进后退、打印机的任务缓冲、缓存淘汰里的FIFO策略到处都有它们。所以数据结构面试题里它们出现频率一直居高不下手写实现、变种设计都是常客。2. 手写栈数组版和链表版实现对比2.1 数组栈基于vector的10分钟实现先来个最接地气的实现。利用标准库的vector做底层存储因为它自带扩容、随机访问、尾部插入删除都是摊还O(1)简直是为栈量身定做的。#include iostream #include vector #include stdexcept template typename T class SimpleStack { public: void push(const T val) { data.push_back(val); } void pop() { if (empty()) { throw std::runtime_error(pop from empty stack); } data.pop_back(); } T top() const { if (empty()) { throw std::runtime_error(top on empty stack); } return data.back(); } T top() { if (empty()) { throw std::runtime_error(top on empty stack); } return data.back(); } bool empty() const { return data.empty(); } size_t size() const { return data.size(); } private: std::vectorT data; };这里有几个值得注意的设计细节。一是top函数同时提供了const和非const两个版本。非const版本返回T允许调用方直接修改栈顶元素。比如你有一个栈存了某个状态的句柄想在不弹栈的情况下更新它这就有用了。二是pop和top之前必须判空。空栈上的操作属于未定义行为很多初学者一脸自信地写pop结果在空栈上报错。与其依赖调试器查半天不如直接在程序里抛异常让错误尽早暴露。三是为什么用value而非引用。在pop里其实不需要参数在push里才需要。我见过有人把push写成一个返回栈顶元素的函数这基本不是栈的语义别照葫芦画瓢。面试时这段代码基本够用了。不过要问一句如果vector的扩容发生在push时之前的迭代器会怎样答案是全部失效。但这个坑放到后面再说。2.2 链表栈动态内存的另类玩法数组栈实现简单但它有一个特点栈的整体容量受vector管理扩容时可能把整个数据搬到新内存。链表栈则完全不预分配连续空间每个元素按需申请用指针串联起来。#include iostream #include stdexcept template typename T class LinkedStack { private: struct Node { T value; Node* next; }; public: LinkedStack() default; // 禁止拷贝避免浅拷贝造成双删 LinkedStack(const LinkedStack) delete; LinkedStack operator(const LinkedStack) delete; ~LinkedStack() { while (head ! nullptr) { Node* tmp head; head head-next; delete tmp; } } void push(const T val) { Node* new_node new Node{val, head}; head new_node; } void pop() { if (empty()) { throw std::runtime_error(pop from empty stack); } Node* tmp head; head head-next; delete tmp; } T top() { if (empty()) { throw std::runtime_error(top on empty stack); } return head-value; } const T top() const { if (empty()) { throw std::runtime_error(top on empty stack); } return head-value; } bool empty() const { return head nullptr; } private: Node* head nullptr; };链表版的关键操作全部集中在头节点。push就是把新节点插到头部pop就是把头节点摘掉时间复杂度都是O(1)。它的好处在于不用扩容不存在元素整体搬迁的问题也不存在迭代器因realloc而全部失效的情况。但你得接受它的代价每个节点都要分配额外内存存储密度比vector低。更重要的是如果栈里存的是自定义类型每次push都通过new创建节点这通常伴随一次T的构造。大量入栈出栈会带来显著的内存分配开销性能未必比得上vector的尾部push_back。链表栈里最容易翻的车是内存泄漏。Node节点都是用new创建的所以在析构函数里要逐个delete。我见过有人把析构函数写成空函数跑一次操作数据一多内存直接飙上去。还有浅拷贝问题如果这个类被默认拷贝两个对象的head指针会指向同一串链表析构时double free直接崩溃。所以要么禁用拷贝要么自己实现深拷贝先禁用是最省事的做法。2.3 两种实现的取舍讲到这里可以做个横向对比对比项数组栈vector链表栈Node入栈/出栈复杂度均摊O(1)O(1)内存连续性连续不连续扩容代价可能整体复制无内存占用预留容量可能浪费每节点有指针开销迭代器稳定性扩容后失效指针稳定不迁移缓存友好度高低实现复杂度低中等实际工程中大部分时候数组栈都是很好的默认选择。vector的缓存命中率高操作连续内存快扩容虽然偶尔有代价但均摊下来并不亏。链表栈更适合场景本身需要节点稳定、元素数量波动极大、或者不想让数据搬来搬去的情况。这里额外提一个面试加分点向量扩容的均摊分析。vector的扩容通常按2倍增长每次扩容复制当前所有元素总复制次数差不多是O(n)而插入n个元素的总成本也就是O(n)算下来每个push均摊O(1)。所以你回答“vector栈的push是均摊O(1)”时最好能把这个推导过程讲出来别只说结论。3. 手写队列绕不开的循环队列与链式队列3.1 数组队列为什么会“假溢出”队列和栈最大的不同在于出队发生在队头入队发生在队尾。如果你直接用vector实现队列最朴素的想法是std::vectorint q; q.push_back(1); // 入队 // 出队时 auto first q[0]; q.erase(q.begin()); // 删除第一个元素这个实现能跑但erase(q.begin())会把后面所有元素整体前移一位复杂度O(n)。队列的核心操作本来应该是O(1)这样一来性能直接劣化。数据量小无所谓一旦队列里塞了十万个元素每次出队都搬一座山。聪明的办法是维护一个队头下标head。出队时不让元素物理移动只把head往后挪一格。可是head越挪越靠后队尾指针tail也一路往后就会出现一个可怕的现象明明队首后面空闲空间一大把tail却已经到数组末尾再做入队就报“队列已满”。这就是所谓的假溢出。假溢出的本质是线性数组中已被出队的空间永远留在前面无法被重新利用。解决方法也不难把数组的首尾在逻辑上接成环形当tail走到数组末尾时绕回下标0继续用这就是循环队列。3.2 循环队列的完整实现循环队列的关键是取模运算。下标从末尾回到开头靠的是 (index 1) % capacity 而不是简单的 index 0。#include vector #include stdexcept template typename T class CircularQueue { public: explicit CircularQueue(size_t cap) : data(cap) {} void push(const T val) { if (size() data.size()) { throw std::runtime_error(queue is full); } data[tail] val; tail (tail 1) % data.size(); count; } void pop() { if (empty()) { throw std::runtime_error(pop from empty queue); } head (head 1) % data.size(); --count; } T front() { if (empty()) { throw std::runtime_error(front on empty queue); } return data[head]; } const T front() const { if (empty()) { throw std::runtime_error(front on empty queue); } return data[head]; } T back() { if (empty()) { throw std::runtime_error(back on empty queue); } return data[(tail data.size() - 1) % data.size()]; } bool empty() const { return count 0; } size_t size() const { return count; } private: std::vectorT data; size_t head 0; size_t tail 0; size_t count 0; };这个实现里我额外引入了一个count字段来区分“空”和“满”。为什么要它因为如果不加count循环队列空和满的状态都是head tail根本分不清。常见的替代方案是牺牲一个存储单元让“队尾指针下一个位置就是队头”时判定为满这样就不用count但队列实际能存的数据量变成capacity - 1空间利用不完整。我的习惯是保留count代码更直观也不存在浪费一个槽位的问题。判空看count判满看count是否等于容量逻辑非常直白。注意back函数取队尾元素时因为tail指向的是下一个可写入的位置真正的队尾元素在下标 (tail size - 1) % size 的位置。这个取模容易踩坑很多人直接把tail当队尾结果始终读到的是队尾后面那个“空”位置。循环队列的使用场景很典型固定大小缓冲区的生产者消费者模型比如网络包缓冲、环形日志、音频数据流。它不需要动态分配新节点也不会无限增长只要缓冲区大小不会超性能是极稳定的。3.3 链式队列实现链式队列的思路比循环队列简单一点维护头尾两个指针入队在tail节点之后追加出队从head节点摘除。#include stdexcept template typename T class LinkedQueue { private: struct Node { T value; Node* next; }; public: LinkedQueue() default; LinkedQueue(const LinkedQueue) delete; LinkedQueue operator(const LinkedQueue) delete; ~LinkedQueue() { while (head ! nullptr) { Node* tmp head; head head-next; delete tmp; } } void push(const T val) { Node* new_node new Node{val, nullptr}; if (tail ! nullptr) { tail-next new_node; } else { head new_node; } tail new_node; size_; } void pop() { if (empty()) { throw std::runtime_error(pop from empty queue); } Node* tmp head; head head-next; if (head nullptr) { tail nullptr; } delete tmp; --size_; } T front() { if (empty()) { throw std::runtime_error(front on empty queue); } return head-value; } bool empty() const { return head nullptr; } size_t size() const { return size_; } private: Node* head nullptr; Node* tail nullptr; size_t size_ 0; };写得时候要特别留意最后一个元素出队后head和tail都要置空。我见过这样一个bug删掉最后一个节点后只更新headtail还残留着那个已释放的地址下次push时tail-next会操作野指针程序直接崩。所以代码里在head变空时把tail也归零这个是保命的一步。链式队列的用法在数据流不太确定、可能长时间运行的场景里更常见。例如一个任务列表来一个加一个不确定峰值大小只要内存够就不会像数组队列那样“铁板钉钉”地写满。与此同时它要承担每节点一次new和delete的开销以及指针存储的额外空间。3.4 队列的性能要点把队列的三种实现放一起看实现方式入队出队空间特点适用场景vectoreraseO(n)O(n)简单仅教学演示循环数组O(1)O(1)固定容量有界缓冲、高频操作链式队列O(1)O(1)动态分配元素数量不可预知的场景如果实际应用中队列长度会不断增长就别用固定容量的循环队列了。一旦满了只能抛异常消费者来不及拿数据生产者就直接阻塞或者报错。这个时候要么选择链式队列要么选择基于动态扩容的heap或deque容器。STL里的std::queue默认底层是std::deque它把动态扩容和头部插入的O(1)结合到了一起。deque本身是个分段连续的数据结构头部压入元素也能均摊O(1)所以它可以同时具备数组的高效访问和动态伸缩能力。平时不想纠结手写队列的话直接用std::queue挺好。4. 标准库stack与queue工程实践的正确选择4.1 stack与queue的基础用法其实手写的最大意义是帮你理解原理真正写工程代码的时候我通常直接用标准库。它成熟、稳定、封装完整别人的代码也一眼就懂。#include stack #include queue #include iostream int main() { std::stackint stk; stk.push(10); stk.push(20); std::cout stk.top() std::endl; // 20 stk.pop(); std::cout stk.top() std::endl; // 10 std::queueint que; que.push(10); que.push(20); std::cout que.front() std::endl; // 10 std::cout que.back() std::endl; // 20 que.pop(); std::cout que.front() std::endl; // 20 return 0; }stack和queue可以理解为容器适配器它们包装了一个底层容器对外只暴露栈/队列语义。stack默认用dequequeue也默认用deque。你还可以显式指定用vector或list做底层容器只要容器满足对应操作要求即可。比如想让stack底层用链表就写std::stackint, std::list 想让queue用数组就写std::queueint, std::list 。4.2 底层容器与priority_queue这里要区分一个概念deque和queue不是一回事。deque是双端队列提供了push_front、push_back、pop_front、pop_back可以从两端进出。queue只是把deque封装成只能队尾入、队头出。标准库设计者的意图很明确你不需要在queue上调用push_back还是push_front再思考一遍直接用push/pop就好语义清晰。另外很多算法题还会用到priority_queue也就是优先队列。它默认是大顶堆每次pop取出的是队列中最大的元素而不是“最先入队的元素”。它的底层是堆结构不是线性队列。用的时候得把容器适配器的概念彻底理解清楚才不会把priority_queue当成普通的先来先服务队列。#include queue #include vector #include iostream int main() { // 大顶堆 std::priority_queueint pq; pq.push(3); pq.push(1); pq.push(4); std::cout pq.top() std::endl; // 4 // 小顶堆 std::priority_queueint, std::vectorint, std::greaterint min_pq; min_pq.push(3); min_pq.push(1); min_pq.push(4); std::cout min_pq.top() std::endl; // 1 return 0; }top的复杂度是O(1)push和pop是O(log n)和普通队列的O(1)完全不同。面试做题时一旦用priority_queue别顺手写成back()它只有top()。4.3 什么时候该手写什么时候用标准库这个问题我几乎每次带新人都要说。如果是生产环境能上标准库就上标准库。std::stack和std::queue经过了大量编译器的验证和优化线程安全方面虽然标准库本身不承诺什么但至少不会有内存管理低级错误。手写容器最大的风险在异常安全上一个析构函数忘了delete或者一个拷贝构造函数没处理深拷贝线上环境就可能变成内存泄漏甚至崩溃。如果是学习阶段或者面试环节我强烈建议你亲手写一遍。面试官考察的重点往往不是你会不会调用std::stack::push而是你能不能理解栈的边界条件能不能处理队列的假溢出能不能用链表实现并保证析构干净。这时候手写就是最好的训练。还有一类情况需要自己动手你想让容器支持某种定制化行为。比如你需要在栈pop时自动记录日志需要在队列满时执行某种背压策略需要栈中元素的迭代顺序可自定义。标准库的适配器封得比较死想插入自定义逻辑很别扭这时候自己封装一层甚至手写底层都是合理的。5. 实战用栈和队列解决两个最常见的算法题5.1 括号匹配栈的经典应用括号匹配几乎是栈的“入门必修题”。给你一个只包含( ) [ ] { }的字符串判断括号是否合法闭合。思路很简单遇到左括号就压栈遇到右括号就弹出栈顶检查是否匹配。如果遍历结束后栈为空则说明所有括号都闭合了。#include stack #include string bool isValid(const std::string s) { std::stackchar stk; for (char c : s) { if (c ( || c [ || c {) { stk.push(c); } else { if (stk.empty()) { return false; } char top stk.top(); if ((c ) top () || (c ] top [) || (c } top {)) { stk.pop(); } else { return false; } } } return stk.empty(); }这些边界条件一定要考虑到位。如果字符串是“)(”第一个右括号拿来对比时栈是空的直接返回false不能等到最后才判定。如果字符串是“(]”栈顶是(但遇到的是]匹配不上也直接返回false。直到循环结束后如果栈里还有左括号比如“( ( )”说明有多余未闭合的符号同理返回false。这个题看着简单但它的变种非常多。比如括号里面可以混入普通字符要求忽略掉普通字符只判断括号是否合法比如要求输出最长的合法括号子串长度比如要求检测括号嵌套深度。这些都可以在栈框架上改改逻辑。把基础版本想透了后面变种都是举一反三的事。5.2 二叉树的层序遍历队列的经典应用层序遍历就是BFS在二叉树上的落地实现。核心思想是从根节点开始把每一层的节点依次入队出队一个节点时把它的左右子节点入队。因为队列是先进先出所以同一层的节点会按照从左到右的顺序被消费。#include queue #include vector struct TreeNode { int val; TreeNode* left; TreeNode* right; }; std::vectorstd::vectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint result; if (root nullptr) { return result; } std::queueTreeNode* que; que.push(root); while (!que.empty()) { int level_size que.size(); std::vectorint level; for (int i 0; i level_size; i) { TreeNode* node que.front(); que.pop(); level.push_back(node-val); if (node-left ! nullptr) { que.push(node-left); } if (node-right ! nullptr) { que.push(node-right); } } result.push_back(level); } return result; }注意那个int level_size que.size()的写法。这里必须在入队子节点之前先把当前层的节点数量记录下来。如果直接在循环里用que.size()做条件那子节点入队后size会变化循环次数和层边界就全乱了。这种“层边界固定”的小技巧是层序遍历的常见坑也是面试官最喜欢问的细节。另外这题的变种包括之字形遍历、每层最大值、每层平均值基本思路都是一样的只是对每一层的结果处理不同。想通一层层的边界如何切分BFS就算吃透了。6. 常见问题与排查技巧实录6.1 栈溢出与下溢的边界条件手写栈时最容易出的问题就是在空栈上执行top或pop。前面我在实现里都抛了异常但很多面试代码为了简洁会省略判空。一旦输入用例有边界情况比如空字符串、只有一个元素、全是右括号代码就会在运行时直接崩溃。调试时看到的报错往往是Segmentation fault或std::bad_alloc但其实根因就是越界访问。我建议无论多简单的代码操作前都保留判空逻辑。在工作环境里抛runtime_error是合理做法。在面试环境里如果嫌estrexception麻烦至少写个if (empty) return or assert表明你考虑到了边界。控制递归深度也是一个常见话题。C的函数调用栈默认约8MB左右具体看平台。每层递归都会消耗栈空间如果队列或树的深度过大递归写法很容易撑爆栈空间。这时把显式的std::stack换掉冗长的编译器递归调用是更稳健的方案。6.2 循环队列的取模陷阱循环队列的取模看起来是加减法的小事实际很容易出错。比如下标回绕时应该用 (tail 1) % capacity。有一些初学者写成 tail 1然后加个if (tail capacity) tail 0这个写法也等价但分支判断属于多余操作。取模写法更统一。另一个经典坑是back函数。我再次强调队尾元素下标是 (tail capacity - 1) % capacity不是 tail。如果tail恰好是0那么真正的队尾元素在下标capacity - 1处不能直接访问data[tail]。还有一个隐蔽的风险如果capacity本身是0那 (head 1) % data.size() 就是除零错误。构造函数里最好检查cap或者至少保证cap不为0。6.3 迭代器失效与内存泄漏用vector实现栈时每次push_back如果触发扩容原来获得的迭代器、指针、引用全部失效。这是vector的固有行为不是bug但你要有这个意识。用链表实现时不存在这个问题节点地址是稳定的。可链表栈/队列的坑集中在内存管理上。析构函数必须逐个delete节点拷贝构造函数和赋值操作符要么自己写深拷贝要么delete掉。不要觉得自己“反正不会拷贝”很多时候你会不经意地按值传栈或队列默认拷贝会直接导致同一块内存被析构两次。如何排查内存泄漏我在开发和课程辅导中常用的手段是写压力测试反复push/pop上万次观察内存是否持续稳定。如果内存随时间无限上涨优先看析构函数和拷贝逻辑。这一步不需要什么工具靠肉眼监控进程内存就行。更复杂的场景再上Valgrind或ASan。6.4 面试和调试中的建议最后一个部分聊点经验心得。面试手写栈和队列题的时候先跟面试官确认边界条件。比如“这个栈是否允许为空时pop”、“队列满了应该报错还是自动扩容”。这不是扭捏而是体现工程思维。实现时可以先用最简方式写出来再补充判空逻辑。调试小技巧给容器写一个dump函数把内部结构临时打印出来比单步断点高效得多。void dumpStack(std::stackint stk) { std::cout stack(top-bottom): ; while (!stk.empty()) { std::cout stk.top() ; stk.pop(); } std::cout std::endl; }传参时按值拷贝stack这样打印完不会破坏原有栈的数据。这个技巧在排查复杂算法时很好用输出一眼就能看出状态是否正常。根据我带过一批又一批初学者踩坑的实际体会栈和队列的理解障碍往往不在API背没背熟而在边界条件和容器适配器底层结构这两块。只要把空栈/满队列这些状况梳理清楚把“容器适配器只是封装了底层容器”这个概念想明白后续学树、图、BFS/DFS都会顺畅得多。希望这篇文章能帮你把基础夯牢下次再遇到手写栈和队列的面试题心里能有底。