题26

题26

题目

【2009 统考真题】设栈 和队列 的初始状态均为空,元素 abcdefg 依次进入栈 S.
若每个元素出栈后立即进入队列 ,且 7 个元素出队的顺序是 bdcfeag,则栈 的容量至少是 ( ).
A. 1
B. 2
C. 3
D. 4

分析

解

C

• 栈的特点是先进后出
• 下表是出入栈的详细过程
  • 序号1：a 入栈
  • 序号2：b 入栈
  • 序号3：b 出栈
  • 序号4：c 入栈
  • 序号5：d 入栈
  • 序号6：d 出栈
  • 序号7：c 出栈
  • 序号8：e 入栈
  • 序号9：f 入栈
  • 序号10：f 出栈
  • 序号11：e 出栈
  • 序号12：a 出栈
  • 序号13：g 入栈
  • 序号14：g 出栈
• 栈内的最大深度为 3
• 栈 S 的容量至少是 3
• 元素的出队顺序和入队顺序相同
• 元素的出栈顺序就是 b d c f e a g
• 元素的出入栈次序为
  • Push(S a)
  • Push(S b)
  • Pop(S b)
  • Push(S c)
  • Push(S d)
  • Pop(S d)
  • Pop(S c)
  • Push(S e)
  • Push(S f)
  • Pop(S f)
  • Pop(S e)
  • Pop(S a)
  • Push(S g)
  • Pop(S g)
• 初始所需容量为 0
• 每做一次 Push 操作 容量加 1
• 每做一次 Pop 操作 容量减 1
• 记录的容量最大值为 3