栈的基本概念

栈

栈(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. 只允许在两端操作

栈后进先出线性表

解题思路:

本题考查栈的基本特征。判断时抓住“栈只允许在一端(栈顶)进行插入和删除”这一操作限制,由此推出它的出栈次序一定是后进先出,再排除描述其他结构的选项。

详细步骤:

  1. 栈是一种操作受限的线性表,插入(入栈)和删除(出栈)都只能在栈顶一端进行。
  2. 由于最后入栈的元素最先出栈,栈的次序特征是后进先出(LIFO),选项 B 正确。
  3. 选项 A“先进先出”是队列的特点;选项 C“随机进出”违反了栈的操作限制;选项 D“只允许在两端操作”是双端队列的特点。

最终答案:

B。

习题 2

设栈的输入序列为 1、2、3,经过入栈出栈操作,不可能得到的出栈序列是( )

A. 3、2、1 B. 2、1、3 C. 3、1、2 D. 1、2、3

栈出栈序列后进先出栈操作模拟

解题思路:

本题要求判断哪个出栈序列不可能出现。方法是模拟入栈出栈过程:要让某个元素先出栈,必须先把它上面的所有元素都压入栈,因此可以利用栈顶只能是“最后入栈且尚未出栈的元素”这条约束来排除。

详细步骤:

  1. 若要 3 最先出栈,则 1、2、3 必须都已入栈,此时栈中自栈底到栈顶为 [1, 2, 3]。
  2. 3 出栈后栈顶变为 2,下一个出栈的只能是 2,不可能是 1。
  3. 因此序列 3、1、2 无法通过任何入栈出栈操作得到,是不可能的出栈序列。

最终答案:

C。

发现内容有问题?

告诉我们哪里需要改进。