Appearance
顺序栈
为什么需要顺序栈
栈是一种操作受限的线性表，只允许在一端（栈顶）进行插入和删除操作，遵循后进先出（LIFO, Last In First Out） 原则。
生活中的例子：一摞盘子，只能从最上面取走或放入；浏览器的后退功能，最近访问的页面最先被返回。在程序设计中，函数调用栈、表达式求值、括号匹配等场景都依赖栈结构。
顺序栈是用数组实现的栈，是栈的最常见实现方式。408 考研中，顺序栈是栈与队列章节的核心起点，入栈/出栈序列问题更是选择题的重灾区。
核心思想
顺序栈的核心特点：
- 后进先出（LIFO）：最后入栈的元素最先出栈
- 操作受限：只能在栈顶进行插入（入栈/Push）和删除（出栈/Pop）
- 栈顶指针
top：指示当前栈顶元素的位置
存储结构定义
c
#define MaxSize 50 // 栈的最大容量
typedef struct {
int data[MaxSize]; // 存放栈中元素
int top; // 栈顶指针
} SqStack;栈顶指针的两种约定
| 约定 | 初始值 | 栈顶元素 | 栈空条件 | 栈满条件 | 入栈操作 | 出栈操作 |
|---|---|---|---|---|---|---|
top 指向栈顶元素 | top = -1 | data[top] | top == -1 | top == MaxSize - 1 | 先 ++top，再赋值 | 先取值，再 top-- |
top 指向栈顶元素的下一个位置 | top = 0 | data[top - 1] | top == 0 | top == MaxSize | 先赋值，再 ++top | 先 top--，再取值 |
⭐ 408 考研默认采用
top = -1的约定，做题时务必看清题目条件。两种约定下入栈/出栈的操作顺序恰好相反，这是选择题常见陷阱。
入栈与出栈操作流程图
以 top = -1 约定为例：
交互可视化
通过下方的交互动画，你可以逐步观察顺序栈的执行过程：
操作详解
入栈操作
将新元素压入栈顶。入栈前必须判断栈是否已满（栈满上溢）。
关键步骤（top = -1 约定）：
- 判断栈是否已满（
top == MaxSize - 1） - 栈顶指针加 1（
++top） - 将新元素放入栈顶位置
c
// 入栈操作（top = -1 约定）
bool Push(SqStack *S, int x) {
if (S->top == MaxSize - 1) // 栈满，上溢
return false;
S->data[++S->top] = x; // 先移指针，再赋值
return true;
}出栈操作
弹出栈顶元素。出栈前必须判断栈是否为空（栈空下溢）。
关键步骤（top = -1 约定）：
- 判断栈是否为空（
top == -1） - 取出栈顶元素
- 栈顶指针减 1（
top--）
c
// 出栈操作（top = -1 约定）
bool Pop(SqStack *S, int *x) {
if (S->top == -1) // 栈空，下溢
return false;
*x = S->data[S->top--]; // 先取值，再移指针
return true;
}获取栈顶元素（Peek）
仅读取栈顶元素，不修改栈顶指针，栈的状态不变。
c
// 获取栈顶元素
bool GetTop(SqStack S, int *x) {
if (S.top == -1)
return false;
*x = S.data[S.top]; // 只读取，不移动指针
return true;
}复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 入栈（Push） | O(1) | 直接在栈顶插入，无需移动元素 |
| 出栈（Pop） | O(1) | 直接删除栈顶元素，无需移动元素 |
| 获取栈顶（GetTop） | O(1) | 直接通过 top 访问 |
| 判空/判满 | O(1) | 只需比较 top 的值 |
空间复杂度：O(1)，所有操作只需常数级辅助空间。
与顺序表对比：顺序表的插入/删除需要 O(n) 时间移动元素，而栈由于只在一端操作，所有操作均为 O(1)。
考研高频考点
- ⭐ 出栈序列的合法性判断（给定入栈顺序 1,2,3,...,n，判断某个出栈序列是否合法，选择题超高频）
- ⭐
top初始值不同时入栈/出栈代码的区别（top=-1vstop=0，选择题常见陷阱） - ⭐ 栈的应用：括号匹配、表达式求值（中缀转后缀）、递归调用栈（综合题/选择题）
- n 个不同元素的合法出栈序列总数 = 卡特兰数 C(2n,n)/(n+1)（填空题）
- 共享栈：两个栈共享一个数组，栈底分别在两端，栈满条件为
top1 + 1 == top2 - 顺序栈 vs 链栈对比：顺序栈需预分配空间，可能上溢；链栈动态分配，不会上溢但每个节点有指针开销