首页/数据结构/03-stack-queue-array/共享栈 🔗 在 Obsidian 中打开
数据结构 · 03-stack-queue-array

共享栈

难度 ★★★重要度 ★★ 考查频率 低题型 选择 / 填空 栈共享栈双端栈
速查
共享栈 = 两个栈共享同一片连续存储：栈 1 从下标 0 向右增长，栈 2 从 MaxSize-1 向左增长；栈满：top1 + 1 == top2（两栈顶指针相邻）。

核心概念 ▾

共享栈（Shared Stack）是指两个栈共享同一片连续存储空间的数据结构。

基本思想

  • 将一个数组的两端分别作为两个栈的栈底
  • 栈 1 从数组头部（下标 0）向右增长
  • 栈 2 从数组尾部（下标 MaxSize-1）向左增长
  • 栈满条件：两个栈顶指针相遇（ $ top1 + 1 == top2 $ ）
#define MaxSize 100
typedef struct {
    ElemType data[MaxSize];
    int top1;  // 栈1的栈顶指针，初始值为 -1
    int top2;  // 栈2的栈顶指针，初始值为 MaxSize
} SharedStack;

关键性质 ▾

初始化

void InitStack(SharedStack *S) {
    S->top1 = -1;        // 栈1为空
    S->top2 = MaxSize;   // 栈2为空
}

判空

  • 栈 1 空：$ S->top1 == -1 $
  • 栈 2 空：$ S->top2 == MaxSize $
  • 两栈都空：$ S->top1 == -1 \;\&\&\; S->top2 == MaxSize $

判满

  • 栈满：$ S->top1 + 1 == S->top2 $

入栈操作

bool Push(SharedStack *S, ElemType x, int stackNum) {
    if (S->top1 + 1 == S->top2)  // 栈满
        return false;
    if (stackNum == 1)
        S->data[++S->top1] = x;  // 栈1入栈
    else
        S->data[--S->top2] = x;  // 栈2入栈
    return true;
}

出栈操作

bool Pop(SharedStack *S, ElemType *x, int stackNum) {
    if (stackNum == 1) {
        if (S->top1 == -1) return false;  // 栈1空
        *x = S->data[S->top1--];
    } else {
        if (S->top2 == MaxSize) return false;  // 栈2空
        *x = S->data[S->top2++];
    }
    return true;
}
空间利用优势当栈 1 使用空间少时，栈 2 可使用更多空间，比两个独立栈更省空间。

手算示例 ▾

示例：共享栈的操作序列

题目：$MaxSize=8$ 的共享栈，执行：①栈 1 压入 A,B,C；②栈 2 压入 X,Y；③栈 1 弹出；④栈 2 压入 Z。

步骤 4 结束后：$top1=1,\; top2=5$。判满：$top1+1=2 \neq top2=5$，未满；还可容纳 $top2-top1-1 = 5-1-1 = 3$ 个元素（下标 2、3、4 三个空位）。

状态栈 1 占 [0,1]，栈 2 占 [5,6,7]，中间 [2,3,4] 空闲，两栈顶指针未相遇。

常见考法 ▾

高频设问
  • 判断栈满：$ top1 + 1 == top2 $。
  • 操作序列分析：给定操作画出共享栈状态图。
  • 最大容量：MaxSize 为 n 的共享栈最多存 n 个元素（两栈可占满整个数组）。
  • 代码填空：补全入栈/出栈代码。

易错点 ▾

必记
  1. top1 初始为 -1，top2 初始为 MaxSize：不要搞反。
  2. 栈满是 $top1+1==top2$ 而非 $top1==top2$：top1 指向最后元素，top2 指向下一个可存位置。
  3. 两个栈独立：栈 1 满不影响栈 2（除非空间用完）。
  4. top2 增长方向向左：栈 2 入栈是 --top2。
  5. 共享 ≠ 数据混在一起：逻辑上仍是两个独立栈。

核心结论 ▾

必背
  • 共享栈让两个栈共享同一数组空间，实现空间互补。
  • 栈满：$ top1 + 1 == top2 $（两栈顶指针相邻即满）。
  • 适合两个栈空间需求互补的场景。
  • 相比两个独立栈节省空间，入栈出栈均为 O(1)。

记忆卡片 ▾

共享栈的栈满条件？
$ top1 + 1 == top2 $，两栈顶指针相邻即满。
初始化时 top1、top2 分别为什么值？
$ top1=-1 $（栈1空），$ top2=MaxSize $（栈2空）。
相比两个独立栈的优势？
空间互补，减少浪费。
栈 2 入栈时 top2 如何变化？
递减 --top2，从数组末尾向左增长。
MaxSize=100 最多存多少元素？
最多 100 个，两栈可占满整个数组。
栈满为何不是 top1==top2？
top2 指向下一个空位，相邻（差1）即已满。

交互动画 · 共享栈 ▾

MaxSize = 8
点击按钮操作两个栈
橙=栈1（向右增长），绿=栈2（向左增长）；两指针相遇即满。

相关知识点

（暂无关联知识点）