写表达式求值、括号匹配这类算法题的人多半都遇到过这样一个尴尬场面一个栈常年半空另一个栈动不动就溢出。你明明给两块栈各分了一半内存可实际跑起来常常是一个饿死、一个撑死。共享栈这个结构就是冲着这个浪费来的。它把两个栈塞进同一段连续空间一个从这头往中间长一个从那头往中间长谁需要谁就多占一点只有当两边真正撞上时才算满。我最早是在看数据结构教材里的“两栈共享空间”时接触到它当时觉得这就是个考试知识点后来在做表达式求值、撤销重做缓存、以及自己写小型虚拟机的时候发现它其实相当实用。这篇文章会把共享栈的来龙去脉、边界条件、完整实现、坑点和排查方法全部讲清楚适合正在准备数据结构考试的同学、刚入行想补基础的开发者以及需要在资源受限环境下榨出一点内存的人。1. 共享栈到底解决什么问题从两个栈抢内存说起1.1 一个真实的内存浪费场景先还原一个具体场景。假设你要写一个中缀表达式转后缀表达式的程序标准做法是准备两个栈一个存操作数一个存运算符。你预算了 200 个元素的空间于是很自然地各分 100。问题是输入一个像12345这样的表达式时操作数栈会堆很多数而运算符栈最多同时压一层反过来遇到((((((1))))))这种深度嵌套的括号运算符栈又会被括号塞满操作数栈几乎空着。这种“一方吃紧、一方闲置”的错配在栈容量固定时几乎是常态。单独分配两个栈的根本问题在于你无法预知两个栈各自的峰值只能按最坏情况各留一份余量。余量留少了某个栈会溢出留多了就是纯浪费。更要命的是一些嵌入式场景比如单片机上的命令行解析器总共可能就几 KB 的可用内存你根本没有余量可以浪费。共享栈的思路很直接既然两个栈不会同时到达各自的峰值那就让它们共用一整块空间用动态的边界来分配谁在用就多给谁一点。这本质上是一种非常朴素的“内存池”思想只不过池子里只有两个用户而且这两个用户的增长方向是相向的。注意免费的内存共享永远有代价共享栈的总容量是固定的它换取的是“平均利用率更高”但并没有凭空变出空间。当两个栈真的同时接近峰值时它依然会满只是满得更晚、更体面。1.2 核心约定与边界条件先把它钉死共享栈的全部精妙都集中在两个指针的约定上。以容量为maxSize的数组data为例左栈记作栈 1的栈底固定在数组下标 0栈顶指针top1初始为-1每压入一个元素top1加一。右栈记作栈 2的栈底固定在数组末尾maxSize - 1栈顶指针top2初始为maxSize每压入一个元素top2减一。这里top2的初值为什么是maxSize而不是maxSize - 1这是最容易被记错的地方。把top2看成“下一个可写入位置”的右边界更直观栈 2 的第一个元素应该写在maxSize - 1所以写入前先执行--top2那初始值自然要设在maxSize。这样两个栈共享同一套“指针指向栈顶元素”的语义判定逻辑才统一。由此推出四条关键判定栈 1 空top1 -1栈 2 空top2 maxSize栈满top1 1 top2两边指针贴在一起中间没有空隙当前元素总数(top1 1) (maxSize - top2)注意栈满条件是top1 1 top2不是top1 top2。这个“差一”关系是所有出错的源头一旦写成top1 top2最后一个空位会被当场覆盖两个栈的值互相污染而且这种 bug 在测试数据不极端时经常不触发非常隐蔽。1.3 为什么是两个栈而不是三个或更多教科书大多只讲两栈共享这不是偷懒。两个栈能做到“相向生长且互不干扰”是因为它们的增长方向恰好只有两条从低地址往高地址、从高地址往低地址。空间被两端的增长夹在中间边界只有一个接触面判定简单。三个栈就麻烦了。三个方向在一条线上没有解它们终会互相交错要么引入更复杂的分段管理要么退化成给每个栈划固定区间那又回到了浪费的老路。真要在多栈之间动态调度实用的做法是链式存储或维护一个空闲块链表让每个栈的块按需伸