栈与队列：从底层实现到工程实战的深度解析

栈和队列大概是每个写代码的人最早接触、也最容易被轻视的两个数据结构。我见过不少工作三五年的开发者，聊起红黑树、跳表、线段树头头是道，但让他手写一个没有bug的循环队列，或者解释清楚为什么函数调用要用栈而不是队列，反而会卡壳。问题不在于他们不懂，而在于当年学的时候只记住了"先进先出"和"后进先出"这两句口诀，没真正把这两个结构放进具体的场景里去理解。这篇内容我想做的事情很直接：把栈和队列从抽象定义一路拉到能跑起来的代码，再拉到真实工程里它们各自扮演的角色，中间穿插我自己踩过的坑和调试经验。不管你是刚学数据结构的学生，还是想回头补基础的开发者，应该都能从中拿到点能直接用的东西。

1. 为什么栈和队列值得单独拿出来讲

1.1 它们不是"简单结构"，而是两种受限的线性表

很多人对栈和队列的第一印象是"这不就是数组加两个限制吗，有什么好讲的"。这个印象本身没错，栈和队列确实都是操作受限的线性表——栈只允许在一端插入和删除，队列只允许在一端插入、另一端删除。但恰恰是这种"受限"，让它们在某些场景下比通用数组和链表更好用。

打个比方，数组像是一个什么都能装的抽屉，你可以从任何位置拿东西放东西；栈像是一摞盘子，你只能从最上面拿、往最上面放；队列像是排队买票，先来的先买，后来的排在后面。抽屉当然更灵活，但当你明确知道自己只需要"从顶部操作"或者"按顺序处理"时，用抽屉反而容易出错——你会忍不住从中间抽一个出来，然后整个逻辑就乱了。

受限带来的好处是接口语义清晰。一个函数接收一个栈作为参数，调用者立刻知道这个函数只会对栈顶做操作，不会去翻中间的元素。这种约束在多人协作的代码库里价值极高，它把"能做什么"和"不该做什么"用类型系统直接表达出来了。

1.2 从调用栈到消息队列：它们藏在系统的每个角落

栈和队列真正有意思的地方在于，它们不是课本里的练习题，而是现代软件系统的基础设施。

先说栈。你写的每一个递归函数，背后都是调用栈在支撑。每次函数调用，系统会把返回地址、参数、局部变量打包成一个栈帧压入调用栈，函数返回时弹出。递归太深导致栈溢出，本质就是这个栈被压爆了。浏览器的前进后退、编辑器的撤销重做、表达式求值、括号匹配，全都是栈的经典应用。

再说队列。操作系统的进程调度、打印机的任务排队、消息中间件的消息投递、广度优先搜索的层序遍历，背后都是队列。生产者消费者模型里，队列是解耦生产速度和消费速度的缓冲区。你用的线程池，任务队列就是一个阻塞队列。

我个人的体会是，理解这两个结构的关键不在于记住它们的定义，而在于建立"什么场景该用哪个"的直觉。这个直觉一旦建立起来，很多设计问题会变得非常清晰。

1.3 本文的实践路线

接下来我会按这样的顺序展开：先把栈和队列的底层实现方式讲透，包括数组实现和链表实现的取舍；然后分别深入栈和队列的典型应用场景，每个场景都给出可运行的代码；再讲几个我在实际项目中踩过的坑，比如循环队列的判空判满、栈溢出的排查；最后聊一聊进阶话题，比如单调栈、双端队列这些变体。代码我会用Python和C两种语言对照着写，Python方便理解逻辑，C方便看清内存层面的细节。

2. 栈的底层实现：数组和链表到底怎么选

2.1 顺序栈：用数组模拟一摞盘子

顺序栈的思路非常朴素：开一块连续内存，用一个变量top记录栈顶位置。入栈就是top加一然后写入，出栈就是读取top位置然后减一。

用Python写一个最小可用的顺序栈：

class ArrayStack: def __init__(self, capacity=10): self._data = [None] * capacity self._top = -1 # 栈顶指针，-1表示空栈 self._capacity = capacity def push(self, value): if self._top == self._capacity - 1: self._resize(2 * self._capacity) self._top += 1 self._data[self._top] = value def pop(self): if self.is_empty(): raise IndexError("pop from empty stack") value = self._data[self._top] self._data[self._top] = None # 帮助GC self._top -= 1 return value def peek(self): if self.is_empty(): raise IndexError("peek from empty stack") return self._data[self._top] def is_empty(self): return self._top == -1 def _resize(self, new_capacity): new_data = [None] * new_capacity for i in range(self._top + 1): new_data[i] = self._data[i] self._data = new_data self._capacity = new_capacity

