课后作业

第二十九课

1. 有6个元素，按照6、5、4、3、2、1的顺序进入栈S，请问下列哪个出栈序列是非法的

• A. 543612
• B. 453126
• C. 346521
• D. 234156

上传请给出推导过程，不要只给出答案，比如，按照其顺序进入栈，然后按照其顺序出栈，看是否符合栈的特性，那一步出错了，要有解释, 本次作业直接上传图片，可以使用手机拍照上传，也可以使用电脑截图上传

• ✅
• 历史解析 结果是对的，推导也有对应选项的出入栈过程，但对于非法答案并没有给出解释，希望下次能够给出解释，比如因为6比5先压入，所以无法先弹出6再弹出5，我们解析也解析到这一步就足够了，后面的没必要在错误的情况下继续推断，整体解答正确💯

2. 对假设栈S和队列Q的初始状态为空。存在e1~e6六个互不相同的数据，每个数据按照进栈S、出栈S、进队列Q、出队列Q的顺序操作，不同数据间的操作可能会交错。已知栈S中依次有数据e1、e2、e3、e4、e5和e6进栈，队列Q依次有数据 e2、e4、e3、e6、e5和e1出队列。则栈S的容量至少是多少个数据

栈容量指的是栈中能存放的元素个数，比如一直入栈就出栈能完成所有操作的话，那么此栈的容量至少有1个就即可

• A. 2
• B. 3
• C. 4
• D. 6

上传请给出推导过程，不要只给出答案，比如，按照其顺序进入栈，然后按照其顺序出栈，看是否符合栈的特性，那一步出错了，要有解释, 本次作业直接上传图片，可以使用手机拍照上传，也可以使用电脑截图上传

• ✅

• 历史解析

  • 栈是后进先出（LIFO），队列是先进先出（FIFO）。
  • 已知队列的出队顺序，就是队列的入队顺序。而队列的入队顺序，就是栈的出栈顺序。所以该题变为：
    已知入栈顺序是：e1, e2, e3, e4, e5, e6，出栈顺序是：e2, e4, e3, e6, e5, e1，请问在整个入栈出栈过程中栈中元素的最大个数是多少？
  • 根据入栈出栈顺序，可知：

  操作	栈内情况（左侧是栈底）	出栈序列
  e1入栈	e1
  e2入栈	e1, e2
  e2出栈	e1	e2
  e3入栈	e1, e3	e2
  e4入栈	e1, e3, e4	e2
  e4出栈	e1, e3	e2, e4
  e3出栈	e1	e2, e4, e3
  e5入栈	e1, e5	e2, e4, e3
  e6入栈	e1, e5, e6	e2, e4, e3
  e6出栈	e1, e5	e2, e4, e3, e6
  e5出栈	e1	e2, e4, e3, e6, e5
  e1出栈		e2, e4, e3, e6, e5, e1

  根据上表可知，栈中最大元素数量为3

  • 整体解答正确💯