先问你一个很实际的问题现在只给你一块空间比如一个int data[100]要同时放下两个栈空间还不能浪费你打算怎么切这个问题我在面试里问过很多次也在课程设计答疑时被同学问过很多次答案就是数据结构里那个看着简单、但细节很容易写错的“共享栈”。共享栈解决的核心问题是顺序栈在空间预分配上的浪费。写顺序栈的人都清楚定长数组一旦确定 MAXSIZEtop 指针从 0 一路走到 MAXSIZE-1满了就溢出。可如果系统里需要两个栈常规做法是各给一半于是麻烦来了一边疯狂 push 已经撑爆另一边几乎没用固定的一半空间白白躺在那里吃灰。共享栈的做法是把两个栈放进同一个数组的两端栈底各占一头栈顶向中间生长谁需要空间谁就“往中间挤”。它不是解决了“总容量不够”的问题而是解决了“两个栈之间空间怎么动态分配才不浪费”的问题。这篇文章适合期末复习、考研数据结构、面试前突击手写代码的同学。我会从空间利用逻辑讲起把满条件和空条件掰开揉碎再给一份能直接跑的 C 语言实现最后聊聊这个结构在实际系统和面试里到底怎么用。文章略长但看完你就能彻底搞懂共享栈。1. 一块数组塞下两个栈共享栈的空间利用逻辑1.1 为什么普通顺序栈总是浪费空间先算一笔账。假设你有一个容量 100 的数组要分给两个顺序栈用。很多人第一直觉是各给 50data[0..49]归栈1data[50..99]归栈2。这个方案实现最简单但问题极其明显。想象一个真实场景栈1运行过程中峰值需要 80 个位置栈2峰值只需要 20 个位置。两个栈的总需求正好是 100理论上一个完整数组足够。但在“各分50”的方案里栈1 在 push 到第 51 个元素时就溢出了栈2 那边还剩 30 多个空位闲置。一边顶到天花板一边睡大床这种空间碎片化浪费在固定划分里根本无法避免。更麻烦的是普通顺序栈的容量上限是写死的。栈1 的最大容量就是 50栈2 的最大容量也是 50。就算你在运行时发现栈2空得离谱想把那 30 个空位临时借给栈1用顺序栈本身做不到因为它的 top 指针只能在自己的区间里移动越过边界就是数组越界轻则数据错乱重则段错误。所以说白了普通顺序栈“各自为政”的存储方式在两个栈需求不均衡时必然产生死区。这个死区不是数据占着不放是结构上根本不可能被利用只能白白空着。1.2 空间利用率对比各分一半和动态互补差多少共享栈的思路就是把“各分一半”改成“共用一整块”。我用一张表说清楚两者差异。对比项两个独立顺序栈共享栈空间划分各自固定区域互不借用共用一个数组动态互补满条件各自 top 到达区域边界top1 1 top2空间利用率有固定死区可能长期闲置只要总量不超容量不浪费元素类型两个栈可以不同类型两个栈元素类型必须一致扩容难度各自扩容互相独立两个栈相互牵制扩容麻烦“各分一半”时有个很扎心的结论两个栈各分 50就算你只用一个栈最多也只能用 50 个位置整体利用率上限就是 50%。共享栈不同它的空间是流动的。假如一个栈空着另一个栈理论上可以占满整个数组两个栈都有数据时只要元素总数不超过数组容量就不会出现“一边满一边空”的固定浪费。举个具体数据对比场景A栈1峰值 80栈2峰值 20总量 100。独立分配各50必然溢出共享一个容量 100 的数组可以正常完成一点不浪费。场景B栈1峰值 70栈2峰值 70总量 140。共享 100 的数组同样溢出因为总容量不够这不怪共享栈是池子本身小了。共享栈真正的适用场景是“两个栈一高一低、总量可控”的互补场景。栈1忙的时候栈2通常比较闲栈2忙起来栈1又让出了空间。生活里最像的例子是合租两人各住一间卧室客厅厨房共用谁有客人来谁就多占一点只要屋子总空间够住就不会有人睡到走廊。2. 核心原理两个栈顶如何相向生长2.1 栈底固定在两端栈顶向中间靠拢共享栈的结构定义不复杂。一个数组data[0..MAXSIZE-1]两个栈分别叫栈1和栈2。栈1的栈底固定在数组头部也就是下标 0 的位置栈顶指针top1从 -1 出发每次入栈先 1 再写入栈2的栈底固定在数组尾部也就是下标 MAXSIZE-1 的位置栈顶指针top2从 MAXSIZE 出发每次入栈先 -1 再写入。两个栈底纹丝不动栈顶随着元素增多逐渐向数组中间靠拢。这里有个新手常问的问题为什么栈2的栈底不也从 0 开始真要那样两个栈都从头部生长中间空闲区域会变得极不规则而且其中一个栈的栈底位置会随另一个栈的长度变化一直搬家。栈结构最核心的约束是“只能在栈顶操作”栈底必须稳定否则元素顺序都保不住。所以共享栈的唯一合理布局就是两端固定、中间浮动。2.2 满条件与空条件的真正含义普通顺序栈的满条件是top MAXSIZE - 1也就是栈顶走到数组边界。共享栈不能这么判因为边界不再是数组两端的固定值而是另一个栈的栈顶。共享栈的满条件是top1 1 top2为什么不是top1 top2因为 top1 和 top2 指向的都是“当前栈顶元素”的位置。当top1 1 top2时说明栈1的下一个可用位置恰好就是栈2当前栈顶所在位置中间已经没有任何空位。而top1 top2这个条件在合法操作下永远不会出现因为早在它出现之前top1 1 top2就已经拦住了继续入栈的请求。如果你真的看到了top1 top2说明两个指针踩到了同一个下标也就是说某个栈已经覆盖了另一个栈的元素数据早就被破坏了。空条件则非常简单栈1空top1 -1栈2空top2 MAXSIZE。这两个和普通顺序栈的判空方式完全一致对称又直观。2.3 一次 push 的完整过程演示拿一个具体的数组长度模拟一遍会特别清晰。假设 MAXSIZE 6初始时 top1 -1top2 6。push 栈1值 10检查top1 1 top2即 -1 1 0不等于 6没满。top1 变为 0data[0] 10。push 栈1值 20top1 变为 1data[1] 20。push 栈1值 30top1 变为 2data[2] 30。push 栈2值 100检查 2 1 3不等于 6没满。top2 变为 5data[5] 100。push 栈2值 200检查 2 1 3top2 是 5不等于。top2 变为 4data[4] 200。push 栈1值 40检查 2 1 3top2 是 4不等于。top1 变为 3data[3] 40。此时数组被填满data[0..3]属于栈1data[4..5]属于栈2top1 3top2 4正好满足top1 1 top2。再任意 push 一个元素都会失败。整个过程走一遍你对“相向生长”和判满条件之间的关系就能彻底建立直觉。3. 标准实现C语言版共享栈完整代码3.1 结构体定义与初始化共享栈的结构体定义长这样#include stdio.h #include stdbool.h #define MAXSIZE 8 typedef struct { int data[MAXSIZE]; int top1; int top2; } SharedStack; void InitSharedStack(SharedStack *s) { s-top1 -1; s-top2 MAXSIZE; }top1 从 -1 开始保证第一次入栈top1得到 0top2 从 MAXSIZE 开始保证第一次入栈--top2得到 MAXSIZE-1。这两个初始值不是随便定的而是为了让两个栈的入栈出栈操作和普通顺序栈保持同样的“指针先移动、再读写”的节奏同时让判空条件极度对称。3.2 入栈出栈的指针移动细节判空和判满的逻辑bool IsFull(SharedStack *s) { return s-top1 1 s-top2; } bool IsEmpty(SharedStack *s, int stackId) { if (stackId 1) { return s-top1 -1; } return s-top2 MAXSIZE; }入栈和出栈的实现bool Push(SharedStack *s, int stackId, int value) { if (IsFull(s)) { return false; } if (stackId 1) { s-data[s-top1] value; } else { s-data[--s-top2] value; } return true; } bool Pop(SharedStack *s, int stackId, int *out) { if (IsEmpty(s, stackId)) { return false; } if (stackId 1) { *out s-data[s-top1--]; } else { *out s-data[s-top2]; } return true; }这里最需要警惕的是前自增和前自减的写法。栈1入栈用data[s-top1]先移动指针再写入因为 top1 初始是 -1下标0才是第一个可用位置。栈2入栈用data[--s-top2]也是先移动再写入因为 top2 初始是 MAXSIZE下标 MAXSIZE-1 才是第一个可用位置。如果你把栈2的入栈写成data[s-top2--]第一次写入就会访问data[MAXSIZE]直接数组越界。出栈则正好反过来先取当前位置的值再把指针往回收。3.3 一个能直接运行的测试样例完整跑一个例子int main(void) { SharedStack s; InitSharedStack(s); Push(s, 1, 11); Push(s, 1, 12); Push(s, 1, 13); Push(s, 2, 21); Push(s, 2, 22); printf(栈1元素个数: %d\n, s.top1 1); printf(栈2元素个数: %d\n, MAXSIZE - s.top2); printf(剩余空位: %d\n, s.top2 - s.top1 - 1); int value; Pop(s, 2, value); printf(栈2出栈: %d\n, value); Push(s, 1, 14); printf(栈1顶部: %d\n, s.data[s.top1]); return 0; }运行结果栈1元素个数: 3 栈2元素个数: 2 剩余空位: 3 栈2出栈: 22 栈1顶部: 14这段代码里MAXSIZE 8初始 push 后栈1占用下标 0、1、2栈2占用下标 7、6中间下标 3、4、5 还能放 3 个元素。出栈栈2后top2 变成 7再 push 栈1 到下标 3整个过程都在边界内结果符合预期。4. 为什么现实中用得少真实应用与思想延伸4.1 程序内存布局栈区与堆区的共享空间思想很多人学完共享栈都会问一个问题这结构现实中到底用在哪说实话业务代码里直接封装一个共享栈用的场合很少因为现代高级语言自带动态数组、无限栈容器没人愿意手写一个容量互相牵扯的数据结构。但共享栈的思想在系统底层到处都是最典型的就是进程虚拟地址空间里的栈区和堆区。程序运行时函数调用栈从高地址向低地址生长堆区从低地址向高地址生长两块区域共享同一片动态地址空间。栈区压得深堆区分配得多某一天二者相遇就会栈溢出或者内存分配失败。这背后的“两端向中间挤”逻辑和共享栈完全一致。虽然这里的“栈”指的是函数调用栈不是一个抽象数据结构的栈但空间管理思路一模一样。理解了这一点再回头看共享栈就会觉得它没那么“冷门”。它其实是空间复用思想的入门课只不过教材喜欢用一个抽象数组来展示核心机制真实系统里这个数组变成了整块地址空间。4.2 同类型双栈场景浏览器前进后退与编辑器撤销重做如果非要找直接使用共享栈的业务场景两个最经典的例子都是“成对出现、需求互补”的双栈结构。第一个是浏览器的前进和后退。浏览器维护两个页面栈后退栈和前进栈。访问一个新页面时当前页面压入后退栈同时清空前进栈点后退时把后退栈弹出的页面作为当前页同时把之前的当前页压入前进栈。这两个栈的容量需求天然互补回退越多前进栈积累越多访问新页面前进栈又被清空。在一次性会话的有限范围内两个栈的数据总量是可控的。如果要在内存受限的环境里实现页面管理用一个数组做共享栈就非常合理。第二个是编辑器里的撤销和重做。撤销栈记录操作历史重做栈记录被撤销掉的操作。一次新编辑会清空重做栈撤销一次又会让重做栈增加一项。两个栈存储的元素类型一致总量也不会无限爆发完全符合共享栈的适用前提。很多桌面软件的会话历史模块内部就是这种成对栈结构。当然现实中这些场景大多用动态分配的两个独立容器实现因为内存足够大代码写起来也更直接。但共享栈的存在提供了一个候选方案尤其当内存被严格限制时它能省下一块不小的固定开销。4.3 广义空间复用思想在受限场景中的应用跳出数据结构课本身共享栈的真正价值在于“空间复用”这四个字。内存池里同一块缓冲区分时扮演不同角色算法竞赛里多个栈或队列共用一段连续内存以压榨空间嵌入式系统中RAM 只有几十 KB经常需要把一个 buffer 的一部分当环形队列、另一部分当栈用用到最后区域不够了再动态调整边界。这种“两个对象错峰使用同一片内存”的思路比共享栈这个数据结构本身值钱得多。我经常跟带的新人说学数据结构不要只背代码要把每种结构背后的“资源管理策略”提炼出来。共享栈的策略就是不预先划分死区让真正有需求的一方临时多占用空闲时自动释放给另一方。理解了这层你在做内存优化时会对空间敏感度完全不一样。5. 边界条件与调试踩坑清单5.1 最容易写错的满条件与指针方向共享栈代码不多但坑点非常集中。我见过最多的错误是把满条件写成top1 top2。前面说过这个条件在正确程序里根本不会触发。真要触发说明两个指针已经指向同一个位置栈1覆盖了栈2的元素数据早就错了。这个 bug 很难发现因为你写测试样例时前面明明还能 push 几个元素到后期却发现数组里莫名其妙少数据排查半天才发现是判满条件失效导致的覆盖。第二个高频错误是栈2的入栈方向。data[--s-top2] value和data[s-top2--] value只差一个前减后减结果天差地别。后者第一次会访问data[MAXSIZE]栈直接崩掉或者在 Debug 版本被 assert 拦下。写共享栈时建议先在纸上画出 top1 和 top2 的初始位置再动笔写代码能有效降低方向搞反的概率。还有一个容易被忽略的点出栈操作要不要把原位置清零。从正确性角度完全不需要因为 top 指针已经回退那个位置下次入栈会被覆盖。但从调试角度数组里残留的旧数据会误导你让你以为某个位置还有元素。我的习惯是在 Debug 模式下把出栈位置写成一个特殊值比如 0 或者 0xCDCD这样看内存时一眼就能分辨哪些是有效数据、哪些是历史残留。5.2 扩容难题与替代方案普通顺序栈扩容是重新分配两倍空间把旧数据复制过去释放旧数组结束。共享栈扩容要麻烦得多因为新数组必须同时保留两个栈的方向。基本思路是这样申请一个更大的新数组。栈1的内容data[0..top1]原样从新数组头部开始复制。栈2的内容data[top2..MAXSIZE-1]从新数组尾部反向复制。更新 top2让它在新数组中新栈2区域的起点位置再向前偏移(newSize - MAXSIZE)。这样操作的风险在于如果新数组申请失败旧数据还在旧数组里但你的复制逻辑如果写到一半发现异常很容易把状态搞乱。所以在实现时要先完成所有复制再更新指针最后释放旧数组。即便如此扩容共享栈的代码也远比普通顺序栈复杂测试样本要覆盖“栈1满”“栈2满”“两栈都接近满”三种情况。如果你在真实项目里发现共享栈频繁需要扩容我的建议是换个思路换成链式栈牺牲一点存储连续性换来容量无限和逻辑简单。共享栈的优势场景是空间固定且受限不是容量频繁变化的场景。5.3 并发环境下共享栈的额外注意点共享栈把两个栈放进同一个结构体struct 内部同时保存 top1 和 top2。单线程下没什么问题一旦多线程同时操作两个栈就有并发风险。先说最基础的两个线程同时 push一个写栈1一个写栈2表面上操作的是不同区域但判满逻辑会同时读取对方的 top 指针两个线程都在修改同一个结构体里的字段存在数据竞争。必须加锁或者用原子操作保证每一步的读改写是互斥的。还有一个比较隐蔽的坑是缓存伪共享。两个栈物理上相邻栈1和栈2的热数据很可能落在同一个缓存行里。在高频并发场景下线程A更新栈1会把线程B正在使用的栈2缓存行标记失效线程B再访问时被迫重新加载性能会莫名其妙地下降。解决思路可以是把 top1 和 top2 对齐到不同的缓存行或者干脆在共享栈外面包一层粒度更粗的锁。对于数据结构课程设计来说这块往往不会深入但作为工程经验心里有数比踩坑之后再查要好得多。6. 面试怎么考共享栈的五种问法6.1 从结构定义到边界条件的层层追问面试里共享栈很少单独作为难题出现更多是顺序栈知识中的一个小分支。最常见的问法是“说说共享栈能解决什么问题”回答要点很简单两个栈共用一段连续空间栈底在两端栈顶相向生长空间可以动态互补避免了固定划分的空间浪费。紧接着面试官大概率会追问“满条件是什么”这时候你要答出top1 1 top2并顺带解释为什么不是top1 top2。这个追问考察的就是对边界条件的理解能讲清楚“top 指向的是栈顶元素位置而不是下一个空位”这句话基本就通过了。再往下可能问“两个栈会互相影响吗”答案是会共享栈的容量是两个栈共同消耗的一个栈 push 太多会把另一个栈的空间挤没。这和两个独立顺序栈最大的区别也是共享栈的适用边界。6.2 单栈退化、三栈延伸与手写代码还有一类延伸问法是“如果共享栈里只用一个栈会怎样”答案是退化成普通顺序栈另一个 top 保持不动第一个栈最多能用满整个数组。这个问题表面问退化实际考察你对“两个栈空间互补”是否真的理解。手写代码是跑不掉的环节。面试时先写结构体和初始化再写判空判满最后写 push/pop。写的时候注意两点一是栈2的入栈必须用--top2这是最容易出错的细节二是 push 和 pop 都要检查边界条件push 先判满pop 先判空返回 bool 而不是在失败时报错或返回垃圾值。更进阶一点面试官会问“三个栈共享一个数组怎么做”。这是个经典的算法设计题思路是数组分成三段栈1从左向右栈2从右向左栈3从某一块中间位置开始浮动。但三栈共享远比两栈复杂因为中间那个栈的边界会被两边的栈的活动挤压需要动态维护三条边界。面试时能讲清思路、画出布局基本就够用了。6.3 能直接说出口的高分回答思路最后整理一套可以直接拿来用的回答框架先画图。在纸上画出数组标出 top1 和 top2 的初始位置画两个箭头表示增长方向。面试官看到图就知道你对结构理解到位。再讲判满。强调top1 1 top2是两指针相邻这时数组已满top1 top2是不合法的异常状态。写代码时先写“判满再写、判空再取”的骨架再填具体逻辑这样不容易漏边界。主动提一句“共享栈要求两个栈元素类型一致”这是很多人完全没意识到的限制条件说出来是加分项。最后补一句复杂度分析push、pop 都是 O(1)空间上动态互补比固定划分更省。这套回答下来面试官基本能确认你不是背的代码而是真正理解了共享栈的运行机制。最后分享一个我自己的习惯。学共享栈的时候别急着敲代码先拿一张纸画一个长度 10 的数组手动模拟几组 push、pop 序列。比如连续 push 栈1五次、栈2三次再用 pop 交错操作每次操作都算一遍两个 top 指针的位置。这样模拟过几轮之后再去看代码指针方向、判满条件、边界问题都会非常自然面试手写时也能写得又快又稳。想进阶一点的话可以试试把共享栈扩展成三栈版本一个数组左边栈从左往右右边栈从右往左中间栈在中段浮动生长。实现完你就会发现共享栈不只是一个小知识点它是对“空间复用”和“动态边界”最直观的练习。数据结构学到这个程度才算是真正入了门。 C语言共享栈详解：原理、实现与面试考点
先问你一个很实际的问题现在只给你一块空间比如一个int data[100]要同时放下两个栈空间还不能浪费你打算怎么切这个问题我在面试里问过很多次也在课程设计答疑时被同学问过很多次答案就是数据结构里那个看着简单、但细节很容易写错的“共享栈”。共享栈解决的核心问题是顺序栈在空间预分配上的浪费。写顺序栈的人都清楚定长数组一旦确定 MAXSIZEtop 指针从 0 一路走到 MAXSIZE-1满了就溢出。可如果系统里需要两个栈常规做法是各给一半于是麻烦来了一边疯狂 push 已经撑爆另一边几乎没用固定的一半空间白白躺在那里吃灰。共享栈的做法是把两个栈放进同一个数组的两端栈底各占一头栈顶向中间生长谁需要空间谁就“往中间挤”。它不是解决了“总容量不够”的问题而是解决了“两个栈之间空间怎么动态分配才不浪费”的问题。这篇文章适合期末复习、考研数据结构、面试前突击手写代码的同学。我会从空间利用逻辑讲起把满条件和空条件掰开揉碎再给一份能直接跑的 C 语言实现最后聊聊这个结构在实际系统和面试里到底怎么用。文章略长但看完你就能彻底搞懂共享栈。1. 一块数组塞下两个栈共享栈的空间利用逻辑1.1 为什么普通顺序栈总是浪费空间先算一笔账。假设你有一个容量 100 的数组要分给两个顺序栈用。很多人第一直觉是各给 50data[0..49]归栈1data[50..99]归栈2。这个方案实现最简单但问题极其明显。想象一个真实场景栈1运行过程中峰值需要 80 个位置栈2峰值只需要 20 个位置。两个栈的总需求正好是 100理论上一个完整数组足够。但在“各分50”的方案里栈1 在 push 到第 51 个元素时就溢出了栈2 那边还剩 30 多个空位闲置。一边顶到天花板一边睡大床这种空间碎片化浪费在固定划分里根本无法避免。更麻烦的是普通顺序栈的容量上限是写死的。栈1 的最大容量就是 50栈2 的最大容量也是 50。就算你在运行时发现栈2空得离谱想把那 30 个空位临时借给栈1用顺序栈本身做不到因为它的 top 指针只能在自己的区间里移动越过边界就是数组越界轻则数据错乱重则段错误。所以说白了普通顺序栈“各自为政”的存储方式在两个栈需求不均衡时必然产生死区。这个死区不是数据占着不放是结构上根本不可能被利用只能白白空着。1.2 空间利用率对比各分一半和动态互补差多少共享栈的思路就是把“各分一半”改成“共用一整块”。我用一张表说清楚两者差异。对比项两个独立顺序栈共享栈空间划分各自固定区域互不借用共用一个数组动态互补满条件各自 top 到达区域边界top1 1 top2空间利用率有固定死区可能长期闲置只要总量不超容量不浪费元素类型两个栈可以不同类型两个栈元素类型必须一致扩容难度各自扩容互相独立两个栈相互牵制扩容麻烦“各分一半”时有个很扎心的结论两个栈各分 50就算你只用一个栈最多也只能用 50 个位置整体利用率上限就是 50%。共享栈不同它的空间是流动的。假如一个栈空着另一个栈理论上可以占满整个数组两个栈都有数据时只要元素总数不超过数组容量就不会出现“一边满一边空”的固定浪费。举个具体数据对比场景A栈1峰值 80栈2峰值 20总量 100。独立分配各50必然溢出共享一个容量 100 的数组可以正常完成一点不浪费。场景B栈1峰值 70栈2峰值 70总量 140。共享 100 的数组同样溢出因为总容量不够这不怪共享栈是池子本身小了。共享栈真正的适用场景是“两个栈一高一低、总量可控”的互补场景。栈1忙的时候栈2通常比较闲栈2忙起来栈1又让出了空间。生活里最像的例子是合租两人各住一间卧室客厅厨房共用谁有客人来谁就多占一点只要屋子总空间够住就不会有人睡到走廊。2. 核心原理两个栈顶如何相向生长2.1 栈底固定在两端栈顶向中间靠拢共享栈的结构定义不复杂。一个数组data[0..MAXSIZE-1]两个栈分别叫栈1和栈2。栈1的栈底固定在数组头部也就是下标 0 的位置栈顶指针top1从 -1 出发每次入栈先 1 再写入栈2的栈底固定在数组尾部也就是下标 MAXSIZE-1 的位置栈顶指针top2从 MAXSIZE 出发每次入栈先 -1 再写入。两个栈底纹丝不动栈顶随着元素增多逐渐向数组中间靠拢。这里有个新手常问的问题为什么栈2的栈底不也从 0 开始真要那样两个栈都从头部生长中间空闲区域会变得极不规则而且其中一个栈的栈底位置会随另一个栈的长度变化一直搬家。栈结构最核心的约束是“只能在栈顶操作”栈底必须稳定否则元素顺序都保不住。所以共享栈的唯一合理布局就是两端固定、中间浮动。2.2 满条件与空条件的真正含义普通顺序栈的满条件是top MAXSIZE - 1也就是栈顶走到数组边界。共享栈不能这么判因为边界不再是数组两端的固定值而是另一个栈的栈顶。共享栈的满条件是top1 1 top2为什么不是top1 top2因为 top1 和 top2 指向的都是“当前栈顶元素”的位置。当top1 1 top2时说明栈1的下一个可用位置恰好就是栈2当前栈顶所在位置中间已经没有任何空位。而top1 top2这个条件在合法操作下永远不会出现因为早在它出现之前top1 1 top2就已经拦住了继续入栈的请求。如果你真的看到了top1 top2说明两个指针踩到了同一个下标也就是说某个栈已经覆盖了另一个栈的元素数据早就被破坏了。空条件则非常简单栈1空top1 -1栈2空top2 MAXSIZE。这两个和普通顺序栈的判空方式完全一致对称又直观。2.3 一次 push 的完整过程演示拿一个具体的数组长度模拟一遍会特别清晰。假设 MAXSIZE 6初始时 top1 -1top2 6。push 栈1值 10检查top1 1 top2即 -1 1 0不等于 6没满。top1 变为 0data[0] 10。push 栈1值 20top1 变为 1data[1] 20。push 栈1值 30top1 变为 2data[2] 30。push 栈2值 100检查 2 1 3不等于 6没满。top2 变为 5data[5] 100。push 栈2值 200检查 2 1 3top2 是 5不等于。top2 变为 4data[4] 200。push 栈1值 40检查 2 1 3top2 是 4不等于。top1 变为 3data[3] 40。此时数组被填满data[0..3]属于栈1data[4..5]属于栈2top1 3top2 4正好满足top1 1 top2。再任意 push 一个元素都会失败。整个过程走一遍你对“相向生长”和判满条件之间的关系就能彻底建立直觉。3. 标准实现C语言版共享栈完整代码3.1 结构体定义与初始化共享栈的结构体定义长这样#include stdio.h #include stdbool.h #define MAXSIZE 8 typedef struct { int data[MAXSIZE]; int top1; int top2; } SharedStack; void InitSharedStack(SharedStack *s) { s-top1 -1; s-top2 MAXSIZE; }top1 从 -1 开始保证第一次入栈top1得到 0top2 从 MAXSIZE 开始保证第一次入栈--top2得到 MAXSIZE-1。这两个初始值不是随便定的而是为了让两个栈的入栈出栈操作和普通顺序栈保持同样的“指针先移动、再读写”的节奏同时让判空条件极度对称。3.2 入栈出栈的指针移动细节判空和判满的逻辑bool IsFull(SharedStack *s) { return s-top1 1 s-top2; } bool IsEmpty(SharedStack *s, int stackId) { if (stackId 1) { return s-top1 -1; } return s-top2 MAXSIZE; }入栈和出栈的实现bool Push(SharedStack *s, int stackId, int value) { if (IsFull(s)) { return false; } if (stackId 1) { s-data[s-top1] value; } else { s-data[--s-top2] value; } return true; } bool Pop(SharedStack *s, int stackId, int *out) { if (IsEmpty(s, stackId)) { return false; } if (stackId 1) { *out s-data[s-top1--]; } else { *out s-data[s-top2]; } return true; }这里最需要警惕的是前自增和前自减的写法。栈1入栈用data[s-top1]先移动指针再写入因为 top1 初始是 -1下标0才是第一个可用位置。栈2入栈用data[--s-top2]也是先移动再写入因为 top2 初始是 MAXSIZE下标 MAXSIZE-1 才是第一个可用位置。如果你把栈2的入栈写成data[s-top2--]第一次写入就会访问data[MAXSIZE]直接数组越界。出栈则正好反过来先取当前位置的值再把指针往回收。3.3 一个能直接运行的测试样例完整跑一个例子int main(void) { SharedStack s; InitSharedStack(s); Push(s, 1, 11); Push(s, 1, 12); Push(s, 1, 13); Push(s, 2, 21); Push(s, 2, 22); printf(栈1元素个数: %d\n, s.top1 1); printf(栈2元素个数: %d\n, MAXSIZE - s.top2); printf(剩余空位: %d\n, s.top2 - s.top1 - 1); int value; Pop(s, 2, value); printf(栈2出栈: %d\n, value); Push(s, 1, 14); printf(栈1顶部: %d\n, s.data[s.top1]); return 0; }运行结果栈1元素个数: 3 栈2元素个数: 2 剩余空位: 3 栈2出栈: 22 栈1顶部: 14这段代码里MAXSIZE 8初始 push 后栈1占用下标 0、1、2栈2占用下标 7、6中间下标 3、4、5 还能放 3 个元素。出栈栈2后top2 变成 7再 push 栈1 到下标 3整个过程都在边界内结果符合预期。4. 为什么现实中用得少真实应用与思想延伸4.1 程序内存布局栈区与堆区的共享空间思想很多人学完共享栈都会问一个问题这结构现实中到底用在哪说实话业务代码里直接封装一个共享栈用的场合很少因为现代高级语言自带动态数组、无限栈容器没人愿意手写一个容量互相牵扯的数据结构。但共享栈的思想在系统底层到处都是最典型的就是进程虚拟地址空间里的栈区和堆区。程序运行时函数调用栈从高地址向低地址生长堆区从低地址向高地址生长两块区域共享同一片动态地址空间。栈区压得深堆区分配得多某一天二者相遇就会栈溢出或者内存分配失败。这背后的“两端向中间挤”逻辑和共享栈完全一致。虽然这里的“栈”指的是函数调用栈不是一个抽象数据结构的栈但空间管理思路一模一样。理解了这一点再回头看共享栈就会觉得它没那么“冷门”。它其实是空间复用思想的入门课只不过教材喜欢用一个抽象数组来展示核心机制真实系统里这个数组变成了整块地址空间。4.2 同类型双栈场景浏览器前进后退与编辑器撤销重做如果非要找直接使用共享栈的业务场景两个最经典的例子都是“成对出现、需求互补”的双栈结构。第一个是浏览器的前进和后退。浏览器维护两个页面栈后退栈和前进栈。访问一个新页面时当前页面压入后退栈同时清空前进栈点后退时把后退栈弹出的页面作为当前页同时把之前的当前页压入前进栈。这两个栈的容量需求天然互补回退越多前进栈积累越多访问新页面前进栈又被清空。在一次性会话的有限范围内两个栈的数据总量是可控的。如果要在内存受限的环境里实现页面管理用一个数组做共享栈就非常合理。第二个是编辑器里的撤销和重做。撤销栈记录操作历史重做栈记录被撤销掉的操作。一次新编辑会清空重做栈撤销一次又会让重做栈增加一项。两个栈存储的元素类型一致总量也不会无限爆发完全符合共享栈的适用前提。很多桌面软件的会话历史模块内部就是这种成对栈结构。当然现实中这些场景大多用动态分配的两个独立容器实现因为内存足够大代码写起来也更直接。但共享栈的存在提供了一个候选方案尤其当内存被严格限制时它能省下一块不小的固定开销。4.3 广义空间复用思想在受限场景中的应用跳出数据结构课本身共享栈的真正价值在于“空间复用”这四个字。内存池里同一块缓冲区分时扮演不同角色算法竞赛里多个栈或队列共用一段连续内存以压榨空间嵌入式系统中RAM 只有几十 KB经常需要把一个 buffer 的一部分当环形队列、另一部分当栈用用到最后区域不够了再动态调整边界。这种“两个对象错峰使用同一片内存”的思路比共享栈这个数据结构本身值钱得多。我经常跟带的新人说学数据结构不要只背代码要把每种结构背后的“资源管理策略”提炼出来。共享栈的策略就是不预先划分死区让真正有需求的一方临时多占用空闲时自动释放给另一方。理解了这层你在做内存优化时会对空间敏感度完全不一样。5. 边界条件与调试踩坑清单5.1 最容易写错的满条件与指针方向共享栈代码不多但坑点非常集中。我见过最多的错误是把满条件写成top1 top2。前面说过这个条件在正确程序里根本不会触发。真要触发说明两个指针已经指向同一个位置栈1覆盖了栈2的元素数据早就错了。这个 bug 很难发现因为你写测试样例时前面明明还能 push 几个元素到后期却发现数组里莫名其妙少数据排查半天才发现是判满条件失效导致的覆盖。第二个高频错误是栈2的入栈方向。data[--s-top2] value和data[s-top2--] value只差一个前减后减结果天差地别。后者第一次会访问data[MAXSIZE]栈直接崩掉或者在 Debug 版本被 assert 拦下。写共享栈时建议先在纸上画出 top1 和 top2 的初始位置再动笔写代码能有效降低方向搞反的概率。还有一个容易被忽略的点出栈操作要不要把原位置清零。从正确性角度完全不需要因为 top 指针已经回退那个位置下次入栈会被覆盖。但从调试角度数组里残留的旧数据会误导你让你以为某个位置还有元素。我的习惯是在 Debug 模式下把出栈位置写成一个特殊值比如 0 或者 0xCDCD这样看内存时一眼就能分辨哪些是有效数据、哪些是历史残留。5.2 扩容难题与替代方案普通顺序栈扩容是重新分配两倍空间把旧数据复制过去释放旧数组结束。共享栈扩容要麻烦得多因为新数组必须同时保留两个栈的方向。基本思路是这样申请一个更大的新数组。栈1的内容data[0..top1]原样从新数组头部开始复制。栈2的内容data[top2..MAXSIZE-1]从新数组尾部反向复制。更新 top2让它在新数组中新栈2区域的起点位置再向前偏移(newSize - MAXSIZE)。这样操作的风险在于如果新数组申请失败旧数据还在旧数组里但你的复制逻辑如果写到一半发现异常很容易把状态搞乱。所以在实现时要先完成所有复制再更新指针最后释放旧数组。即便如此扩容共享栈的代码也远比普通顺序栈复杂测试样本要覆盖“栈1满”“栈2满”“两栈都接近满”三种情况。如果你在真实项目里发现共享栈频繁需要扩容我的建议是换个思路换成链式栈牺牲一点存储连续性换来容量无限和逻辑简单。共享栈的优势场景是空间固定且受限不是容量频繁变化的场景。5.3 并发环境下共享栈的额外注意点共享栈把两个栈放进同一个结构体struct 内部同时保存 top1 和 top2。单线程下没什么问题一旦多线程同时操作两个栈就有并发风险。先说最基础的两个线程同时 push一个写栈1一个写栈2表面上操作的是不同区域但判满逻辑会同时读取对方的 top 指针两个线程都在修改同一个结构体里的字段存在数据竞争。必须加锁或者用原子操作保证每一步的读改写是互斥的。还有一个比较隐蔽的坑是缓存伪共享。两个栈物理上相邻栈1和栈2的热数据很可能落在同一个缓存行里。在高频并发场景下线程A更新栈1会把线程B正在使用的栈2缓存行标记失效线程B再访问时被迫重新加载性能会莫名其妙地下降。解决思路可以是把 top1 和 top2 对齐到不同的缓存行或者干脆在共享栈外面包一层粒度更粗的锁。对于数据结构课程设计来说这块往往不会深入但作为工程经验心里有数比踩坑之后再查要好得多。6. 面试怎么考共享栈的五种问法6.1 从结构定义到边界条件的层层追问面试里共享栈很少单独作为难题出现更多是顺序栈知识中的一个小分支。最常见的问法是“说说共享栈能解决什么问题”回答要点很简单两个栈共用一段连续空间栈底在两端栈顶相向生长空间可以动态互补避免了固定划分的空间浪费。紧接着面试官大概率会追问“满条件是什么”这时候你要答出top1 1 top2并顺带解释为什么不是top1 top2。这个追问考察的就是对边界条件的理解能讲清楚“top 指向的是栈顶元素位置而不是下一个空位”这句话基本就通过了。再往下可能问“两个栈会互相影响吗”答案是会共享栈的容量是两个栈共同消耗的一个栈 push 太多会把另一个栈的空间挤没。这和两个独立顺序栈最大的区别也是共享栈的适用边界。6.2 单栈退化、三栈延伸与手写代码还有一类延伸问法是“如果共享栈里只用一个栈会怎样”答案是退化成普通顺序栈另一个 top 保持不动第一个栈最多能用满整个数组。这个问题表面问退化实际考察你对“两个栈空间互补”是否真的理解。手写代码是跑不掉的环节。面试时先写结构体和初始化再写判空判满最后写 push/pop。写的时候注意两点一是栈2的入栈必须用--top2这是最容易出错的细节二是 push 和 pop 都要检查边界条件push 先判满pop 先判空返回 bool 而不是在失败时报错或返回垃圾值。更进阶一点面试官会问“三个栈共享一个数组怎么做”。这是个经典的算法设计题思路是数组分成三段栈1从左向右栈2从右向左栈3从某一块中间位置开始浮动。但三栈共享远比两栈复杂因为中间那个栈的边界会被两边的栈的活动挤压需要动态维护三条边界。面试时能讲清思路、画出布局基本就够用了。6.3 能直接说出口的高分回答思路最后整理一套可以直接拿来用的回答框架先画图。在纸上画出数组标出 top1 和 top2 的初始位置画两个箭头表示增长方向。面试官看到图就知道你对结构理解到位。再讲判满。强调top1 1 top2是两指针相邻这时数组已满top1 top2是不合法的异常状态。写代码时先写“判满再写、判空再取”的骨架再填具体逻辑这样不容易漏边界。主动提一句“共享栈要求两个栈元素类型一致”这是很多人完全没意识到的限制条件说出来是加分项。最后补一句复杂度分析push、pop 都是 O(1)空间上动态互补比固定划分更省。这套回答下来面试官基本能确认你不是背的代码而是真正理解了共享栈的运行机制。最后分享一个我自己的习惯。学共享栈的时候别急着敲代码先拿一张纸画一个长度 10 的数组手动模拟几组 push、pop 序列。比如连续 push 栈1五次、栈2三次再用 pop 交错操作每次操作都算一遍两个 top 指针的位置。这样模拟过几轮之后再去看代码指针方向、判满条件、边界问题都会非常自然面试手写时也能写得又快又稳。想进阶一点的话可以试试把共享栈扩展成三栈版本一个数组左边栈从左往右右边栈从右往左中间栈在中段浮动生长。实现完你就会发现共享栈不只是一个小知识点它是对“空间复用”和“动态边界”最直观的练习。数据结构学到这个程度才算是真正入了门。