设栈 S 和队列 Q 的初始状态均为空，元素a, b, c, d, e, f, g依次进入栈 S 。_

返回主页

[数据结构 P2007] 设栈 S 和队列 Q 的初始状态均为空，元素a, b, c, d, e, f, g依次进入栈 S 。

学习人数: 531

正确率: 91%

答案解析

题目描述

未通过

设栈 S 和队列 Q 的初始状态均为空，元素a, b, c, d, e, f, g依次进入栈 S 。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是b, d, c, f, e, a, g，则栈 S 的容量至少是（）。

A. 1

B. 2

C. 3

D. 4

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

1 个回答 (点击展开回答)

快乐小土狗

2024年1月3日 11:13

由于栈具有先进后出的特性,队列具有先进先出的特性,出队顺序即为人队顺序。在本题中,每个元素出栈 S后立即进入队列 Q出栈顺序即为入队顺序,所以本题中队列的作用形同虚设,根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程: 第一个出栈元素为b,表明栈内

还有元素a, b出栈前的深度为2;第二个出栈元素为d,栈内元素为a和c, d 出栈前的深度为 3; c 出栈后,剩余元素为 a,c 出栈前的深度为 2; f 出栈后, 剩余元素为a和e, f出栈前的深度为3; e出栈后,剩余元素为a, e出栈前的深度为2; a出栈后,无剩余元素,a出栈前的深度为1; g出栈后,无剩余元素, g 出栈前的深度为 1。所以栈容量至少是 3。