栈的基本概念
栈
栈（Stack）是一种后进先出（Last In First Out，简称 LIFO）的线性表，只允许在一端（称为栈顶，top）进行插入和删除操作。
- 插入操作称为入栈（push）
- 删除操作称为出栈（pop）
- 不含任何元素的栈称为空栈
栈的特点
- 后进先出（LIFO）：最后入栈的元素最先出栈
- 操作受限：只能在栈顶插入和删除，不能像线性表那样在任意位置操作
- 栈底固定：栈底位置不变，栈顶随操作动态变化
栈的基本操作
| 操作 | 说明 |
|---|---|
InitStack(&S) | 初始化空栈 |
StackEmpty(S) | 判断栈是否为空 |
Push(&S, x) | 元素 x 入栈 |
Pop(&S, &x) | 栈顶元素出栈，用 x 返回 |
GetTop(S, &x) | 读取栈顶元素，用 x 返回（不出栈） |
习题
习题 1
栈的特点是（ ）
A. 先进先出 B. 后进先出 C. 随机进出 D. 只允许在两端操作
答案与解析
答案：B
解析：栈是后进先出（LIFO）的线性表，只允许在栈顶一端进行插入和删除。A 是队列的特点，D 是双端队列的特点。
习题 2
设栈的输入序列为 1、2、3，经过入栈出栈操作，不可能得到的出栈序列是（ ）
A. 3、2、1 B. 2、1、3 C. 3、1、2 D. 1、2、3
答案与解析
答案：C
解析：若要 3 第一个出栈，则 1、2、3 必须都已入栈（此时栈为 [1,2,3]），之后 3 出栈，栈顶为 2，只能 2 再出栈，不可能 1 先出。所以 3、1、2 不可能。