栈的基本概念
定义
定义是对概念、术语或对象含义的精确描述。理解定义是学习任何知识领域的基础,每个概念都有其明确的定义。
栈
栈(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. 只允许在两端操作
解题思路:
本题考查栈的基本特征。判断时抓住“栈只允许在一端(栈顶)进行插入和删除”这一操作限制,由此推出它的出栈次序一定是后进先出,再排除描述其他结构的选项。
详细步骤:
- 栈是一种操作受限的线性表,插入(入栈)和删除(出栈)都只能在栈顶一端进行。
- 由于最后入栈的元素最先出栈,栈的次序特征是后进先出(LIFO),选项 B 正确。
- 选项 A“先进先出”是队列的特点;选项 C“随机进出”违反了栈的操作限制;选项 D“只允许在两端操作”是双端队列的特点。
最终答案:
B。
习题 2
设栈的输入序列为 1、2、3,经过入栈出栈操作,不可能得到的出栈序列是( )
A. 3、2、1 B. 2、1、3 C. 3、1、2 D. 1、2、3
解题思路:
本题要求判断哪个出栈序列不可能出现。方法是模拟入栈出栈过程:要让某个元素先出栈,必须先把它上面的所有元素都压入栈,因此可以利用栈顶只能是“最后入栈且尚未出栈的元素”这条约束来排除。
详细步骤:
- 若要 3 最先出栈,则 1、2、3 必须都已入栈,此时栈中自栈底到栈顶为 [1, 2, 3]。
- 3 出栈后栈顶变为 2,下一个出栈的只能是 2,不可能是 1。
- 因此序列 3、1、2 无法通过任何入栈出栈操作得到,是不可能的出栈序列。
最终答案:
C。
