队列和栈这两个东西几乎是每个写代码的人都绕不过去的基础结构。但说句实话很多时候我们只是拿来就用——queue、stack、deque这些容器一调完事。真正让我觉得我好像没完全懂的是某次面试被问到让你自己实现一个队列你打算怎么设计我脑子里只有std::queue的底层封装张口就开始背API。那之后我花了些时间把这两种结构的模拟实现从数组到链表、从单端到循环全手写了一遍。这篇文章就是那段时间的沉淀适合刚学完数据结构想动手验证的同学也适合面试前来临阵磨枪的兄弟。1. 为什么需要模拟实现而不直接用现成的1.1 现成容器和模拟实现之间的落差很多人觉得奇怪Python有collections.dequeC有std::queueJava有ArrayDeque明明直接调用就行为什么还要自己写一遍我的理解是这样的你调API的时候看到的是接口看不到的是行为。比如队列的先进先出你只知道push进去的东西pop出来顺序不变但底层是数组还是链表满的时候怎么办空的时候front()返回什么这些问题只有亲手模拟过一遍才能说出个所以然。更重要的是很多面试题不会直接问你队列是什么而是给你一个场景比如设计一个支持获取最大值的队列、用两个栈实现队列这些都需要你对底层实现有真正的掌控力而不是只会调包。1.2 模拟实现的三种层次我给自己定了一个递进目标也推荐你按这个顺序来第一层数组实现静态队列和栈。用固定大小的数组用下标模拟顶指针和队首队尾。这个层次解决结构怎么组织的问题。第二层链表实现动态队列和栈。不限定容量需要多少就new多少体会指针操作和内存管理的细节。第三层循环队列与特殊变体。用数组模拟环形缓冲解决假溢出问题。这一层直接对应实际生产环境中的环形缓冲区、消息队列的内部实现。每一层都有不同的坑。数组版容易越界链表版容易丢指针循环队列的判空判满条件一不小心就写反。这篇文章会把三层都过一遍每个细节都标注清楚我踩过的坑。2. 栈的模拟实现从数组版到链表版2.1 栈的核心不变量在动手写代码之前必须把栈的行为约束用一句话锁死所有插入和删除操作都发生在栈顶。这句话就是栈的全部。所以我不管用什么底层结构只需要维护一个顶的位置。数组版里它是一个整数下标链表版里它是一个指向链表头部的指针。只要保证每次插入删除都动这个位置其他元素原地不动栈的特性就自然成立。注意栈的模拟实现有一个容易被忽略的细节pop操作到底要不要销毁元素。用数组模拟时pop只需要把top减一原来位置上的数据还残留在数组里下次push会覆盖它。很多教材为了简洁直接忽略这一点但面试官喜欢问你如何保证pop之后旧数据不能再被访问这时候你要能答出来因为top是唯一合法的访问边界下标小于top才是有效数据top以上的内容属于已过期区域。2.2 数组版静态栈直接上代码我用C写但你完全可以用任何语言翻译核心逻辑是一样的template typename T class ArrayStack { private: T* data; int capacity; int top; // 栈顶索引指向下一个可写入位置 public: ArrayStack(int cap) : capacity(cap), top(0) { data new T[capacity]; } ~ArrayStack() { delete[] data; } bool push(const T val) { if (top capacity) return false; // 栈满 data[top] val; return true; } bool pop(T out) { if (top 0) return false; // 栈空 out data[--top]; return true; } bool peek(T out) const { if (top 0) return false; out data[top - 1]; return true; } bool empty() const { return top 0; } };这段代码里最关键的设计决策是top指向下一个空位而不是当前栈顶。我写第一版的时候用的是top指向当前栈顶元素结果初始化时要设成-1push时要先top再赋值pop时要先取值再--top代码变得异常容易出错。后来统一成top指向下一个空位的写法初始化为0每次push在data[top]处赋值再每次pop先--再取data[top]所有操作都变成了前后一致的模式。这种小细节说穿了不值钱但不知道的时候真的会卡很久。2.3 链表版动态栈数组版的问题显而易见容量固定满了就只能返回false。要想做到无限扩容实际受内存限制就得用链表。链表栈更简单因为栈顶天然就是链表的头部。每次push就相当于在链表头插入一个节点每次pop就相当于删除头节点template typename T class LinkedStack { private: struct Node { T data; Node* next; Node(const T val, Node* nxt nullptr) : data(val), next(nxt) {} }; Node* head; // 栈顶 public: LinkedStack() : head(nullptr) {} ~LinkedStack() { while (head) { Node* tmp head; head head-next; delete tmp; } } void push(const T val) { head new Node(val, head); } bool pop(T out) { if (!head) return false; out head-data; Node* tmp head; head head-next; delete tmp; return true; } };链表栈的核心优势在于没有容量上限代价是每个节点有额外的指针开销。我实际测试过同样存100万个整数数组栈大概用4MB10^6 * 4字节链表栈每个节点除了数据还要8字节的指针再加上内存分配器的对齐开销总共要20MB以上。所以生产环境里如果你能预估最大容量数组优先无法预估且内存足够再上链表。2.4 栈模拟实现的常见边界条件写栈最容易翻车的永远是那两件事满栈继续push和空栈继续pop。我见过太多人写代码时默认输入是合法的结果线上数据稍一异常就崩。我的习惯是无论内部逻辑多清楚对外接口必须判断空和满并返回明确的状态码。上面的代码里我用了bool返回值比写一个void pop()然后空栈时抛异常或者干脆静默失败要稳得多。3. 队列的模拟实现数组版的致命缺陷3.1 为什么队列比栈难实现栈只有一头在动队列却有两头队尾负责入队队首负责出队。这看起来只是多了一个指针的事但实际写起来问题一大堆。先用最直觉的方式——数组两个下标——来实现。rear表示下一个入队位置front表示当前队首元素下标template typename T class BadQueue { private: T* data; int capacity; int front_idx; int rear_idx; public: BadQueue(int cap) : capacity(cap), front_idx(0), rear_idx(0) { data new T[capacity]; } bool enqueue(const T val) { if (rear_idx capacity) return false; data[rear_idx] val; return true; } bool dequeue(T out) { if (front_idx rear_idx) return false; out data[front_idx]; return true; } };这个版本有一个非常隐蔽的bugdequeue并不会真正释放数组前部的空间。假设容量是100你进来10个元素再出队10个此时front_idx变成了10rear_idx也是10队列看起来是空的但数组的前10个位置永远空着后面再也进不来了。继续操作下去rear_idx迟早撞到capacity但前面明明有一大片空位。这就是所谓的假溢出。3.2 解决假溢出的方案对比面对假溢出教材上给了两个方向一是数据搬移二是循环队列。数据搬移的思路是当rear_idx到顶但front_idx不为0时把[front_idx, rear_idx)区间的数据整体搬到数组头部然后更新下标。这个方案简单直观但每次搬移的时间复杂度是O(n)如果队列频繁出入队这个开销会被放大到不可接受。循环队列的思路更优雅把数组看成一个环形结构下标到达capacity - 1后再加一就回到0。这样只要整个数组还有空位不管空位在哪个位置队列都能继续工作。所有操作的时间复杂度都是O(1)没有搬移开销。代价是判空判满的条件变复杂了这也是很多人实现循环队列时出错的地方。如果你实际去查知名消息中间件的源码你会发现几乎所有的有界阻塞队列底层都用了循环数组或类似的环形缓冲结构。Kafka、RocketMQ的存储层大量使用了这种设计不是因为他们喜欢绕弯子而是因为这种结构在性能上确实无可替代。3.3 循环队列的正确实现循环队列的核心是下标取模运算。rear (rear 1) % capacityfront (front 1) % capacity。但判空判满有个经典陷阱如果你让front rear表示空那么满的时候rear绕一圈追上front同样满足front rear就会和空冲突。解决冲突有三种常规思路牺牲一个存储单元。数组大小为capacity但最多只存capacity - 1个元素。当(rear 1) % capacity front时判定为满。空的条件仍然是front rear。增加一个count计数器。每次入队count出队count--count 0为空count capacity为满。不浪费空间但需要额外维护一个变量。增加一个flag标记。每次出队置flag false入队置flag true配合front rear判断。实现稍绕用的少。我推荐第一种方案因为它在不引入额外变量的情况下保持了逻辑最简。下面是我实际用过的实现template typename T class CircularQueue { private: T* data; int capacity; int front; // 队首元素下标 int rear; // 下一个可用位置下标 public: CircularQueue(int cap) : capacity(cap), front(0), rear(0) { 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; } int size() const { return (rear - front capacity) % capacity; } };注意size()的计算方式(rear - front capacity) % capacity。因为取模运算中rear - front可能是负数所以要加上capacity对齐。这个公式我建议你直接背下来每次现推太浪费时间。用牺牲一个单元的思路时真正的可用容量是capacity - 1。比如你new T[100]最多只能存99个元素。这一点在上层调用时很容易漏我的做法是在构造函数里校验capacity 2避免出现容量为1的极端情况导致full()逻辑永远成立。3.4 链表版队列真正的无界方案如果你需要无界队列链表是更自然的选择。链表队列需要维护两个指针——head指向队首出队端tail指向队尾入队端。这里有个特别容易犯的错入队时忘了处理空队列的情况。当队列为空时head和tail都是nullptr此时新节点既是头也是尾所以必须同时更新两个指针template typename T class LinkedQueue { private: struct Node { T data; Node* next; Node(const T val) : data(val), next(nullptr) {} }; Node* head; Node* tail; public: LinkedQueue() : head(nullptr), tail(nullptr) {} ~LinkedQueue() { while (head) { Node* tmp head; head head-next; delete tmp; } } void enqueue(const T val) { Node* newNode new Node(val); if (tail) { tail-next newNode; } else { head newNode; } tail newNode; } bool dequeue(T out) { if (!head) return false; out head-data; Node* tmp head; head head-next; if (!head) tail nullptr; // 队列变空tail同步置空 delete tmp; return true; } };这段代码里有两个细节我必须强调。第一个是enqueue时如果tail为空说明队列本来就是空的新节点同时是头和尾第二个是dequeue删掉最后一个节点后tail还指着那个被删的节点这是一个典型的悬垂指针所以必须把tail也置为nullptr。这两个坑我都掉过尤其是第二个用调试器看半天才发现tail指向了已释放的内存。4. 队列的进阶模拟阻塞队列与环形缓冲区4.1 从基础队列到阻塞队列数据库的连接池、线程池的任务队列、消息队列的生产消费者模型底层都用到了队列。但生产环境里的队列和教科书队列有一个显著区别当队列为空时消费者不能一直轮询空转否则CPU白白烧掉当队列满时生产者也不能直接丢弃数据。阻塞队列就是为解决这两件事而生的。阻塞队列可以理解为队列 线程等待/唤醒机制。Java的ArrayBlockingQueue、LinkedBlockingQueue是典型实现如果是C通常用std::mutex配合std::condition_variable来实现。我用C写了一个最简版本帮你把阻塞逻辑拆开看template typename T class BlockingQueue { private: std::mutex mtx; std::condition_variable cv_not_empty; std::condition_variable cv_not_full; const int capacity; std::queueT inner; public: BlockingQueue(int cap) : capacity(cap) {} void push(const T val) { std::unique_lockstd::mutex lock(mtx); cv_not_full.wait(lock, [this] { return inner.size() capacity; }); inner.push(val); cv_not_empty.notify_one(); } T pop() { std::unique_lockstd::mutex lock(mtx); cv_not_empty.wait(lock, [this] { return !inner.empty(); }); T val inner.front(); inner.pop(); cv_not_full.notify_one(); return val; } };这里最有价值的设计模式是条件变量必须配谓词判断。直接cv.wait(lock)是反模式因为会发生虚假唤醒——线程被唤醒时条件可能并不成立。只有wait(lock, predicate)这种带判断条件的写法才能保证唤醒后重新检查状态不满足就继续睡。4.2 环形缓冲区在消息队列中的应用你在看Kafka、RocketMQ的存储设计时会发现高频使用了一个叫环形缓冲区的结构也就是我们前面实现的循环队列在生产环境中的正式形态。消息中间件里生产者把消息字节流不断写入缓冲区消费者从另一端按序读取当缓冲区写满生产者要么等待、要么触发刷盘腾出空间。这就是循环队列的核心价值没有数据搬移的成本固定内存就能持续运转。实现环形缓冲区时还有一个很少被提及的细节正确用volatile或内存屏障保证多线程可见性。如果是单线程使用直接读写下标没有任何问题一旦涉及多线程只靠一个循环队列结构是不够的必须配合互斥锁或原子变量。我自己在写一个安卓网络请求队列时为了减少锁竞争用了无锁环形队列 原子下标的方案性能确实比加锁高但调ABA问题调到头秃。新手阶段老老实实加锁先把逻辑跑对。4.3 用两个栈模拟队列面试高频题用两个栈实现队列本质上考察的是你能否利用栈的后进先出特性构造出先进先出的效果。思路核心是一个栈inStack专门处理入队另一个栈outStack专门处理出队出队时如果outStack为空一次性把inStack所有元素弹入outStack这样元素顺序就翻转了两次入栈两次出栈两次最终保持先进先出。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): self._transfer() return self.out_stack.pop() def peek(self): self._transfer() return self.out_stack[-1] def empty(self): return not self.in_stack and not self.out_stack def _transfer(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())这个实现有一个性能特征值得划重点均摊时间复杂度是O(1)。虽然每次pop可能需要搬移一堆元素但每个元素最多进一次in_stack、出一次in_stack、进一次out_stack、出一次out_stack总共4次操作洗牌均摊下来就是常数时间。这个分析方法面试时非常加分因为面试官真正想看的不是你会不会背答案而是你有没有思考复杂度摊还的能力。反过来用两个队列实现栈思路就变成入栈时直接入主队列出栈时把主队列除最后一个元素外的所有元素移到辅助队列然后弹出最后一个再把辅助队列和主队列互换角色。这个操作每次出栈是O(n)因为每出一次栈都要把整队扫一遍。5. 队列和栈的实现选型与性能实测5.1 数组 vs 链表不只是内存布局的区别很多初学者觉得数组和链表就是内存连续和非连续的区别这种理解太浅了。真正的性能差异来自缓存命中率。数组是连续内存遍历时CPU缓存能一次把一大块数据预加载到L1/L2缓存后续访问全部命中链表节点是分散的每访问一个节点都可能发生缓存未命中要重新到内存去取数据。我实测过用数组实现和链表实现各入队出队100万次数组版耗时大约是链表版的五分之一。这个差距在百万级数据量下就已经非常明显到千万级更是指数级拉大。所以我的选型建议很简单能预估容量上限的选循环数组队列。无法预估容量上限且数据量很小选链表队列省心。需要频繁在中间插入删除选链表但队列栈根本不涉及中间操作所以这条不适用。数据量极大且对延迟敏感除了数组之外还要考虑内存池避免频繁new/delete带来的分配器开销。5.2 内存管理的坑用链表实现队列栈最让人头疼的是内存泄漏和悬垂指针。下面这段代码就是我之前犯过的错你可能一眼就能看出问题void pop() { Node* toDelete head; head head-next; // 忘了 delete toDelete; }这个看起来无害实际每次出队都泄漏一个节点。跑久了内存占用只增不减线上服务迟早OOM。我现在的习惯是写完任何链表操作立刻用valgrind或AddressSanitizer跑一遍内存检测成了肌肉记忆。Visual Studio的调试堆、Linux的valgrind --leak-checkfull、Clang的-fsanitizeaddress随便选一个都行关键是要在开发期就做别等上线了再被运维抓。5.3 可视化验证与调试技巧队列和栈的实现逻辑看得见摸不着最容易出错的恰恰是边界条件。我用过一个很土但很有效的调试办法写一个dump函数把当前状态完整打印出来。数组循环队列的dump可以这样写void dump() { std::cout front front , rear rear , size size() : ; for (int i 0; i size(); i) { int idx (front i) % capacity; std::cout data[idx] ; } std::cout std::endl; }每次入队出队后调一次dump眼睛看到的东西立刻和封面逻辑对上了。尤其是循环队列下标绕回0的那一下如果不打出来光靠脑补非常容易漏掉边界。调试链表队列时我还会打印每个节点的地址。比如for (Node* p head; p; p p-next) { std::cout p - p-data ; }这样一旦出现指向已释放内存的悬垂指针地址信息能很快帮你定位问题出在哪个环节。6. 常见问题与排查技巧实录6.1 队列和栈实现的高频报错速查表症状可能原因排查思路入队后打印队列为空判空条件写错front rear在处理满队列时误判检查full()和empty()逻辑循环队列满时(rear1)%cap front数组队列前面的空间永远用不上假溢出rear撞到容量边界改成循环队列或者出队时搬移数据链表队列tail指向被释放内存删最后一个节点后未把tail置空dequeue后检查head是否为空是则tailnullptr栈pop后旧数据仍能被访问top管理不当越界访问已弹出区域确认有效区间是[0, top)禁止访问top下标阻塞队列永远卡住wait谓词写反或忘记notify检查条件变量是否使用wait(lock, pred)模式内存持续增长链表节点删除时漏了delete/free用内存检测工具扫描逐个检查析构函数6.2 调试队列代码的实战经验我自己调试循环队列时最常用的一种策略是穷举长度法分别用一个容量为1、2、3的循环队列把所有操作序列在纸上手算一遍再和程序输出对比。容量为2时最容易暴露判空判满问题因为容量小front和rear每绕一圈就会碰撞。比如容量为3的循环队列操作序列是入队1、入队2、出队、入队3、入队4此时应该满、出队、入队5。我手工推一遍下标变化再跑程序任何不一致都能立刻发现。6.3 面试题角度如何在这一主题上展示深度面试官问队列和栈的实现其实是在问三个层次第一层是基础实现你要能流利写出循环队列和链表栈的核心逻辑第二层是变体应用比如双端队列、单调队列、优先队列、阻塞队列要知道各自的使用场景第三层是底层原理比如为什么循环队列能提高缓存命中率为什么链表内存开销大什么时候用数组什么时候用链表。我建议你准备一个应用场景倒推实现的思维模板这里需要频繁进出吗有容量限制吗允许阻塞等待吗数据是普通标量还是大对象四个问题一过选型结论自己就出来了。这一套组合拳打下来比单纯背代码要深刻得多面试官会明显感觉到你是真懂。7. 一些个人的实操心得文章写到这里我停下来回顾了一下自己从能用API到能写实现的过程。最深刻的体会是数据结构不是背出来的是调试调出来的。我写循环队列第一次跑通时根本不是我逻辑多清晰而是dump函数打印了一百多行输出我才看明白自己的front和rear错在哪。那种哦原来是这样的时刻比任何教程都管用。另一个体会是不要急着封装。很多人一上来就写模板类、加继承、套接口结果调试时层层封装遮挡了核心逻辑。我建议初学阶段就把所有变量和操作赤裸裸地平铺在一个main函数里跑通了再封装成类。你封装的不是代码是你已经验证过正确性的逻辑。最后分享一个小技巧如果你用Python学这块别用list直接模拟栈因为list.pop(0)是O(n)的不是栈该有的效率。list.append和list.pop()倒是O(1)可以用来模拟栈但要模拟队列用collections.deque它内部就是双向链表加块状数组进出两端都是O(1)。读懂这个库的源码其实又是一次模拟实现的进阶练习。队列和栈模拟实现的精髓不在于你背了多少模板代码而在于你能不能用最底层的手段让这些看似简单的结构在边界条件下依然行为正确。这个能力练好了后面看线程池、消息队列、DFS、BFS这些复杂场景都会顺畅得多。