栈和队列是C初阶学习中最容易被低估的两个容器。很多人在学完数组、vector、list之后觉得栈和队列不过是受限的表稍微包装一下而已于是草草跳过。真正到了写OJ题、参与项目、看开源代码的时候才发现自己在栈的边界处理上频频出错在队列的容量与溢出问题上反复踩坑——更别提面试官最爱的用栈实现队列用队列实现栈单调队列求滑动窗口最大值这些题目全都建立在深刻理解这两种结构的基础上。这篇文章我会从数据结构原理讲到C实现从手写底层到使用标准库把栈和队列的为什么讲透。无论你是刚学完C语法想夯实基础的新手还是准备校招需要系统复习的求职者跟着这篇文章走一遍再回头看那些看似简单的使用场景你会理解完全不一样。我会用大量可以编译运行的实际代码说话所有关键边界条件和参数选择原因都会逐条讲清楚。1. 栈LIFO规则的专制统治者1.1 栈的运行规则后进先出的使用直觉栈的核心特征是一句话后进先出LIFO。你往一个只开放顶部的容器里依次放入A、B、C想取数据时第一个拿到的必然是最后放进去的C。生活里最直观的类比是叠盘子——你总是从最上面拿盘子而不是从底部硬抽。这个受限的特征恰恰是栈强大的地方。它屏蔽了从任意位置插入/删除的可能性只保留了在栈顶操作的一个口子。正因为规则简单你可以非常容易地推演任意操作序列后的结果这是后续实现递归调用、括号匹配、表达式求值、撤销操作等功能的基础。在C里使用栈新手最先接触的往往不是自己手写而是直接用std::stack。但我要强调如果你不知道栈底元素放在哪、栈顶指针怎么移动、栈满了会发生什么你写出的代码一旦遇到边界条件就会变成玄学Bug。所以下面我先带你从零手写一个栈让你把底层机制看清楚。1.2 栈的存储结构选型数组还是链表实现栈有两种常见的底层存储数组和链表。两者各有取舍实际工程中两种都有使用。数组实现的栈依赖于一块连续内存。它的优势是缓存友好——CPU读取连续内存时命中率高访问速度比链表快一个量级劣势是扩容需要整体搬迁数据且需要预先知道或动态判断容量。链表实现的栈不要求连续内存每次入栈只需要申请一个节点理论上没有容量上限但每个节点需要额外的指针空间且频繁的new/delete操作会带来性能损耗。从初学角度我强烈建议先把数组实现练熟。原因有两个第一数组栈的容量管理让你必须考虑栈满与栈空这两个极端情况这对逻辑严谨性的训练价值极大第二C里std::stack默认使用的底层容器是std::deque其本质是分段连续内存的数组变体理解数组栈有助于理解标准库的行为。// 静态数组栈容量固定简单直观 templatetypename T, std::size_t N class StaticStack { private: T data[N]; std::size_t top_; // 栈顶索引指向下一个可写入位置 public: StaticStack() : top_(0) {} void push(const T value) { if (full()) { throw std::overflow_error(栈已满无法入栈); } data[top_] value; } void pop() { if (empty()) { throw std::underflow_error(栈为空无法出栈); } --top_; // 注意这里没有真正销毁元素只是让top_后退 // 如果T是需要释放资源的类型需要调用析构函数 } T top() { if (empty()) { throw std::underflow_error(栈为空无法访问栈顶); } return data[top_ - 1]; } const T top() const { if (empty()) { throw std::underflow_error(栈为空无法访问栈顶); } return data[top_ - 1]; } bool empty() const { return top_ 0; } bool full() const { return top_ N; } std::size_t size() const { return top_; } };上面这段代码的关键在于top_的语义。我让top_指向下一个元素要写入的位置所以栈顶元素在data[top_-1]。入栈时写入后自增出栈时直接自减。这个约定与很多教材中top指向栈顶元素的写法不同但各有优点——指向下一个空位的写法让push的实现更对称且利用top_ 0判断空栈非常自然。另一个值得注意的点是pop并没有真正销毁元素只是让top_后退。在初学阶段如果你存的是int这类平凡类型这没有任何问题但如果你存的是一个带动态资源的自定义对象比如std::string直接调pop会存在资源没被释放的隐患。严谨的写法是调用data[--top_].~T()显式析构不过对于初阶教程先用基础类型跑通逻辑更重要。1.3 动态扩容栈如何优雅地处理容量不足静态栈的局限很明显容量写死一旦数据量超出N就无法工作。现实中更常见的是动态栈——底层使用动态数组满时自动扩容。扩容的直觉方案是不够就翻倍。为什么选择翻倍而不是1因为申请新内存、拷贝旧数据、释放旧内存的成本很高如果每次只增加1个位置那么插入n个元素的总体复杂度是O(n^2)而翻倍扩容让每一次扩容的开销按几何级数增长被均摊插入n个元素的总体复杂度是O(n)均摊到每个元素依然O(1)。这是均摊复杂度的基本思想你以后在看std::vector的实现时会再次遇到。templatetypename T class DynamicStack { private: T* data; std::size_t capacity_; std::size_t top_; void resize() { std::size_t new_capacity capacity_ * 2; T* new_data new T[new_capacity]; for (std::size_t i 0; i top_; i) { new_data[i] data[i]; } delete[] data; data new_data; capacity_ new_capacity; } public: DynamicStack() : capacity_(4), top_(0) { data new T[capacity_]; } ~DynamicStack() { delete[] data; } void push(const T value) { if (top_ capacity_) { resize(); } data[top_] value; } void pop() { if (empty()) { throw std::underflow_error(栈为空无法出栈); } --top_; } T top() { if (empty()) { throw std::underflow_error(栈为空无法访问栈顶); } return data[top_ - 1]; } bool empty() const { return top_ 0; } std::size_t size() const { return top_; } std::size_t capacity() const { return capacity_; } };这个实现里有两个实际工程中值得斟酌的地方。第一初始容量4是在小对象环境下较合理的默认值既不会一上来浪费大量内存也能覆盖绝大多数初学测试场景。第二resize里用的是new T[new_capacity]然后逐元素赋值对复杂类型来说复制成本偏高更好的做法是使用移动语义但初阶阶段先理解机制优化留到后续学习RAII和移动构造时再来改进。我个人的建议是手写动态栈的主要价值在于帮你看清楚容量管理的代价。真正写算法、写项目时直接用标准库容器不要重复造轮子。但如果你准备校招笔试手写栈底层细节是会被问到的这部分一定要吃透。1.4 手写栈的常见边界Bug清单我见过很多初学C的同学在实现栈时犯同样的错误这里集中列出来你可以对照自查栈顶指针初始值不一致导致的错位有人让top指向-1表示栈空有人让它指向0表示下一个写入位置。两种约定都能工作但混用就会出错——一会儿用data[top]取栈顶一会儿用data[top-1]数据全部错乱。我的建议选定一种约定所有方法严格遵循。pop之前不检查空栈空栈调用pop会直接越界访问未定义内存可能崩溃也可能返回垃圾数据。务必在pop和top里检查empty()。扩容后忘记更新容量一旦capacity_没更新下一次push又满足top_ capacity_就再次扩容逻辑上虽然不会崩溃但性能剧烈下降。析构函数写成空实现如果栈存的是自己new出来的指针而析构时只释放data本身所有元素都会内存泄漏。这些问题解决起来都不难难的是每次写代码都有意识地检查这些点。多写几次肌肉记忆就养成了。2. 队列FIFO的世界也需要精妙设计2.1 队列的运行规则排队买菜的基本逻辑队列的核心规则是先进先出FIFO。谁先来谁先走就像食堂排队打饭后来的人不能插队到前面。队列有两个口队尾负责入队队头负责出队数据从一头进从另一头出。和栈一样队列的规则限制成就了它的价值。操作系统中进程调度、网络请求的缓冲、打印机任务队列、广度优先搜索全都依赖这个先来先服务的特性。工程里的消息队列、任务队列底层思想正是这里要讲的队列。2.2 顺序队列的假溢出与循环队列的诞生假设你用一块连续数组实现队列队头指针front指向第一个元素队尾指针rear指向最后一个元素。入队时rear出队时front。初看没问题但真实使用中很快会遇到尴尬局面队列不断入队出队后rear走到了数组末尾数组前面却空着一大片——因为出队只是让front前进却没有把后面的元素往前平移。这就是假溢出明明数组前半段是空的但rear已经到达末尾新元素入队时直接越界。要解决假溢出最优雅的方案是循环队列把数组想象成一个环rear走到末尾后自己绕回开头。templatetypename T, std::size_t N class CircularQueue { private: T data[N]; std::size_t front_; // 队头索引指向队头元素 std::size_t rear_; // 队尾索引指向下一个写入位置 public: CircularQueue() : front_(0), rear_(0) {} void enqueue(const T value) { if (full()) { throw std::overflow_error(队列已满); } data[rear_] value; rear_ (rear_ 1) % N; } void dequeue() { if (empty()) { throw std::underflow_error(队列为空); } front_ (front_ 1) % N; } T front() { if (empty()) { throw std::underflow_error(队列为空); } return data[front_]; } bool empty() const { return front_ rear_; } bool full() const { return (rear_ 1) % N front_; } std::size_t size() const { return (rear_ - front_ N) % N; } };循环队列最难理解的部分是判空和判满。这里用front_ rear_表示空用(rear_ 1) % N front_表示满。为什么满的时候不是rear_ front_因为如果允许队尾追平队头那么满和空就没有区别了——都是两个指针相等。所以循环队列最常见的实现是牺牲一个存储单元让rear_指向下一个写入位置当rear_绕一圈追上front_时我们认为队列已满实际上数组还有一个空位。这个空位是死空间用它的代价换来了判空判满的简单性。实际工程中也有用计数器或标志位区分空满的方案那可以充分利用最后一个空位但代码会更复杂。size()的计算公式(rear_ - front_ N) % N同样值得留意rear_ - front_可能为负因为rear绕过表头加了N再取模就保证结果落在0到N-1之间。这是循环队列处理回绕的标准写法务必记住。2.3 链式队列没有容量上限的等待队伍链式队列用链表存储每个节点包含数据和next指针。队头用head标记队尾用tail标记——注意这里与单链表的经典头部插入不同队列必须在tail处入队在头部出队否则出队时需要遍历到倒数第二个节点复杂度退化为O(n)。templatetypename T class LinkedQueue { private: struct Node { T data; Node* next; Node(const T val) : data(val), next(nullptr) {} }; Node* head_; // 队头 Node* tail_; // 队尾 std::size_t size_; public: LinkedQueue() : head_(nullptr), tail_(nullptr), size_(0) {} ~LinkedQueue() { while (head_) { Node* tmp head_; head_ head_-next; delete tmp; } } void enqueue(const T value) { Node* new_node new Node(value); if (tail_) { tail_-next new_node; } else { head_ new_node; } tail_ new_node; size_; } void dequeue() { if (empty()) { throw std::underflow_error(队列为空); } Node* tmp head_; head_ head_-next; if (!head_) { tail_ nullptr; } delete tmp; --size_; } T front() { if (empty()) { throw std::underflow_error(队列为空); } return head_-data; } bool empty() const { return head_ nullptr; } std::size_t size() const { return size_; } };链式队列有一个细节总被新手忽略删除最后一个节点时需要把tail_也置空。因为如果你只更新head_那么head_变成nullptr但tail_还指向那个已被删除的节点之后你调用enqueue时tail_-next会访问已经释放的内存产生未定义行为。这种尾指针悬挂的问题调试时非常隐蔽。链式队列与循环队列的取舍链式队列没有容量上限插入和删除都是O(1)不考虑new的开销适合元素数量不确定、频繁动态变化的场景循环队列使用连续内存缓存友好性能更优适合容量可预估、追求高吞吐的场景。2.4 双端队列与优先队列队列家族的扩展初学阶段还值得认识两个队列家族的成员。std::deque双端队列允许在队头和队尾两侧进行O(1)插入删除。它之所以重要是因为C标准库的std::stack和std::queue默认都用它作为底层容器。deque在实现上采用分段连续内存维护一个中控器管理多个连续缓冲区这使得它在双端都能高效操作而且扩容时不需要像vector那样整体搬迁数据。std::priority_queue优先队列则打破FIFO规则——每次出队的元素是当前优先级最高的元素而非最早入队的元素。它底层用二叉堆实现插入和删除的时间复杂度都是O(log n)。优先队列在任务调度CPU调度、定时器、图算法Dijkstra最短路径、数据流中找Top K等场景中非常常用。初学阶段建议先把普通队列吃透优先队列可以作为下一阶段的学习目标。3. 标准库容器从手写到会用接口3.1 容器适配器的概念为什么stack和queue不直接叫容器std::stack和std::queue在C标准库中不是独立的容器而是容器适配器。什么意思呢它们不自己维护内存而是内部封装另一个容器默认为std::deque只对外开放受限的操作接口。stack只让你操作栈顶queue只让你操作队头和队尾——底层仍然是一块或几块连续内存但对外隐藏了中间部分。选deque作为默认底层容器有两个原因。第一deque可以在头尾两端都高效插入删除刚好同时满足stack的栈顶操作和queue的队头出、队尾入需求第二deque扩容不搬迁整体数据比vector在频繁push/pop的场景下更稳定。你也可以显式地给stack指定其他底层容器比如std::stackint, std::vectorint——这同样合法只是vector在尾部操作性能足够好栈恰好只用尾端所以在某些场景下用vector作底层的stack甚至更快。3.2 std::stack的常用成员函数与使用示例std::stack的接口绝对够用关键就几个push(x)入栈将x放到栈顶。pop()出栈删除栈顶元素。注意pop不返回弹出值。这个设计让很多从其他语言转过来的程序员困惑原因是为了保证异常安全——如果你想同时拿值和弹出直接用top()先取值再调用pop()即可。top()返回栈顶元素的引用可用于读取和修改。empty()/size()判空与大小。#include iostream #include stack int main() { std::stackint st; st.push(10); st.push(20); st.push(30); std::cout 栈顶元素: st.top() std::endl; // 30 st.pop(); std::cout 弹出后栈顶: st.top() std::endl; // 20 std::cout 元素数量: st.size() std::endl; // 2 return 0; }std::stack还有一个容易踩的坑它不提供遍历接口也没有迭代器。如果你想看栈里面的全部元素只能一次次top()然后pop()这会把栈清空。所以在调试需要观察栈内容时我习惯把数据先复制一份到一个临时栈或vector里再慢慢看后面在第5节会给出一个调试小技巧。3.3 std::queue的常用成员函数与使用示例std::queue同样简单push(x)从队尾入队。pop()从队头出队同样不返回出队值。front()返回队头元素的引用。back()返回队尾元素的引用。empty()/size()。#include iostream #include queue int main() { std::queueint q; q.push(1); q.push(2); q.push(3); std::cout 队头: q.front() std::endl; // 1 std::cout 队尾: q.back() std::endl; // 3 while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; // 输出 1 2 3 return 0; }有些教材会把栈和队列比喻成受限的表这个说法很准确。std::stack和std::queue的用户接口只暴露操作两端的窗口这是它们与std::vector/std::deque最大的区别。3.4 用C标准库时该注意的坑在循环里pop容器时使用while(!q.empty())不要用for (int i 0; i q.size(); i)因为pop会改变size()循环次数会动态减少结果不符合预期。优先使用empty()而非size()0虽然两者等价但标准库更推荐用empty()因为有些容器的size()复杂度可能不是O(1)虽然stack和queue是养成好习惯。不要在栈或队列中存放原始指针除非你明确所有权对象生命周期管理是C最棘手的问题之一。初学时不建议直接在stack/queue里存裸指针并用new创建否则清理困难改用智能指针std::shared_ptr或直接存对象值。4. 经典应用场景栈和队列的实战价值4.1 函数调用栈每一个函数调用都是一次压栈栈最深入人心的应用场景是函数调用。当程序调用一个函数时系统会在调用栈上压入一个栈帧stack frame栈帧里存放函数的返回地址、参数、局部变量等信息。函数返回时栈帧被弹出控制权回到调用位置。这就是为什么递归调用过深会导致栈溢出——每一层递归都压入一个新的栈帧而调用栈的空间是有限的。理解这一点对写C程序很重要。比如你写一个没有终止条件的递归函数或者递归深度达到几十万层的深度优先搜索程序大概率会崩溃报错信息常常是stack overflow。这不是编译器出了问题就是调用栈空间被耗尽了。看到这里你可能会想函数调用栈跟std::stack有什么关系其实关系很大——任何嵌套调用的结构从语言运行时到表达式求值本质都是用一个栈来维护先进入的调用要先等待后进入的调用可以先返回这一规则。LIFO的天然匹配让栈成为这类问题的标准解法。4.2 括号匹配与表达式求值用栈解决嵌套结构问题初学阶段最经典的栈练习是括号匹配判断给定一个字符串包含()、[]、{}判断括号是否正确配平。算法思路很简单遍历字符串遇到左括号就入栈遇到右括号就与栈顶元素匹配如果匹配成功则弹出栈顶否则直接返回不匹配。遍历结束后如果栈为空说明全部匹配否则存在未闭合的左括号。这个问题的关键是它精准利用了栈的LIFO特性——匹配一对括号时最内层的括号一定在栈顶后遇到的左括号必须先生效。bool isMatching(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 {)) { st.pop(); } else { return false; } } } return st.empty(); }表达式的后缀表达逆波兰表达式求值也用栈遇到操作数就入栈遇到运算符就弹出两个操作数计算再将结果压回栈。栈在这里充当了中间结果的暂存区让表达式从左到右一遍扫描即可完成计算。在刷题训练里这两个案例几乎是栈必考题熟练之后你再看其他嵌套匹配问题如HTML标签匹配、数组下标括号匹配思路会非常顺畅。4.3 工程场景中的队列谁在排队又是谁在消费队列在工程中的应用面比栈更广毕竟生产者-消费者模型天然符合FIFO思想。最典型的例子是任务队列。在多线程环境中一个或多个生产者线程把任务投递到队列的一端一个或多个消费者线程从另一端取任务执行。这样一来任务的生产速度和消费速度可以不同步——生产快了任务堆积在队列中排队等待消费快了队列变空生产者再补上。在项目里你会听到消息队列这个词比如Kafka、RabbitMQ、RocketMQ它们虽然是分布式场景中的中间件但最核心的模型就是队列消息先进入队列消费者按顺序取走消费。它们额外解决了持久化、可靠性、顺序性、分布式协调等问题但基本封装的先进先出思想与你今天在这里实现的队列如出一辙。另一个工程常见的队列是阻塞队列。当队列满时生产者线程被阻塞直到消费者取走元素腾出空间当队列空时消费者线程被阻塞直到生产者投递新元素。线程池内部一般会维护一个阻塞队列来存放待执行任务这在以后写多线程程序时你会遇到。4.4 算法竞赛中的队列BFS、滑动窗口与单调队列除了工程场景队列也是算法中的基础工具。广度优先搜索BFS遍历图结构时用队列记录当前层的所有节点先处理完一层再进入下一层。这正是FIFO天然适配的场景先发现的节点先扩展保证了按层级遍历。树的层序遍历、迷宫最短路径本质上都是BFS。滑动窗口最大值问题给定数组和窗口大小k求每个窗口中的最大值使用单调队列解决队列中元素按从队头到队尾严格递减每次窗口滑动时把新元素插入队列前先弹出所有比它小的队尾元素同时让过期元素从队头弹出。这样队头永远是当前窗口的最大值每个元素最多进出队列一次总时间复杂度O(n)。我见过很多初学者直接背单调队列的代码却不懂为什么队列里要弹出较小元素其实很简单当新元素比队尾元素大时队尾元素在后续窗口里不可能再成为最大值新元素更大且更晚过期留着它只会增加无用的比较成本。这个淘汰不可能成为答案的元素的思想就是单调队列的精髓。初学阶段可以先理解整体目标等自己做几道滑动窗口题后再细品。5. 初学必踩的坑与面试考点速查5.1 初学阶段的高频Bug实录我把这几年看到学生反复犯的错误整理成几类写代码时你可以主动规避混淆top()和pop()有些同学以为pop()会返回栈顶元素于是直接写int x st.pop();编译报错后还不明白原因。记住C的pop()是void需要先top()取值再pop()弹出。在队列里使用back()取队尾却用来修改队头数据逻辑颠倒修出来的数据完全错乱。明确front()是队头、back()是队尾两者只差一个最近入队的元素。迭代遍历中动态改变容器一边用size()做循环上界一边pop()会把遍历范围缩水。直接改用while(!container.empty())这种模式语义更清晰。使用未定义行为例如在空栈/空队列上调用top()、front()、pop()。标准库容器对这些操作的行为未定义可能崩溃也可能返回垃圾数据依赖它等于把命运交给编译器。忘记包含头文件std::stack在stack中std::queue在queue中std::deque在deque中。编译报错时先检查头文件。5.2 面试高频考察点与分析思路校招笔试和面试中栈和队列相关的问题已经形成了固定题库常见的解题方向如下用两个栈实现队列入队时把元素压入stack1出队时若stack2为空则将stack1的所有元素依次弹出并压入stack2再从stack2弹出栈顶。这样stack2的栈顶就是最早入队的元素两个栈模拟出了FIFO效果。均摊复杂度O(1)。用两个队列实现栈入栈时正常入queue1出栈时把queue1除队尾外的所有元素搬到queue2然后弹出queue1中最后一个元素再把queue2的元素搬回queue1。每次出栈需要O(n)操作这是用队列模拟栈绕不开的成本。设计一个能O(1)获取最小值的栈在栈内部额外维护一个最小栈每次push时比较新元素与当前最小值把较小者压入最小栈pop时同步弹出最小栈的栈顶。借助空间换时间的思想。单调栈的经典应用求数组中每个元素左边第一个比它小的元素位置。维护一个栈栈内元素保持单调递增遍历时不断弹出比当前元素大或小的栈顶剩下的栈顶就是答案。这类问题模式化较强刷3~5道题即可掌握套路。这里我建议初学者不要急于背代码而是先用自己的话把上面每个问题的数据结构组合逻辑讲给同学听讲清楚了再动手写。很多面试者就是代码会背但被追问为什么这样设计时卡壳。5.3 调试技巧观察栈和队列的内容而不破坏它们栈和队列不提供迭代器调试时想观察内部数据比较麻烦。最简单的办法是复制拷贝一份临时栈/队列然后不断从临时对象中弹出元素打印。这个方法会额外消耗O(n)的时间与空间但调试场景下完全可接受。void debugPrintStack(std::stackint st) { // 按值传递自动复制 std::cout [栈内元素自顶向下] ; while (!st.empty()) { std::cout st.top() ; st.pop(); } std::cout std::endl; } void debugPrintQueue(std::queueint q) { // 按值传递自动复制 std::cout [队列内元素自队头到队尾] ; while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; }这两个函数的妙处在于按值传递函数内部pop的是副本原始容器不受影响。你可以随时把它加入自己的调试工具集。另一个思路是改用std::vector作为栈的底层容器比如std::stackint, std::vectorint然后想办法拿到那个vector的引用在标准实现中stack的受保护成员c可以被继承访问但初学阶段不必折腾直接用下标遍历。5.4 手写实现还是直接用标准库这个问题我被问过很多次既然标准库有std::stack和std::queue自己手写还有意义吗我的观点很明确学习阶段必须手写工程阶段直接用标准库。学习阶段手写是为了理解栈顶指针随入栈出栈怎么移动、循环队列的容量怎么算、链表节点怎么安全释放。这些细节是编程思维的磨刀石——尤其是循环队列的取模绕回和链表的尾指针维护几乎能锻炼你处理所有边界条件的能力。工程阶段直接用标准库则是因为标准库经过严格的测试和极致的性能调优接口语义清楚可以用最小的成本完成工作。项目里自己维护一个栈/队列实现不仅可能带来Bug和性能问题还会让读你代码的同事感到困惑。当然如果你在实现自带库的嵌入式环境、内存极小的芯片上做开发那么手写一个精简的栈/队列是必要的——到那时你会感谢学习阶段自己认真推演过每一个指针的偏移。我在实际带项目和学习C的过程中最大的体会是栈和队列看似基础但几乎所有复杂系统的角落里都有它们。操作系统内核的任务栈、网络协议栈的报文段、编译器的语法分析栈、线程池的阻塞队列、缓存系统的LRU队列这些高大上的内容拆开底层核心逻辑就是你今天在纸上反复画过的入栈出栈、入队出队。最后再分享一个实用的学习方法学完这部分后建议你做三件事。第一不看任何参考代码自己手写一个栈和一个循环队列并用测试用例包括空容器操作、满容量操作跑通。第二实现括号匹配和用栈实现队列这两道题做完后看别人的题解对比自己在边界处理和代码结构上的差异。第三翻开std::deque的文档弄清楚它和std::vector的区别这能帮你理解标准库为何为stack/queue选择deque作为默认底层容器。搞定这三件事栈和队列这个板块你就真正过关了。
C++栈与队列深度解析：从手写底层到标准库实战
栈和队列是C初阶学习中最容易被低估的两个容器。很多人在学完数组、vector、list之后觉得栈和队列不过是受限的表稍微包装一下而已于是草草跳过。真正到了写OJ题、参与项目、看开源代码的时候才发现自己在栈的边界处理上频频出错在队列的容量与溢出问题上反复踩坑——更别提面试官最爱的用栈实现队列用队列实现栈单调队列求滑动窗口最大值这些题目全都建立在深刻理解这两种结构的基础上。这篇文章我会从数据结构原理讲到C实现从手写底层到使用标准库把栈和队列的为什么讲透。无论你是刚学完C语法想夯实基础的新手还是准备校招需要系统复习的求职者跟着这篇文章走一遍再回头看那些看似简单的使用场景你会理解完全不一样。我会用大量可以编译运行的实际代码说话所有关键边界条件和参数选择原因都会逐条讲清楚。1. 栈LIFO规则的专制统治者1.1 栈的运行规则后进先出的使用直觉栈的核心特征是一句话后进先出LIFO。你往一个只开放顶部的容器里依次放入A、B、C想取数据时第一个拿到的必然是最后放进去的C。生活里最直观的类比是叠盘子——你总是从最上面拿盘子而不是从底部硬抽。这个受限的特征恰恰是栈强大的地方。它屏蔽了从任意位置插入/删除的可能性只保留了在栈顶操作的一个口子。正因为规则简单你可以非常容易地推演任意操作序列后的结果这是后续实现递归调用、括号匹配、表达式求值、撤销操作等功能的基础。在C里使用栈新手最先接触的往往不是自己手写而是直接用std::stack。但我要强调如果你不知道栈底元素放在哪、栈顶指针怎么移动、栈满了会发生什么你写出的代码一旦遇到边界条件就会变成玄学Bug。所以下面我先带你从零手写一个栈让你把底层机制看清楚。1.2 栈的存储结构选型数组还是链表实现栈有两种常见的底层存储数组和链表。两者各有取舍实际工程中两种都有使用。数组实现的栈依赖于一块连续内存。它的优势是缓存友好——CPU读取连续内存时命中率高访问速度比链表快一个量级劣势是扩容需要整体搬迁数据且需要预先知道或动态判断容量。链表实现的栈不要求连续内存每次入栈只需要申请一个节点理论上没有容量上限但每个节点需要额外的指针空间且频繁的new/delete操作会带来性能损耗。从初学角度我强烈建议先把数组实现练熟。原因有两个第一数组栈的容量管理让你必须考虑栈满与栈空这两个极端情况这对逻辑严谨性的训练价值极大第二C里std::stack默认使用的底层容器是std::deque其本质是分段连续内存的数组变体理解数组栈有助于理解标准库的行为。// 静态数组栈容量固定简单直观 templatetypename T, std::size_t N class StaticStack { private: T data[N]; std::size_t top_; // 栈顶索引指向下一个可写入位置 public: StaticStack() : top_(0) {} void push(const T value) { if (full()) { throw std::overflow_error(栈已满无法入栈); } data[top_] value; } void pop() { if (empty()) { throw std::underflow_error(栈为空无法出栈); } --top_; // 注意这里没有真正销毁元素只是让top_后退 // 如果T是需要释放资源的类型需要调用析构函数 } T top() { if (empty()) { throw std::underflow_error(栈为空无法访问栈顶); } return data[top_ - 1]; } const T top() const { if (empty()) { throw std::underflow_error(栈为空无法访问栈顶); } return data[top_ - 1]; } bool empty() const { return top_ 0; } bool full() const { return top_ N; } std::size_t size() const { return top_; } };上面这段代码的关键在于top_的语义。我让top_指向下一个元素要写入的位置所以栈顶元素在data[top_-1]。入栈时写入后自增出栈时直接自减。这个约定与很多教材中top指向栈顶元素的写法不同但各有优点——指向下一个空位的写法让push的实现更对称且利用top_ 0判断空栈非常自然。另一个值得注意的点是pop并没有真正销毁元素只是让top_后退。在初学阶段如果你存的是int这类平凡类型这没有任何问题但如果你存的是一个带动态资源的自定义对象比如std::string直接调pop会存在资源没被释放的隐患。严谨的写法是调用data[--top_].~T()显式析构不过对于初阶教程先用基础类型跑通逻辑更重要。1.3 动态扩容栈如何优雅地处理容量不足静态栈的局限很明显容量写死一旦数据量超出N就无法工作。现实中更常见的是动态栈——底层使用动态数组满时自动扩容。扩容的直觉方案是不够就翻倍。为什么选择翻倍而不是1因为申请新内存、拷贝旧数据、释放旧内存的成本很高如果每次只增加1个位置那么插入n个元素的总体复杂度是O(n^2)而翻倍扩容让每一次扩容的开销按几何级数增长被均摊插入n个元素的总体复杂度是O(n)均摊到每个元素依然O(1)。这是均摊复杂度的基本思想你以后在看std::vector的实现时会再次遇到。templatetypename T class DynamicStack { private: T* data; std::size_t capacity_; std::size_t top_; void resize() { std::size_t new_capacity capacity_ * 2; T* new_data new T[new_capacity]; for (std::size_t i 0; i top_; i) { new_data[i] data[i]; } delete[] data; data new_data; capacity_ new_capacity; } public: DynamicStack() : capacity_(4), top_(0) { data new T[capacity_]; } ~DynamicStack() { delete[] data; } void push(const T value) { if (top_ capacity_) { resize(); } data[top_] value; } void pop() { if (empty()) { throw std::underflow_error(栈为空无法出栈); } --top_; } T top() { if (empty()) { throw std::underflow_error(栈为空无法访问栈顶); } return data[top_ - 1]; } bool empty() const { return top_ 0; } std::size_t size() const { return top_; } std::size_t capacity() const { return capacity_; } };这个实现里有两个实际工程中值得斟酌的地方。第一初始容量4是在小对象环境下较合理的默认值既不会一上来浪费大量内存也能覆盖绝大多数初学测试场景。第二resize里用的是new T[new_capacity]然后逐元素赋值对复杂类型来说复制成本偏高更好的做法是使用移动语义但初阶阶段先理解机制优化留到后续学习RAII和移动构造时再来改进。我个人的建议是手写动态栈的主要价值在于帮你看清楚容量管理的代价。真正写算法、写项目时直接用标准库容器不要重复造轮子。但如果你准备校招笔试手写栈底层细节是会被问到的这部分一定要吃透。1.4 手写栈的常见边界Bug清单我见过很多初学C的同学在实现栈时犯同样的错误这里集中列出来你可以对照自查栈顶指针初始值不一致导致的错位有人让top指向-1表示栈空有人让它指向0表示下一个写入位置。两种约定都能工作但混用就会出错——一会儿用data[top]取栈顶一会儿用data[top-1]数据全部错乱。我的建议选定一种约定所有方法严格遵循。pop之前不检查空栈空栈调用pop会直接越界访问未定义内存可能崩溃也可能返回垃圾数据。务必在pop和top里检查empty()。扩容后忘记更新容量一旦capacity_没更新下一次push又满足top_ capacity_就再次扩容逻辑上虽然不会崩溃但性能剧烈下降。析构函数写成空实现如果栈存的是自己new出来的指针而析构时只释放data本身所有元素都会内存泄漏。这些问题解决起来都不难难的是每次写代码都有意识地检查这些点。多写几次肌肉记忆就养成了。2. 队列FIFO的世界也需要精妙设计2.1 队列的运行规则排队买菜的基本逻辑队列的核心规则是先进先出FIFO。谁先来谁先走就像食堂排队打饭后来的人不能插队到前面。队列有两个口队尾负责入队队头负责出队数据从一头进从另一头出。和栈一样队列的规则限制成就了它的价值。操作系统中进程调度、网络请求的缓冲、打印机任务队列、广度优先搜索全都依赖这个先来先服务的特性。工程里的消息队列、任务队列底层思想正是这里要讲的队列。2.2 顺序队列的假溢出与循环队列的诞生假设你用一块连续数组实现队列队头指针front指向第一个元素队尾指针rear指向最后一个元素。入队时rear出队时front。初看没问题但真实使用中很快会遇到尴尬局面队列不断入队出队后rear走到了数组末尾数组前面却空着一大片——因为出队只是让front前进却没有把后面的元素往前平移。这就是假溢出明明数组前半段是空的但rear已经到达末尾新元素入队时直接越界。要解决假溢出最优雅的方案是循环队列把数组想象成一个环rear走到末尾后自己绕回开头。templatetypename T, std::size_t N class CircularQueue { private: T data[N]; std::size_t front_; // 队头索引指向队头元素 std::size_t rear_; // 队尾索引指向下一个写入位置 public: CircularQueue() : front_(0), rear_(0) {} void enqueue(const T value) { if (full()) { throw std::overflow_error(队列已满); } data[rear_] value; rear_ (rear_ 1) % N; } void dequeue() { if (empty()) { throw std::underflow_error(队列为空); } front_ (front_ 1) % N; } T front() { if (empty()) { throw std::underflow_error(队列为空); } return data[front_]; } bool empty() const { return front_ rear_; } bool full() const { return (rear_ 1) % N front_; } std::size_t size() const { return (rear_ - front_ N) % N; } };循环队列最难理解的部分是判空和判满。这里用front_ rear_表示空用(rear_ 1) % N front_表示满。为什么满的时候不是rear_ front_因为如果允许队尾追平队头那么满和空就没有区别了——都是两个指针相等。所以循环队列最常见的实现是牺牲一个存储单元让rear_指向下一个写入位置当rear_绕一圈追上front_时我们认为队列已满实际上数组还有一个空位。这个空位是死空间用它的代价换来了判空判满的简单性。实际工程中也有用计数器或标志位区分空满的方案那可以充分利用最后一个空位但代码会更复杂。size()的计算公式(rear_ - front_ N) % N同样值得留意rear_ - front_可能为负因为rear绕过表头加了N再取模就保证结果落在0到N-1之间。这是循环队列处理回绕的标准写法务必记住。2.3 链式队列没有容量上限的等待队伍链式队列用链表存储每个节点包含数据和next指针。队头用head标记队尾用tail标记——注意这里与单链表的经典头部插入不同队列必须在tail处入队在头部出队否则出队时需要遍历到倒数第二个节点复杂度退化为O(n)。templatetypename T class LinkedQueue { private: struct Node { T data; Node* next; Node(const T val) : data(val), next(nullptr) {} }; Node* head_; // 队头 Node* tail_; // 队尾 std::size_t size_; public: LinkedQueue() : head_(nullptr), tail_(nullptr), size_(0) {} ~LinkedQueue() { while (head_) { Node* tmp head_; head_ head_-next; delete tmp; } } void enqueue(const T value) { Node* new_node new Node(value); if (tail_) { tail_-next new_node; } else { head_ new_node; } tail_ new_node; size_; } void dequeue() { if (empty()) { throw std::underflow_error(队列为空); } Node* tmp head_; head_ head_-next; if (!head_) { tail_ nullptr; } delete tmp; --size_; } T front() { if (empty()) { throw std::underflow_error(队列为空); } return head_-data; } bool empty() const { return head_ nullptr; } std::size_t size() const { return size_; } };链式队列有一个细节总被新手忽略删除最后一个节点时需要把tail_也置空。因为如果你只更新head_那么head_变成nullptr但tail_还指向那个已被删除的节点之后你调用enqueue时tail_-next会访问已经释放的内存产生未定义行为。这种尾指针悬挂的问题调试时非常隐蔽。链式队列与循环队列的取舍链式队列没有容量上限插入和删除都是O(1)不考虑new的开销适合元素数量不确定、频繁动态变化的场景循环队列使用连续内存缓存友好性能更优适合容量可预估、追求高吞吐的场景。2.4 双端队列与优先队列队列家族的扩展初学阶段还值得认识两个队列家族的成员。std::deque双端队列允许在队头和队尾两侧进行O(1)插入删除。它之所以重要是因为C标准库的std::stack和std::queue默认都用它作为底层容器。deque在实现上采用分段连续内存维护一个中控器管理多个连续缓冲区这使得它在双端都能高效操作而且扩容时不需要像vector那样整体搬迁数据。std::priority_queue优先队列则打破FIFO规则——每次出队的元素是当前优先级最高的元素而非最早入队的元素。它底层用二叉堆实现插入和删除的时间复杂度都是O(log n)。优先队列在任务调度CPU调度、定时器、图算法Dijkstra最短路径、数据流中找Top K等场景中非常常用。初学阶段建议先把普通队列吃透优先队列可以作为下一阶段的学习目标。3. 标准库容器从手写到会用接口3.1 容器适配器的概念为什么stack和queue不直接叫容器std::stack和std::queue在C标准库中不是独立的容器而是容器适配器。什么意思呢它们不自己维护内存而是内部封装另一个容器默认为std::deque只对外开放受限的操作接口。stack只让你操作栈顶queue只让你操作队头和队尾——底层仍然是一块或几块连续内存但对外隐藏了中间部分。选deque作为默认底层容器有两个原因。第一deque可以在头尾两端都高效插入删除刚好同时满足stack的栈顶操作和queue的队头出、队尾入需求第二deque扩容不搬迁整体数据比vector在频繁push/pop的场景下更稳定。你也可以显式地给stack指定其他底层容器比如std::stackint, std::vectorint——这同样合法只是vector在尾部操作性能足够好栈恰好只用尾端所以在某些场景下用vector作底层的stack甚至更快。3.2 std::stack的常用成员函数与使用示例std::stack的接口绝对够用关键就几个push(x)入栈将x放到栈顶。pop()出栈删除栈顶元素。注意pop不返回弹出值。这个设计让很多从其他语言转过来的程序员困惑原因是为了保证异常安全——如果你想同时拿值和弹出直接用top()先取值再调用pop()即可。top()返回栈顶元素的引用可用于读取和修改。empty()/size()判空与大小。#include iostream #include stack int main() { std::stackint st; st.push(10); st.push(20); st.push(30); std::cout 栈顶元素: st.top() std::endl; // 30 st.pop(); std::cout 弹出后栈顶: st.top() std::endl; // 20 std::cout 元素数量: st.size() std::endl; // 2 return 0; }std::stack还有一个容易踩的坑它不提供遍历接口也没有迭代器。如果你想看栈里面的全部元素只能一次次top()然后pop()这会把栈清空。所以在调试需要观察栈内容时我习惯把数据先复制一份到一个临时栈或vector里再慢慢看后面在第5节会给出一个调试小技巧。3.3 std::queue的常用成员函数与使用示例std::queue同样简单push(x)从队尾入队。pop()从队头出队同样不返回出队值。front()返回队头元素的引用。back()返回队尾元素的引用。empty()/size()。#include iostream #include queue int main() { std::queueint q; q.push(1); q.push(2); q.push(3); std::cout 队头: q.front() std::endl; // 1 std::cout 队尾: q.back() std::endl; // 3 while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; // 输出 1 2 3 return 0; }有些教材会把栈和队列比喻成受限的表这个说法很准确。std::stack和std::queue的用户接口只暴露操作两端的窗口这是它们与std::vector/std::deque最大的区别。3.4 用C标准库时该注意的坑在循环里pop容器时使用while(!q.empty())不要用for (int i 0; i q.size(); i)因为pop会改变size()循环次数会动态减少结果不符合预期。优先使用empty()而非size()0虽然两者等价但标准库更推荐用empty()因为有些容器的size()复杂度可能不是O(1)虽然stack和queue是养成好习惯。不要在栈或队列中存放原始指针除非你明确所有权对象生命周期管理是C最棘手的问题之一。初学时不建议直接在stack/queue里存裸指针并用new创建否则清理困难改用智能指针std::shared_ptr或直接存对象值。4. 经典应用场景栈和队列的实战价值4.1 函数调用栈每一个函数调用都是一次压栈栈最深入人心的应用场景是函数调用。当程序调用一个函数时系统会在调用栈上压入一个栈帧stack frame栈帧里存放函数的返回地址、参数、局部变量等信息。函数返回时栈帧被弹出控制权回到调用位置。这就是为什么递归调用过深会导致栈溢出——每一层递归都压入一个新的栈帧而调用栈的空间是有限的。理解这一点对写C程序很重要。比如你写一个没有终止条件的递归函数或者递归深度达到几十万层的深度优先搜索程序大概率会崩溃报错信息常常是stack overflow。这不是编译器出了问题就是调用栈空间被耗尽了。看到这里你可能会想函数调用栈跟std::stack有什么关系其实关系很大——任何嵌套调用的结构从语言运行时到表达式求值本质都是用一个栈来维护先进入的调用要先等待后进入的调用可以先返回这一规则。LIFO的天然匹配让栈成为这类问题的标准解法。4.2 括号匹配与表达式求值用栈解决嵌套结构问题初学阶段最经典的栈练习是括号匹配判断给定一个字符串包含()、[]、{}判断括号是否正确配平。算法思路很简单遍历字符串遇到左括号就入栈遇到右括号就与栈顶元素匹配如果匹配成功则弹出栈顶否则直接返回不匹配。遍历结束后如果栈为空说明全部匹配否则存在未闭合的左括号。这个问题的关键是它精准利用了栈的LIFO特性——匹配一对括号时最内层的括号一定在栈顶后遇到的左括号必须先生效。bool isMatching(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 {)) { st.pop(); } else { return false; } } } return st.empty(); }表达式的后缀表达逆波兰表达式求值也用栈遇到操作数就入栈遇到运算符就弹出两个操作数计算再将结果压回栈。栈在这里充当了中间结果的暂存区让表达式从左到右一遍扫描即可完成计算。在刷题训练里这两个案例几乎是栈必考题熟练之后你再看其他嵌套匹配问题如HTML标签匹配、数组下标括号匹配思路会非常顺畅。4.3 工程场景中的队列谁在排队又是谁在消费队列在工程中的应用面比栈更广毕竟生产者-消费者模型天然符合FIFO思想。最典型的例子是任务队列。在多线程环境中一个或多个生产者线程把任务投递到队列的一端一个或多个消费者线程从另一端取任务执行。这样一来任务的生产速度和消费速度可以不同步——生产快了任务堆积在队列中排队等待消费快了队列变空生产者再补上。在项目里你会听到消息队列这个词比如Kafka、RabbitMQ、RocketMQ它们虽然是分布式场景中的中间件但最核心的模型就是队列消息先进入队列消费者按顺序取走消费。它们额外解决了持久化、可靠性、顺序性、分布式协调等问题但基本封装的先进先出思想与你今天在这里实现的队列如出一辙。另一个工程常见的队列是阻塞队列。当队列满时生产者线程被阻塞直到消费者取走元素腾出空间当队列空时消费者线程被阻塞直到生产者投递新元素。线程池内部一般会维护一个阻塞队列来存放待执行任务这在以后写多线程程序时你会遇到。4.4 算法竞赛中的队列BFS、滑动窗口与单调队列除了工程场景队列也是算法中的基础工具。广度优先搜索BFS遍历图结构时用队列记录当前层的所有节点先处理完一层再进入下一层。这正是FIFO天然适配的场景先发现的节点先扩展保证了按层级遍历。树的层序遍历、迷宫最短路径本质上都是BFS。滑动窗口最大值问题给定数组和窗口大小k求每个窗口中的最大值使用单调队列解决队列中元素按从队头到队尾严格递减每次窗口滑动时把新元素插入队列前先弹出所有比它小的队尾元素同时让过期元素从队头弹出。这样队头永远是当前窗口的最大值每个元素最多进出队列一次总时间复杂度O(n)。我见过很多初学者直接背单调队列的代码却不懂为什么队列里要弹出较小元素其实很简单当新元素比队尾元素大时队尾元素在后续窗口里不可能再成为最大值新元素更大且更晚过期留着它只会增加无用的比较成本。这个淘汰不可能成为答案的元素的思想就是单调队列的精髓。初学阶段可以先理解整体目标等自己做几道滑动窗口题后再细品。5. 初学必踩的坑与面试考点速查5.1 初学阶段的高频Bug实录我把这几年看到学生反复犯的错误整理成几类写代码时你可以主动规避混淆top()和pop()有些同学以为pop()会返回栈顶元素于是直接写int x st.pop();编译报错后还不明白原因。记住C的pop()是void需要先top()取值再pop()弹出。在队列里使用back()取队尾却用来修改队头数据逻辑颠倒修出来的数据完全错乱。明确front()是队头、back()是队尾两者只差一个最近入队的元素。迭代遍历中动态改变容器一边用size()做循环上界一边pop()会把遍历范围缩水。直接改用while(!container.empty())这种模式语义更清晰。使用未定义行为例如在空栈/空队列上调用top()、front()、pop()。标准库容器对这些操作的行为未定义可能崩溃也可能返回垃圾数据依赖它等于把命运交给编译器。忘记包含头文件std::stack在stack中std::queue在queue中std::deque在deque中。编译报错时先检查头文件。5.2 面试高频考察点与分析思路校招笔试和面试中栈和队列相关的问题已经形成了固定题库常见的解题方向如下用两个栈实现队列入队时把元素压入stack1出队时若stack2为空则将stack1的所有元素依次弹出并压入stack2再从stack2弹出栈顶。这样stack2的栈顶就是最早入队的元素两个栈模拟出了FIFO效果。均摊复杂度O(1)。用两个队列实现栈入栈时正常入queue1出栈时把queue1除队尾外的所有元素搬到queue2然后弹出queue1中最后一个元素再把queue2的元素搬回queue1。每次出栈需要O(n)操作这是用队列模拟栈绕不开的成本。设计一个能O(1)获取最小值的栈在栈内部额外维护一个最小栈每次push时比较新元素与当前最小值把较小者压入最小栈pop时同步弹出最小栈的栈顶。借助空间换时间的思想。单调栈的经典应用求数组中每个元素左边第一个比它小的元素位置。维护一个栈栈内元素保持单调递增遍历时不断弹出比当前元素大或小的栈顶剩下的栈顶就是答案。这类问题模式化较强刷3~5道题即可掌握套路。这里我建议初学者不要急于背代码而是先用自己的话把上面每个问题的数据结构组合逻辑讲给同学听讲清楚了再动手写。很多面试者就是代码会背但被追问为什么这样设计时卡壳。5.3 调试技巧观察栈和队列的内容而不破坏它们栈和队列不提供迭代器调试时想观察内部数据比较麻烦。最简单的办法是复制拷贝一份临时栈/队列然后不断从临时对象中弹出元素打印。这个方法会额外消耗O(n)的时间与空间但调试场景下完全可接受。void debugPrintStack(std::stackint st) { // 按值传递自动复制 std::cout [栈内元素自顶向下] ; while (!st.empty()) { std::cout st.top() ; st.pop(); } std::cout std::endl; } void debugPrintQueue(std::queueint q) { // 按值传递自动复制 std::cout [队列内元素自队头到队尾] ; while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; }这两个函数的妙处在于按值传递函数内部pop的是副本原始容器不受影响。你可以随时把它加入自己的调试工具集。另一个思路是改用std::vector作为栈的底层容器比如std::stackint, std::vectorint然后想办法拿到那个vector的引用在标准实现中stack的受保护成员c可以被继承访问但初学阶段不必折腾直接用下标遍历。5.4 手写实现还是直接用标准库这个问题我被问过很多次既然标准库有std::stack和std::queue自己手写还有意义吗我的观点很明确学习阶段必须手写工程阶段直接用标准库。学习阶段手写是为了理解栈顶指针随入栈出栈怎么移动、循环队列的容量怎么算、链表节点怎么安全释放。这些细节是编程思维的磨刀石——尤其是循环队列的取模绕回和链表的尾指针维护几乎能锻炼你处理所有边界条件的能力。工程阶段直接用标准库则是因为标准库经过严格的测试和极致的性能调优接口语义清楚可以用最小的成本完成工作。项目里自己维护一个栈/队列实现不仅可能带来Bug和性能问题还会让读你代码的同事感到困惑。当然如果你在实现自带库的嵌入式环境、内存极小的芯片上做开发那么手写一个精简的栈/队列是必要的——到那时你会感谢学习阶段自己认真推演过每一个指针的偏移。我在实际带项目和学习C的过程中最大的体会是栈和队列看似基础但几乎所有复杂系统的角落里都有它们。操作系统内核的任务栈、网络协议栈的报文段、编译器的语法分析栈、线程池的阻塞队列、缓存系统的LRU队列这些高大上的内容拆开底层核心逻辑就是你今天在纸上反复画过的入栈出栈、入队出队。最后再分享一个实用的学习方法学完这部分后建议你做三件事。第一不看任何参考代码自己手写一个栈和一个循环队列并用测试用例包括空容器操作、满容量操作跑通。第二实现括号匹配和用栈实现队列这两道题做完后看别人的题解对比自己在边界处理和代码结构上的差异。第三翻开std::deque的文档弄清楚它和std::vector的区别这能帮你理解标准库为何为stack/queue选择deque作为默认底层容器。搞定这三件事栈和队列这个板块你就真正过关了。