这里有几个细节值得说。第一，_top初始化为-1而不是0，这样is_empty判断就是top == -1，逻辑最干净。第二，出栈时把原位置置为None，这是为了帮助垃圾回收——如果存的是大对象，不置空的话这块内存会一直被引用着。第三，扩容采用翻倍策略，这样均摊下来每次push是O(1)的。

用C写的话，内存管理要自己来：

typedef struct { int *data; int top; int capacity; } ArrayStack; ArrayStack* stack_create(int capacity) { ArrayStack *s = malloc(sizeof(ArrayStack)); s->data = malloc(sizeof(int) * capacity); s->top = -1; s->capacity = capacity; return s; } void stack_push(ArrayStack *s, int value) { if (s->top == s->capacity - 1) { s->capacity *= 2; s->data = realloc(s->data, sizeof(int) * s->capacity); } s->data[++s->top] = value; } int stack_pop(ArrayStack *s) { if (s->top == -1) { fprintf(stderr, "pop from empty stack\n"); exit(1); } return s->data[s->top--]; }

C版本里realloc可能失败返回NULL，生产代码里必须检查，我这里为了简洁省略了。这是新手很容易忽略的点——realloc失败时原指针还有效，直接覆盖会导致内存泄漏。

2.2 链栈：没有容量上限的代价

链栈用单链表实现，栈顶就是链表头。入栈是头插法，出栈是删除头节点。好处是没有扩容问题，坏处是每个节点多一个指针的开销，而且内存不连续，缓存命中率低。

class Node: __slots__ = ('value', 'next') def __init__(self, value, next=None): self.value = value self.next = next class LinkedStack: def __init__(self): self._head = None self._size = 0 def push(self, value): self._head = Node(value, self._head) self._size += 1 def pop(self): if self._head is None: raise IndexError("pop from empty stack") value = self._head.value self._head = self._head.next self._size -= 1 return value

__slots__是我加的一个小优化，它告诉Python这个类不需要__dict__，能省下不少内存。如果你要存几百万个节点，这个优化效果很明显。

2.3 两种实现的取舍：别只看时间复杂度

很多人选实现方式只看时间复杂度，觉得两者push/pop都是O(1)，随便选。实际上工程里要考虑的东西多得多。

维度	顺序栈	链栈
单次push最坏	O(n)（扩容时）	O(1)
均摊push	O(1)	O(1)
内存开销	可能有预留浪费	每节点多一个指针
缓存友好度	高（连续内存）	低（指针跳转）
容量上限	受内存限制但需扩容	理论上无上限
实现复杂度	需处理扩容	简单

我的经验是：如果你能预估栈的最大深度，优先用顺序栈。连续内存带来的缓存优势在现代CPU上非常明显，实测下来同样的操作顺序栈往往比链栈快2到3倍。只有当栈深度完全不可预测、且可能非常大时，才考虑链栈。

注意：顺序栈扩容时如果一次性申请了很大的新数组，可能触发内存分配失败。在嵌入式等内存受限环境里，宁可一开始就分配固定大小，也不要动态扩容。

3. 队列的实现：循环队列是绕不过去的坎

3.1 朴素数组队列的致命缺陷

用数组实现队列，最直觉的做法是：用一个front指向队头，一个rear指向队尾。入队时rear后移，出队时front后移。

问题很快就来了：随着不断入队出队，front和rear都只增不减，前面的空间被出队释放了却无法复用，最后rear撞到数组末尾，明明前面还有空位却报"队列满"。这就是所谓的假溢出。

解决办法就是循环队列：把数组看成一个环，rear到末尾后绕回开头。但绕回之后，判空和判满就冲突了——front == rear既可能是空也可能是满。

3.2 循环队列判空判满的三种方案

这个问题我被面试问过，也在实际代码里写错过。三种主流方案：

方案一：牺牲一个存储单元。规定rear的下一个位置是front时就算满，这样队列最多存capacity - 1个元素。判空是front == rear，判满是(rear + 1) % capacity == front。这个方案最简单，我平时用得最多。

方案二：加一个size变量。记录当前元素个数，判空是size == 0，判满是size == capacity。逻辑最清晰，代价是多维护一个变量。

方案三：加一个标志位。记录上一次操作是入队还是出队，据此区分空和满。这个方案最省空间，但逻辑最绕，容易写错。

我用方案一写一个完整的循环队列：

