栈和队列大概是数据结构里最容易被低估的两个结构。很多人复习的时候扫一眼"后进先出""先进先出"就翻过去了，觉得这玩意儿能有什么花样。但我带过几轮校招笔试和项目代码评审之后发现，真正在工程里把栈和队列用明白的人并不多——大部分人的问题不是不懂定义，而是不知道什么时候该用、用哪种变体、边界条件怎么处理。这篇就把栈和队列的复习拆开揉碎讲一遍，从底层实现选型到典型应用场景，再到实际写代码时最容易翻车的地方，尽量把"考试会考"和"工程会用"这两条线都覆盖到。不管你是正在准备笔试面试，还是写业务代码时隐约觉得该用个栈但不确定怎么下手，下面这些内容应该都能对上号。
1. 先把栈和队列的底层实现选型搞清楚
很多人复习数据结构有个习惯：直接背操作和复杂度，跳过实现方式。这个顺序其实是反的。栈和队列只是"逻辑结构"——规定了元素进出的顺序规则，但底层用什么物理结构承载，直接决定了你的代码在真实场景下的表现。同一个栈，用数组实现和用链表实现，在缓存友好度、扩容开销、内存碎片这几个维度上完全是两回事。
1.1 顺序存储与链式存储的真实差异
顺序栈的底层是一块连续内存，靠一个栈顶指针（本质是数组下标）标记当前位置。入栈就是往top+1的位置写值再把top加一，出栈就是把top减一。这个过程的优势在于内存连续，CPU 缓存命中率高，而且不需要为每个元素额外存指针。缺点是容量固定，扩容时要重新申请一块更大的内存并把旧数据搬过去，这个搬迁是 O(n) 的。
链式栈每个节点存一个值和一
