首页 > 试题广场 >

设栈 S 和队列 Q 的初始状态为空，元素 e1 、 e2

[单选题]

设栈 S 和队列 Q 的初始状态为空，元素 e1 、 e2 、 e3 、 e4 、 e5 和 e6 依次通过栈 S ，一个元素出栈后即进入队列 Q ，若 6 个元素出队的顺序是 e2 、 e4 、 e3 、 e6 、 e5 、和 e1 ，则栈 S 容量至少应该是

```
6
```
```
4
```
```
3
```
```
2
```

查看正确选项

NightJan

e1，e2进栈（同时存在2个e1,e2），e2出，

e3,e4进栈（同时存在3个e1,e3,e4）,e4,e3出，

e5,e6进栈（同时存在3个e1,e5,e6），e6,e5,e1出

综上，只要容量为3就行。

发表于 2017-11-06 11:07:28 回复(0)

__sgf__

栈+队列。这种题目队列的特点（先进先出）不影响顺序，所以可以先忽略队列再进行演算，看某一时刻栈中的最大数量是多少。

发表于 2022-01-08 18:15:55 回复(0)

Xer97

小技巧：

按出队列顺序遍历的每个元素，

判断当前元素之后有几(n)个元素在其原本入栈位置之前，依次判断每个元素，找出最大值MAXn

则栈的最小容量为MAXn+1

例如：

入栈顺序 a、b、c、d、e、f、g

出队列（也是出栈）顺序：b、c、f、e、g、d、a

① 出队列元素b，其后面只有a原本在它前面，则n=1；（b出栈时，a还驻留在栈中）

② 出队列元素c，其后面也只有a原本在它前面，则n=1；（c出栈时，a还驻留在栈中）

③ 出队列元素f，其后面有a、d、e原本在它前面，则n=3；（f出栈时，a、d、e还驻留在栈中，所以加上f容量总共为4）

④ e，...a、d...，n=2；

⑤ g，...a、d...，n=2；

⑥ d，...a...，n=1;

最大为3，因此最小容量为n+1=4；

以上是个人的脑回路，有什么错误欢迎指正。

发表于 2019-01-26 21:28:07 回复(1)

_void__

根据队列先进先出的特点，出栈的顺序就是出队的顺序，因此该题实际上考验的是栈的特性。而入栈时e1先入，最后出，因此整个顺序应该是：

e1入栈，e2入栈，e2出栈，e3入栈，e4入栈，e4出栈，e3出栈，e5入栈，e6入栈，e6出栈，e5出栈，最后e1出栈。

也就是说e1永远占着一个位置，e3和e4连续入栈出栈至少需要两个位置，所以总共至少需要3个位置。

发表于 2022-10-01 14:05:06 回复(0)

牛客852104548号

<p>出队的顺序是出队列的顺序吗，如果是的话应该选四个吧，</p>

发表于 2020-08-13 19:08:03 回复(0)

许愿建行拿到offer

e1,e2进栈，栈里有e1,e2,然后e2出栈；

e3,e4进栈，栈里有e1，e3，e4，然后e4，e3出栈；

e5，e6进栈，栈里有e1，e5，e6，然后e6，e5，e1出栈。

所以栈的容量是3

发表于 2019-11-09 22:08:28 回复(0)

提交观点

问题信息

栈

上传者：阿奻_

难度：

6条回答 87收藏 5852浏览

设栈 S 和队列 Q 的初始状态为空，元素 e1 、 e2

问题信息

热门推荐

相关试题