class CircularQueue: def __init__(self, capacity): if capacity < 1: raise ValueError("capacity must be >= 1") self._data = [None] * (capacity + 1) # 多开一个单元 self._front = 0 self._rear = 0 self._capacity = capacity + 1 def enqueue(self, value): if self.is_full(): raise OverflowError("queue is full") self._data[self._rear] = value self._rear = (self._rear + 1) % self._capacity def dequeue(self): if self.is_empty(): raise IndexError("dequeue from empty queue") value = self._data[self._front] self._data[self._front] = None self._front = (self._front + 1) % self._capacity return value def is_empty(self): return self._front == self._rear def is_full(self): return (self._rear + 1) % self._capacity == self._front def size(self): return (self._rear - self._front + self._capacity) % self._capacity

注意size的计算，(rear - front + capacity) % capacity这个公式在rear < front时也能正确工作，因为加了capacity保证结果为正。

3.3 链式队列：头尾双指针的配合

链式队列需要同时维护队头指针和队尾指针。入队在尾部追加，出队在头部删除。这里有个容易出错的边界：当队列中只有一个元素时出队，必须同时把队尾指针置空，否则队尾会指向一个已经被释放的节点。

class LinkedQueue: def __init__(self): self._head = None self._tail = None self._size = 0 def enqueue(self, value): node = Node(value) if self._tail is None: self._head = self._tail = node else: self._tail.next = node self._tail = node self._size += 1 def dequeue(self): if self._head is None: raise IndexError("dequeue from empty queue") value = self._head.value self._head = self._head.next if self._head is None: # 队列变空，tail也要置空 self._tail = None self._size -= 1 return value

这个if self._head is None: self._tail = None就是那个经典边界，我当年写的时候漏过，结果队列空了之后tail还指着旧节点，下次入队就出问题了。

3.4 双端队列：两端都能进出的结构

双端队列（deque）允许在两端插入和删除，是栈和队列的超集。Python的collections.deque就是双端队列，底层是分块的双向链表，两端操作都是O(1)。如果你需要频繁在两端操作，直接用deque比自己写数组实现要快得多。

from collections import deque dq = deque() dq.append(1) # 右端入 dq.appendleft(2) # 左端入 dq.pop() # 右端出 dq.popleft() # 左端出

deque的maxlen参数很有意思，设置之后队列满了会自动从另一端丢弃元素，实现固定窗口非常方便：

recent = deque(maxlen=5) for i in range(10): recent.append(i) print(list(recent)) # [5, 6, 7, 8, 9]

4. 栈的实战场景：从括号匹配到表达式求值

4.1 括号匹配：栈的入门级应用

括号匹配是栈最经典的应用，思路是：遇到左括号入栈，遇到右括号检查栈顶是否是对应的左括号，是就弹出，不是就说明不匹配。遍历结束后栈为空才算匹配。

def is_balanced(s): pairs = {')': '(', ']': '[', '}': '{'} stack = [] for ch in s: if ch in '([{': stack.append(ch) elif ch in ')]}': if not stack or stack[-1] != pairs[ch]: return False stack.pop() return len(stack) == 0

这个代码看起来简单，但有个细节：遇到右括号时，必须先检查栈是否为空。如果输入是")"，栈是空的，直接访问stack[-1]会出错。我见过不少人在这个点上翻车。

4.2 表达式求值：中缀转后缀再求值

表达式求值是栈的进阶应用，分两步：先把中缀表达式（就是我们平时写的3 + 4 * 2）转成后缀表达式（也叫逆波兰表达式，3 4 2 * +），再对后缀表达式求值。

中缀转后缀用到一个运算符栈，规则是：遇到数字直接输出；遇到运算符时，把栈中优先级大于等于当前运算符的都弹出输出，然后当前运算符入栈；遇到左括号直接入栈；遇到右括号则弹出直到左括号。

def infix_to_postfix(tokens): precedence = {'+': 1, '-': 1, '*': 2, '/': 2} output = [] op_stack = [] for token in tokens: if token.isdigit(): output.append(token) elif token == '(': op_stack.append(token) elif token == ')': while op_stack and op_stack[-1] != '(': output.append(op_stack.pop()) op_stack.pop() # 弹出左括号 else: while (op_stack and op_stack[-1] != '(' and precedence[op_stack[-1]] >= precedence[token]): output.append(op_stack.pop()) op_stack.append(token) while op_stack: output.append(op_stack.pop()) return output

