我上个月排查一个线上服务的崩溃问题时翻了大半天core dump最后靠backtrace的栈回溯才把问题定位到一段深递归调用上——那一刻我突然特别想写一篇关于栈和队列的文章。因为你会发现这两个号称数据结构课第一节课就教的东西真正落到C系统级开发里几乎是无处不在的基石每个线程手里都有一条函数调用栈线程池里躺着的是任务队列网络库的收发缓冲是队列游戏里的撤销操作是栈编译器的表达式求值还是栈。你越往底层走越会意识到这两个最简单的结构恰恰最不可替代。这篇文章适合几类人看一是刚啃完C语法、想认真把数据结构基础过一遍的同学二是从Java或Python转C、需要真正理解STL容器行为的工程师三是在做服务端或嵌入式开发想搞清楚阻塞队列、无锁队列、调用栈回溯这些概念的同行。我会从手写一个栈开始慢慢深入到循环队列、单调栈、无锁队列最后聊几个我在实际调试中踩过的坑。全程不堆概念代码都能直接拿过去用。1. 为什么栈和队列是系统级程序员的地基1.1 函数调用栈与backtrace回溯的原理很多初学者以为栈就是括号匹配用的数据结构或者表达式求值用的这个理解没错但太窄了。实际上每次函数调用都在消耗真实的栈空间CPU会做压栈操作把返回地址、函数参数、局部变量按约定顺序推入栈帧函数返回时再从栈帧弹出来。C里异常抛出时的栈展开stack unwinding本质就是沿着调用栈一层层退出去顺带把沿途栈上对象的析构函数全部执行掉。你平时在日志里看到的一串backtrace就是调试器沿着当前栈指针一级级往上找父栈帧的结果这就是为什么崩溃时backtrace能把谁调用了我、我又调用了谁这条完整链路打印出来。理解了这个之后很多看起来奇怪的现象就有了解释。比如递归函数写得深了会栈溢出而不是堆溢出因为每次递归都消耗一块栈帧空间再比如为什么局部变量很大的数组容易崩因为栈空间就那么几MB你往里面塞一个几十MB的临时数组栈直接越界。栈不仅仅是个理论结构它本身就是操作系统给每个线程分配的一块真实内存。1.2 消息队列、任务队列与线程池的调度逻辑队列在系统里的存在感同样不低。服务器处理请求时不太可能来一个请求就开一个线程那样线程切换开销会先把CPU打满。常规做法是线程池加任务队列生产者把任务丢进队列消费者线程从队列头部取任务执行。网络协议栈的收包缓冲、日志系统的异步写盘、消息中间件的承接底层都是一条队列。为什么非要用队列而不用栈因为生产者和消费者的节奏天然不一样生产者可能一瞬间抛出几十个任务消费者一次只能处理一个这时就需要一个缓冲地带把双方的速率差拉平而队列的先进先出语义刚好保证任务按到达顺序被处理不会出现后到的任务抢跑。我见过不少刚转C服务端的人一遇到流量波动就问要不要上消息队列——但很多场景其实一把带锁的阻塞队列就够了。消息队列解决的是跨进程、跨机器的可靠传输进程内的线程通信用它纯属过度设计。1.3 后进先出与先进先出背后的两种语义如果给这两个结构各贴一个标签栈的关键词是回溯队列的关键词是顺序。栈天然适合所有需要撤销、回退、嵌套处理的场景函数调用的返回、编译器的递归下降解析、浏览器的后退、编辑器的Undo全是后进先出的语义。队列天然适合所有需要排队、缓冲、公平调度的场景任务分发、流量整形、打印任务先进先出保证先来先服务。我的经验是拿到一个需求先别急着选结构问一句最近插入的元素应该最先被处理还是最久远的元素应该最先被处理——答案如果是前者用栈如果是后者用队列。这个判断比背任何性能参数都重要。2. 手写一个栈数组实现与链表实现的真实取舍2.1 数组栈的完整实现与扩容策略栈最常见的实现就是动态数组栈顶放在数组尾部push和pop都是O(1)操作。写一个模板类非常简单template typename T class ArrayStack { private: T* data; int topIndex; int capacity; public: explicit ArrayStack(int cap 16) : capacity(cap), topIndex(-1) { data new T[cap]; } ~ArrayStack() { delete[] data; } void push(const T value) { if (topIndex 1 capacity) { grow(); } data[topIndex] value; } bool pop(T out) { if (isEmpty()) return false; out data[topIndex--]; return true; } bool isEmpty() const { return topIndex -1; } int size() const { return topIndex 1; } private: void grow() { int newCap capacity * 2; T* newData new T[newCap]; for (int i 0; i topIndex; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCap; } };扩容那里我用了最直白的倍增策略。为什么是倍增而不是加固定长度因为倍增可以把均摊复杂度压到O(1)每次扩容后之前N次push都不需要再扩容均摊下来每个元素只承担常数级的拷贝成本。你如果每次只加10个槽位频繁push时扩容成本会被反复摊到你头上整体退化成O(n)。注意这段代码为了教学直观省略了移动语义和异常安全处理实际工程里应该用std::vector托底、用move构造减少拷贝但核心思路就是上面这条。2.2 链表栈的内存模型与局部性链表栈是另一种常见实现思路是头插头删新节点永远挂在头部template typename T class LinkedStack { private: struct Node { T data; Node* next; Node(const T value, Node* nxt nullptr) : data(value), next(nxt) {} }; Node* topNode; int count; public: LinkedStack() : topNode(nullptr), count(0) {} ~LinkedStack() { while (topNode) { Node* tmp topNode; topNode topNode-next; delete tmp; } } void push(const T value) { topNode new Node(value, topNode); count; } bool pop(T out) { if (!topNode) return false; out topNode-data; Node* tmp topNode; topNode topNode-next; delete tmp; --count; return true; } int size() const { return count; } };这段代码同样略去了拷贝构造和赋值操作符但栈的核心语义已经完整了。链表栈的最大优势在于不需要扩容不管塞多少元素每次都只是现new一个节点最大劣势在内存局部性差因为节点分散在堆的各处CPU缓存基本帮不上忙。2.3 数组栈与链表栈的对比选型表我把这两种实现的关键差异整理成了一张表实际选型时照着判断就行维度数组栈链表栈push/pop复杂度O(1) 均摊O(1) 每次内存分配次数扩容时批量分配每次push分配内存局部性连续内存缓存友好节点随机散布缓存差存储密度有预留容量密度略低每节点额外一个指针迭代器稳定性扩容后失效天然稳定适用场景高频读写、性能敏感大小不可控、需节点稳定说实话在C里你几乎不需要手写链表栈std::vector天然就是数组栈的完美底层。但是理解链表栈仍然有价值因为它能帮你理解为什么list在某些场景又慢又不省内存——每个节点多个指针的开销在元素体积小的时候非常致命。3. 队列的进阶循环队列、双端队列到无锁队列3.1 循环队列的判空判满rear与length的设计哲学普通数组队列有个很尴尬的问题队头出队之后front往后移动前面空出来的位置再也用不上物理上还有空间逻辑上却队满了这就是假溢出。循环队列的解决办法是把数组首尾相接rear移动到末尾后绕回开头。经典教科书里判断空和满用的是front rear表示空、(rear 1) % m front表示满后一种会浪费一个槽位因为必须留一个空位区别空和满两种状态。前几年我辅导过一个小伙子他跟我抱怨这块死活想不明白。我说你换一个角度既然是front和length共同描述状态那就别去纠结front和rear的相对位置了直接用元素个数length判断。判空是length 0判满是length m不打架也不用浪费槽位。他一下子就通了。代码是这样的template typename T class CircularQueue { private: T* data; int head; // 队头下标 int tail; // 队尾下标 int count; // 当前元素个数 int capacity; public: explicit CircularQueue(int cap) : capacity(cap), head(0), tail(0), count(0) { data new T[cap]; } ~CircularQueue() { delete[] data; } bool enqueue(const T value) { if (count capacity) return false; // 队满 data[tail] value; tail (tail 1) % capacity; count; return true; } bool dequeue(T out) { if (count 0) return false; // 队空 out data[head]; head (head 1) % capacity; --count; return true; } int size() const { return count; } bool isEmpty() const { return count 0; } };很多数据结构考研题里会直接给以数组q[m]存放循环队列元素同时以rear和length分别指示队尾和元素个数考的就是这套逻辑。length是比一个flag位更稳定的方案它把判空判满统一成了查计数器不需要额外的状态位也天然支持size()查询。3.2 双端队列std::deque的分段连续存储聊完经典循环队列下一个绕不开的是双端队列deque。它允许在头部和尾部都做O(1)的插入删除还能按下标随机访问。很多人以为它是链表和数组的合体其实deque底层是一张中控器map加上一组定长的连续缓冲区整体呈分段连续状态。这意味着它的随机访问虽然能用计算偏移量完成但比vector多一次指针跳转性能略低头尾插删却比vector优越不需要搬移整个数组。C标准库里的std::queue和std::stack默认都以deque为底层容器看中的就是它能头部删、尾部增同时还有不错的局部性。实际问题里如果你需要一个既能从头部取元素、又能从尾部插入元素的结构别犹豫直接上std::deque。比如滑动窗口算法要维护窗口内的最大值就是靠双端队列两头操作实现的这个我后面会展开。3.3 阻塞队列与线程池的队列选型多线程场景下的队列需要加锁保护。一个经典的线程安全阻塞队列模型是互斥锁加两个条件变量生产者在队列满时等待not_full消费者在队列空时等待not_empty#include mutex #include condition_variable #include queue template typename T class BlockingQueue { private: std::mutex mtx; std::condition_variable notFull; std::condition_variable notEmpty; std::queueT data; size_t capacity; public: explicit BlockingQueue(size_t cap) : capacity(cap) {} void push(const T value) { std::unique_lockstd::mutex lock(mtx); notFull.wait(lock, [this] { return data.size() capacity; }); data.push(value); notEmpty.notify_one(); } void pop(T out) { std::unique_lockstd::mutex lock(mtx); notEmpty.wait(lock, [this] { return !data.empty(); }); out data.front(); data.pop(); notFull.notify_one(); } };构造的时候一定要用带容量的有界队列这是我踩过跟头的地方。无界队列看起来省心——永远能往里丢东西可一旦生产者速率长期高于消费者内存会被无限制地吃掉服务直接OOM。有界队列配上一个饱和策略阻塞、丢弃、拒绝新任务才是线上服务的正确玩法。线程池的队列选型同理追求公平就选FIFO队列追求优先级就选优先队列但无论如何请给队列一个上限。3.4 从原子操作到无锁SPSC队列锁是好东西但高并发下锁竞争会让线程等着干瞪眼。单生产者单消费者SPSC场景下有一种非常经典的无锁队列环形缓冲区加两个原子索引。生产者和消费者各写各的索引用原子操作避免数据竞争#include atomic #include vector template typename T, size_t N class SPSCQueue { static_assert((N (N - 1)) 0, N must be power of 2); std::vectorT buffer; std::atomicsize_t head{0}; // 消费者读位置 std::atomicsize_t tail{0}; // 生产者写位置 const size_t mask N - 1; public: explicit SPSCQueue() : buffer(N) {} bool push(const T val) { size_t t tail.load(std::memory_order_relaxed); size_t h head.load(std::memory_order_acquire); if (t - h N) return false; // 队满 buffer[t mask] val; tail.store(t 1, std::memory_order_release); return true; } bool pop(T out) { size_t h head.load(std::memory_order_relaxed); size_t t tail.load(std::memory_order_acquire); if (h t) return false; // 队空 out buffer[h mask]; head.store(h 1, std::memory_order_release); return true; } };注意原子变量两个方向的读生产者push时用acquire读head保证能看到消费者release写入的head更新避免覆盖还没被消费的元素消费者pop时用acquire读tail保证能看到生产者release写入的数据内容。这里的内存序安排是SPSC无锁队列不出错的根本我早年图省事全部memory_order_relaxed跑release模式直接读到未初始化的脏数据。需要清醒认识到无锁队列只是解决了锁竞争的一个侧面它并没有比阻塞队列更正确。一旦场景变成多生产者多消费者SPSC这套模型会立刻失效需要引入更复杂的CAS机制还会面临ABA问题这个我放到最后一章细说。4. 四个高频实战场景从括号匹配到任务调度4.1 括号匹配与表达式求值调度场算法括号匹配是栈最经典的入门应用。思路很朴素遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配则弹栈不匹配或者栈为空就直接判定非法bool isValid(const std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; } st.pop(); } } return st.empty(); }这套就近匹配的逻辑在编译器里处处可见。再进一步表达式求值用到了调度场算法把中缀表达式转成后缀表达式逆波兰式转换过程中操作符的暂存用的还是栈int precedence(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } std::vectorstd::string toRPN(const std::string expr) { std::stackchar ops; std::vectorstd::string out; std::string num; for (char c : expr) { if (isdigit(c)) { num c; } else { if (!num.empty()) { out.push_back(num); num.clear(); } if (c () { ops.push(c); } else if (c )) { while (!ops.empty() ops.top() ! () { out.push_back(std::string(1, ops.top())); ops.pop(); } ops.pop(); // 弹出左括号 } else { while (!ops.empty() precedence(ops.top()) precedence(c)) { out.push_back(std::string(1, ops.top())); ops.pop(); } ops.push(c); } } } if (!num.empty()) out.push_back(num); while (!ops.empty()) { out.push_back(std::string(1, ops.top())); ops.pop(); } return out; }拿到后缀表达式后再算值就简单了遇到数字压栈遇到操作符弹两个数计算后压回。你看编译器实现一个简易计算器的整个过程栈从头到尾都在出力。括号匹配、操作符优先级、求值顺序三个问题一个栈全搞定。4.2 单调栈找右边第一个更大元素的O(n)解法单调栈是栈的进阶玩法核心是栈内元素保持单调性通常用于解决下一个更大/更小元素问题。经典题目是给一个数组求每个元素右边第一个比它大的数。暴力法是两层循环O(n²)单调栈可以把复杂度降到O(n)std::vectorint nextGreater(const std::vectorint nums) { std::vectorint ans(nums.size(), -1); std::stackint st; // 存下标 for (int i 0; i (int)nums.size(); i) { while (!st.empty() nums[st.top()] nums[i]) { ans[st.top()] nums[i]; st.pop(); } st.push(i); } return ans; }逻辑是栈内下标对应的元素从栈底到栈顶严格递减遍历到新元素时把所有比它小的栈顶逐一弹出弹出时它的下一个更大元素就是当前这个元素。这个思路在柱状图最大矩形、接雨水这类问题里也是核心面试中出现的频率极高。记住一句话单调栈把对每个元素向后找满足条件的元素这个二维搜索问题压缩成了一趟线性的先进后出过程。4.3 用队列实现生产者消费者与消息缓冲队列在任务调度里的角色前面说线程池时提过。这里给一个更具体的画面一个爬虫程序生产者线程不断从种子列表里取URL发起下载下载完的内容塞进队列消费者线程从队列取内容做解析和入库。队列就是生产者和消费者之间的缓冲地带。如果生产和消费速率不均衡队列就是那个蓄水池。但注意队列只是保证消息传递的顺序不保证消息被成功处理。所谓消息队列重复消费问题本质上是至少一次投递语义带来的副作用——消费者处理完但没来得及提交offset下次就重复收到了。解决方式是业务侧做幂等消费端记录已处理的消息ID或状态位而不是在队列层面强行追求只消费一次。这个原则放到任何消息系统里都适用。4.4 双端队列在滑动窗口算法中的应用再看一个双端队列的实际案例滑动窗口最大值。给定一个数组窗口每次右移一格求每个窗口内的最大值。暴力法是每格扫一遍窗口O(nk)用deque维护一个从队头到队尾递减的候选下标队列可以做到O(n)std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { std::dequeint dq; // 存下标对应元素从队头到队尾递减 std::vectorint ans; for (int i 0; i (int)nums.size(); i) { if (!dq.empty() dq.front() i - k) dq.pop_front(); while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); dq.push_back(i); if (i k - 1) ans.push_back(nums[dq.front()]); } return ans; }为什么从队尾弹掉那些比当前元素小的老元素因为它们既不比当前元素大又比当前元素先出窗口永远不可能成为后续窗口的最大值留着纯属浪费。deque的头尾双操作在这里缺一不可队尾作为入口淘汰旧候选队头作为出口提供当前窗口最大值。5. STL里的栈与队列适配器本质、容器选型与性能陷阱5.1 stack与queue为什么是容器适配器很多初学者有一个误区认为std::stack和std::queue是独立容器。实际上它们被称为容器适配器——本身不存数据只是在一个底层容器的基础上把接口收窄成栈或队列的语义。定义大概是templateclass T, class Container std::dequeT class stack { /* 底层是Container对外只暴露push/pop/top等接口 */ }; templateclass T, class Container std::dequeT class queue { /* 底层是Container对外只暴露push/pop/front等接口 */ };你可以通过第二个模板参数指定底层容器。比如stack想用vector做底层可以写std::stackint, std::vector queue需要头部删除不能直接用vector可以换std::list但默认的deque通常是综合最优解——因为它支持头尾O(1)插入删除随机访问虽然慢于vector但比list强太多内存局部性也过得去。这个设计给我们的启发是栈和队列不是新东西而是对已有容器做接口约束。理解到这一层你就不会纠结std::stack到底是不是容器这种问题了。5.2 vector、deque、list做底层的性能差异为了选对底层容器我把三者的关键性能指标列出来做了个对比特性vectordequelist头部插入O(n) 搬移O(1) 摊销O(1)尾部插入O(1) 摊销O(1) 摊销O(1)随机访问O(1)O(1) 多一次跳转O(n)内存分布连续分段连续散布中间插入O(n)O(n)O(1) 已知位置迭代器失效扩容后全失效两端插入不失效中间插入失效仅被删除节点失效C实践里我基本遵循这几条规则默认容器用vector需要在头部频繁增删选deque需要稳定的节点引用、不介意随机访问性能时才选list。很多从Java转过来的人习惯性用list理由是插入快但忽略了一个残酷事实——list每次增删都要分配节点内存加上糟糕的缓存局部性在小对象场景下性能往往是被vector碾压的。5.3 三个与容器选型相关的常见坑第一个坑是栈用vector做底层却忘了reserve。std::vector自带倍增扩容没错但如果你要连续push十万个元素中间会触发多次扩容和数据搬移性能肉眼可见地下降。提前reserve一下内存只分配一次CPU缓存命中率也高。第二个坑是deque的迭代器失效规则和人们直觉不一样。在deque中间插入元素会令所有迭代器失效但在两端插入则通常不影响已有元素的迭代器引用只是迭代器本身可能失效。很多人在deque上跑一个双端操作循环边遍历边push写着写着迭代器就野了这就是没记住这套规则。第三个坑是我反复见的——用list存小对象。假设你存一个int组成的list每个节点除了int还要多存两个指针32字节的节点只为装4字节的数据内存膨胀四倍起。更糟的是访问时节点地址分散cache miss率感人。真正适合list的是那些需要稳定地址引用、元素移动代价高的场景比如要长期持有一个对象的指针不因容器扩容而失效。6. 实战调试笔记栈溢出、假溢出与无锁队列的坑6.1 递归栈溢出的定位与处理写递归爽是真的爽爆栈也是真的容易。Linux下线程栈默认8MBWindows下默认1MB写一个不小心就会越界。我遇到过一个真实案例线上接口处理树形数据结构树的深度一深递归函数直接段错误日志里只有一句Segmentation fault最后是gdb挂上去看backtrace才看到的爆栈位置。处理办法无非三条一是把递归改成显式栈的循环自己用std::stack管理待处理节点代码啰嗦一点但栈空间可控二是利用尾递归优化把递归调用放到函数最后一步让编译器有机会把它优化成循环但C不保证一定优化别太指望三是干脆把栈空间调大用ulimit -s或者链接选项实现但这是治标不治本递归深度不可控时迟早再踩一次。我自己做开发的原则很简单凡是深度不确定的递归遍历文件系统、解析深层JSON、处理链表环一律不用原生递归全部改成显式栈或者迭代。面试聊起来是数据结构题线上跑起来就是系统稳定性问题。6.2 普通数组队列的假溢出现象前面提到过假溢出这里重复一次是因为我见过太多人在这个问题上栽跟头。普通数组队列是头尾都往前走的状态每出队一次front数组前面的位置就空出来了但入队时tail照样往后走直到tail走到数组末尾明明前面空着一大片程序却报队满这就是假溢出。解决思路有两个方向一是每出队一次就把剩余元素整体前移换来的是O(n)的搬移开销二是把数组首尾相接做成循环队列用取模运算让tail绕回开头配上一开始提到的length计数判满判空。我强烈建议直接用循环队列因为整体前移的方案在元素多、操作频繁时性能不堪入目而循环队列的实现成本也就是一个取模运算。6.3 无锁队列的ABA问题与内存序陷阱继续说无锁队列的高阶问题。CAS比较并交换是无锁编程的核心原语但CAS有一个著名的坑叫ABA问题线程A读到一个指针值X线程B把指针改成Y又改回X线程A的CAS比较时发现值还是X认为没人动过于是继续操作实际上这个内存已经被复用甚至改写了。解决ABA的常见思路是给指针加上一个版本号计数器CAS比较指针加版本号这个复合值版本号每次修改都递增即使指针值回到X版本号也回不去问题自然暴露了。另一种做法是延迟回收为了保证一个节点在CAS失败期间不会被真的释放用带有引用计数的内存管理或hazard pointer。这些方案都需要非常深的心智模型才能写对我的建议是除非你确认自己是这个领域的专家否则无锁队列用于生产环境要极度谨慎。与此同时无锁队列还要求严谨的内存序配合。早期我图方便在原子操作上全部用memory_order_seq_cst性能差后来为了性能改用relaxed又出脏数据问题。只有真正理解了生产者写入数据必须release消费者读到数据必须acquire这一对内存序协议无锁队列才算真正写对。SPSC场景下我上面给的队列代码就够了多生产者多消费者的场景优先考虑有界阻塞队列配锁别拿生产环境开玩笑。6.4 阻塞队列死锁与条件变量唤醒丢失最后一个坑来自阻塞队列的实现细节条件变量配合互斥锁使用时等待条件必须放在while循环里不能是if。比如pop操作的等待条件写成while (data.empty())就算被notify唤醒也要再检查一次条件是否成立。原因是条件变量存在伪唤醒和唤醒丢失两种问题系统可能毫无理由地唤醒一个等待线程另一个线程可能刚好在notify和wait之间争锁先把队列里的元素抢走了。如果写的是if被唤醒后的线程就会在队列依旧为空的情况下去取数据读到未定义行为。另外多条件变量时notify和wait的顺序也要小心生产者先持锁判断队满不满则入队并notify消费者消费者持锁判断队空不空则出队并notify生产者。同一把锁保护两个条件变量时务必用while等条件再操作配合unique_lock在wait时释放锁、唤醒后重新拿锁这一套下来死锁和饥饿的隐患才能压到最低。最后分享一个我自己排查问题时的习惯凡是涉及栈和队列的线上故障先问三个问题——数据是先进先出还是后进先出边界条件判空判满有没有覆盖并发访问有没有正确加锁或使用原子操作大多数坑其实都出在这三个问题上。栈和队列入门门槛低但它们背后的工程复杂度一点也不低把这些基础结构吃透后续看调度器、看网络库、看消息中间件都会轻松不止一个量级。