如何用一个数组实现多个栈？有哪些空间分配策略？
简化版
一个数组实现多个栈，可以固定分区，也可以动态共享空间。两个栈常从数组两端向中间增长；多个栈可以用空闲链表管理数组槽位，让不同栈按需占用空间。核心问题是避免空间浪费和处理栈满。
详细版
固定分区最简单：数组平均切成 k 段，每个栈只能用自己的段。优点是实现容易，缺点是某个栈满时，即使其他段空着也不能用。
更灵活的方式：
- 两个栈：一个从左往右增长，一个从右往左增长。
- k 个栈：用
next[]数组维护每个元素的链接，再用freeTop管理空闲槽位。 - 每个栈保存自己的栈顶下标。
- push 时从空闲链表拿槽位，pop 时把槽位还回空闲链表。
这题考的是数组空间复用和栈顶管理，不只是 push/pop。
完整版教学
一、为什么会想用一个数组放多个栈
有些场景希望减少对象分配，或者底层内存只能提供一段连续空间。此时多个逻辑栈可以共享一个物理数组。
最简单想法是固定分区：
数组长度 12，3 个栈
栈0: [0..3]
栈1: [4..7]
栈2: [8..11]这种方式容易实现，但空间利用率差。栈0满了以后，即使栈2完全空着，栈0也不能继续增长。
二、两个栈为什么可以从两端增长
如果只有两个栈，可以让一个从左端增长，另一个从右端增长。
leftStack -> <- rightStack
[a,b,_,_,_,_,x,y]只要两个栈顶没有相遇，就还有空间。判断条件通常是：
top1 + 1 < top2这种方式比固定分区灵活，因为两个栈共享中间剩余空间。只要总元素数没超过数组容量，就不会因为某一边固定分区满而提前失败。
三、多个栈共享空间为什么需要空闲链表
k 个栈不能简单都从不同方向增长，因为方向不够。更通用的方式是把数组槽位当成节点池，用 next[] 记录链接关系。
需要几个数组：
data[] 存元素
next[] 存同栈下一个节点或空闲链下一个槽位
top[] 每个栈的栈顶下标
freeTop 空闲槽位链表头初始化时，所有槽位都在空闲链表里。push 某个栈时，从 freeTop 拿一个槽位；pop 时，把槽位还给 freeTop。
四、push 操作如何更新指针
假设要向第 s 个栈 push 值 x：
const i = freeTop;
freeTop = next[i];
data[i] = x;
next[i] = top[s];
top[s] = i;这段逻辑类似链表头插。新槽位 i 成为栈顶，它的 next[i] 指向旧栈顶。所有操作都是下标操作，不需要真正分配节点对象。
数字例子：容量 5，空闲链 0 -> 1 -> 2 -> 3 -> 4。向栈0 push A，会拿槽位 0，栈0 top 变 0，空闲链从 1 开始。
五、pop 操作如何回收槽位
pop 第 s 个栈时，从 top[s] 取槽位，再把它挂回空闲链表。
const i = top[s];
top[s] = next[i];
const value = data[i];
next[i] = freeTop;
freeTop = i;这一步非常关键：释放的槽位不能丢，必须回到 free list。否则数组空间会越来越少，出现“逻辑上空了，物理上不能再用”的泄漏。
六、不同策略怎么比较
| 策略 | 适用 | 优点 | 缺点 |
|---|---|---|---|
| 固定分区 | 栈数量和大小稳定 | 简单 | 空间浪费 |
| 两端增长 | 两个栈 | 共享空间 | 只适合两个 |
| 空闲链表 | 多个栈 | 空间利用高 | 实现复杂 |
记忆钩子：多个栈共享数组，本质是把数组槽位当“节点池”；top 管各栈，freeTop 管空位。
七、常见误区与追问
- 误区：固定分区就能充分利用空间。 某个栈满时，其他栈的空位不能共享，会浪费。
- 误区：多个栈都能从两端增长。 两端增长天然适合两个栈，k 个栈需要更通用的空间管理。
- 误区：pop 后只移动 top 就行。 槽位必须回收到空闲链表，否则空间泄漏。
- 追问：push 什么时候失败？
freeTop == -1时说明没有空闲槽位，整个数组满。 - 追问：这种结构的 push/pop 复杂度是多少？ 都是 O(1)，因为只改常数个下标。
八、加强记忆
一个数组实现多个栈，先从简单到复杂回答：固定分区最简单但浪费；两个栈可从两端向中间长；多个栈用 data + next + top + freeTop，把数组当节点池。能讲清 free list 的回收，才算真正理解空间复用。