后缀表达式求值更简单：遇到数字入栈，遇到运算符就弹出两个操作数计算，结果再入栈。

def eval_postfix(tokens): stack = [] for token in tokens: if token.isdigit(): stack.append(int(token)) else: b = stack.pop() a = stack.pop() if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) elif token == '/': stack.append(a // b) return stack[0]

注意：后缀求值时先弹出的是右操作数，后弹出的是左操作数。减法和除法不满足交换律，顺序搞反结果就错了。这个坑我踩过不止一次。

4.3 用两个栈实现队列

这是一个经典的设计题，思路是：一个栈负责入队（in_stack），一个栈负责出队（out_stack）。入队时直接压入in_stack；出队时如果out_stack为空，就把in_stack的所有元素依次弹出压入out_stack，然后从out_stack弹出。

class QueueWithTwoStacks: def __init__(self): self._in = [] self._out = [] def enqueue(self, value): self._in.append(value) def dequeue(self): if not self._out: while self._in: self._out.append(self._in.pop()) if not self._out: raise IndexError("dequeue from empty queue") return self._out.pop()

这个实现的关键在于只有out_stack为空时才搬运，这样每个元素最多被搬运一次，均摊时间复杂度是O(1)。如果每次出队都搬运，复杂度就退化成O(n)了。

4.4 单调栈：解决"下一个更大元素"的利器

单调栈是栈的一个变体，栈内元素保持单调递增或递减。它专门用来解决"找下一个更大/更小元素"这类问题。

以"下一个更大元素"为例：给定数组，对每个元素找它右边第一个比它大的元素。暴力解法是O(n²)，单调栈能做到O(n)。

def next_greater(nums): n = len(nums) result = [-1] * n stack = [] # 存下标，对应值单调递减 for i in range(n): while stack and nums[stack[-1]] < nums[i]: idx = stack.pop() result[idx] = nums[i] stack.append(i) return result

核心逻辑是：栈里存的是还没找到更大元素的那些下标，且它们的值从栈底到栈顶单调递减。当遇到一个更大的数时，它就是这个数右边第一个更大的，可以弹出并记录。

单调栈的题目有个共同特征：一旦你识别出"找左右两边第一个比当前大/小的元素"，就应该立刻想到它。我做过统计，力扣上单调栈相关的题目大概有二十多道，套路高度一致。

5. 队列的实战场景：从BFS到任务调度

5.1 广度优先搜索：队列的主场

BFS是队列最经典的应用。它的核心是：从起点开始，先把起点入队，然后不断出队一个节点，把它的未访问邻居入队，直到队列为空。

from collections import deque def bfs(graph, start): visited = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order

BFS和DFS的区别就在于是用队列还是用栈。用队列是层序遍历，用栈是深度优先。这个对比很能说明两个结构的本质差异。

BFS的一个重要性质是第一次访问到某个节点时，走的就是最短路径（在无权图里）。这个性质让BFS成为最短路径问题的基础。如果你在BFS里记录每个节点的层数，就能直接得到最短距离。

5.2 滑动窗口最大值：单调队列的舞台

单调队列是队列的变体，队列内元素保持单调。它最经典的应用是滑动窗口最大值：给定数组和窗口大小k，求每个窗口的最大值。

暴力解法是每个窗口扫一遍，O(nk)。单调队列能做到O(n)。

from collections import deque def max_sliding_window(nums, k): dq = deque() # 存下标，对应值单调递减 result = [] for i, num in enumerate(nums): # 移除超出窗口的 while dq and dq[0] <= i - k: dq.popleft() # 移除比当前小的，它们不可能是最大值了 while dq and nums[dq[-1]] < num: dq.pop() dq.append(i) # 窗口形成后记录结果 if i >= k - 1: result.append(nums[dq[0]]) return result

这个算法的精髓在于：如果一个元素比它右边的新元素小，那它在有生之年都不可能成为最大值了，可以直接从队尾踢掉。这样队列里始终保持递减，队头就是当前窗口最大值。

我第一次看这个算法的时候觉得很妙，但自己写的时候在"移除超出窗口"和"移除更小元素"的顺序上纠结了很久。实测下来，先处理窗口越界再处理单调性是对的，反过来在某些边界情况下会出错。

5.3 生产者消费者模型：队列作为缓冲区

在多线程编程里，队列是解耦生产者和消费者的标准工具。生产者往队列里放任务，消费者从队列里取任务，两者速度不一致时队列起到缓冲作用。

Python的queue.Queue是线程安全的，直接拿来用：

import queue import threading import time def producer(q, n): for i in range(n): q.put(i) print(f"produced {i}") time.sleep(0.1) def consumer(q): while True: item = q.get() if item is None: # 毒丸信号 break print(f"consumed {item}") q.task_done() q = queue.Queue(maxsize=5) t1 = threading.Thread(target=producer, args=(q, 10)) t2 = threading.Thread(target=consumer, args=(q,)) t1.start(); t2.start() t1.join() q.put(None) # 通知消费者结束 t2.join()

这里用了一个"毒丸"技巧：生产者结束后往队列里放一个特殊值，消费者读到它就退出。这是多线程编程里终止消费者的常见做法。

maxsize=5限制了队列大小，当队列满时put会阻塞，这就是所谓的有界队列。有界队列能防止生产过快导致内存爆掉，是生产环境的标配。无界队列在流量突增时可能把内存吃光，我见过因为这个导致服务OOM的案例。

5.4 用两个队列实现栈

和"两个栈实现队列"对称，用两个队列也能实现栈。思路是：入栈时把元素放入非空队列；出栈时把非空队列的前n-1个元素搬到另一个空队列，剩下的那个就是栈顶。

class StackWithTwoQueues: def __init__(self): self._q1 = deque() self._q2 = deque() def push(self, value): if self._q1: self._q1.append(value) else: self._q2.append(value) def pop(self): src = self._q1 if self._q1 else self._q2 dst = self._q2 if self._q1 else self._q1 if not src: raise IndexError("pop from empty stack") while len(src) > 1: dst.append(src.popleft()) return src.popleft()

这个实现出栈是O(n)的，比两个栈实现队列的均摊O(1)要差。所以实际工程里没人这么干，它更多是面试题。但它能帮你理解两个结构的对称性。

6. 那些年我踩过的坑和排查经验

6.1 循环队列的判满条件写反

我最早写循环队列时，判满条件写成了(front + 1) % capacity == rear，结果队列一满就报错，但明明还有空间。排查了半天才发现是front和rear写反了。

正确的判满应该是(rear + 1) % capacity == front，意思是"队尾的下一个位置如果追上了队头，就满了"。这个方向感很重要：rear在追front，追上了就满。

我的建议是，写循环队列时画个图，标出front和rear的位置，然后手动模拟几次入队出队，确认判空判满条件。别嫌麻烦，这个结构一旦写错，bug往往很隐蔽。

6.2 栈溢出：递归太深的代价

栈溢出是另一个常见问题。Python默认递归深度是1000，超过就抛RecursionError。C语言里栈溢出更危险，直接段错误。

我遇到过一次线上事故，一个递归解析JSON的函数，遇到特别深的嵌套结构时栈溢出，整个服务挂掉。后来改成了显式用栈的迭代版本：

def parse_iterative(tokens): stack = [] for token in tokens: if token == '[': stack.append([]) elif token == ']': completed = stack.pop() if stack: stack[-1].append(completed) else: return completed else: stack[-1].append(token)

这个教训是：递归能解决的问题，迭代基本都能解决。当数据规模不可控时，优先考虑迭代版本，把栈放到堆上，避免调用栈溢出。

6.3 队列满了之后的行为选择

队列满了怎么办？这个问题没有标准答案，取决于业务场景。常见策略有：

策略	行为	适用场景
阻塞	等待直到有空位	生产者消费者，允许背压
抛异常	立即报错	不能丢数据，需要调用方处理
丢弃最新	拒绝新元素	实时性要求高，旧数据更重要
丢弃最旧	挤掉队头	只关心最近数据，如监控指标

我在做日志采集时用过"丢弃最旧"策略，因为日志量太大，只保留最近的。但在做订单处理时用的是"阻塞"，因为订单不能丢。

提示：选择队列满的策略时，先问自己一个问题——"丢一条数据，业务能接受吗？"能接受就丢弃，不能接受就阻塞或抛异常。

6.4 多线程下队列的线程安全问题

自己实现的队列默认不是线程安全的。多线程环境下，enqueue和dequeue可能同时修改front和rear，导致数据错乱。

Python里因为GIL的存在，简单的整数操作是原子的，但复合操作（比如先判断再修改）不是。所以要么用queue.Queue，要么自己加锁：

import threading class ThreadSafeQueue: def __init__(self, capacity): self._queue = deque() self._capacity = capacity self._lock = threading.Lock() self._not_empty = threading.Condition(self._lock) self._not_full = threading.Condition(self._lock) def enqueue(self, value): with self._not_full: while len(self._queue) >= self._capacity: self._not_full.wait() self._queue.append(value) self._not_empty.notify() def dequeue(self): with self._not_empty: while not self._queue: self._not_empty.wait() value = self._queue.popleft() self._not_full.notify() return value

这里用了两个条件变量，一个管"非空"，一个管"非满"。用while而不是if判断条件，是为了防止虚假唤醒。这个细节很多人会忽略，但在高并发下可能导致bug。

7. 进阶话题：从基础结构到算法武器

7.1 单调栈和单调队列的识别套路

单调栈和单调队列是基础结构的进阶用法，它们的共同点是在普通栈/队列的基础上维护单调性。识别它们的关键是看问题里有没有"下一个更大/更小"或者"窗口内最值"这类字眼。

我总结了一个简单的判断流程：如果问题是"找每个元素左边/右边第一个比它大/小的元素"，用单调栈；如果问题是"求每个固定大小窗口内的最值"，用单调队列。这两个套路覆盖了大部分相关题目。

7.2 优先队列：队列的排序版本

优先队列不是简单的先进先出，而是每次出队优先级最高的元素。它通常用堆实现，插入和删除都是O(log n)。Python的heapq模块提供了堆操作：

import heapq pq = [] heapq.heappush(pq, (3, 'task3')) heapq.heappush(pq, (1, 'task1')) heapq.heappush(pq, (2, 'task2')) while pq: priority, task = heapq.heappop(pq) print(priority, task) # 1 task1, 2 task2, 3 task3

优先队列在任务调度、Dijkstra算法、Top K问题里都有应用。它和普通队列的区别在于出队顺序由优先级决定，而不是入队顺序。

7.3 用栈实现表达式树

表达式树是表达式求值的另一种思路：把中缀表达式建成一棵二叉树，叶子是操作数，内部节点是运算符。建树的过程用栈来实现。

class ExprNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def build_expr_tree(postfix): stack = [] for token in postfix: if token.isdigit(): stack.append(ExprNode(token)) else: right = stack.pop() left = stack.pop() stack.append(ExprNode(token, left, right)) return stack[0]

建好树之后，中序遍历得到中缀表达式，后序遍历得到后缀表达式，前序遍历得到前缀表达式。这个结构在编译器的语法分析里很常见。

7.4 循环队列在嵌入式里的应用

在嵌入式开发里，循环队列用得特别多，因为它的内存是预分配的，不会动态申请，适合资源受限的环境。串口通信的接收缓冲区、ADC采样的数据缓冲，基本都是循环队列。

嵌入式里的循环队列通常用宏或者内联函数实现，避免函数调用开销。而且判空判满往往用位运算优化，比如容量取2的幂，取模用& (capacity - 1)代替，速度更快。

#define QUEUE_SIZE 256 // 必须是2的幂 typedef struct { int data[QUEUE_SIZE]; volatile int head; volatile int tail; } RingBuffer; static inline int rb_is_empty(RingBuffer *rb) { return rb->head == rb->tail; } static inline int rb_is_full(RingBuffer *rb) { return ((rb->tail + 1) & (QUEUE_SIZE - 1)) == rb->head; }

volatile关键字在嵌入式里很重要，因为head和tail可能被中断服务程序修改，编译器不能优化掉对它们的读取。

8. 写在最后的一些个人体会

栈和队列这两个结构，我用了十几年，每次回头看都有新的理解。刚开始学的时候觉得它们太简单，没什么好讲的；工作几年后发现，很多复杂系统的设计里都有它们的影子；再后来做架构，才真正体会到"受限"带来的价值——正是因为它们只允许在特定位置操作，才让并发控制、内存管理、逻辑推理都变得简单。

如果你正在学这两个结构，我的建议是别只停留在看代码，一定要自己动手写一遍。顺序栈的扩容、循环队列的判满、链式队列的边界，这些坑只有自己踩过才记得住。写完之后再去找几道相关的算法题练手，括号匹配、滑动窗口最大值、用栈实现队列，做完这些你基本就掌握了。

如果你已经工作几年，想回头补基础，我建议从"为什么"入手。不要只问"栈怎么实现"，要问"为什么函数调用要用栈""为什么BFS要用队列"。把结构和它解决的问题联系起来，理解会深刻得多。

最后分享一个我自己的习惯：每次遇到一个新的数据结构或算法，我都会问自己三个问题——它解决什么问题？它的核心操作是什么？它的边界条件在哪里？这三个问题想清楚了，基本就掌握得差不多了。栈和队列也不例外。