题目来源于王道论坛设栈S和队列Q的初始状态均为

[单选题]

题目来源于王道论坛

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

```
1
```
```
2
```
```
3
```
```
4
```

推荐

林呼

解析：

由于队列的特点是先进先出，即栈S的出栈顺序就是队Q的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。

序号	说明	栈内	栈外	序号	说明	栈内	栈外
1	a入栈	a		8	e入栈	ae	bdc
2	b入栈	ab		9	f入栈	aef	bdc
3	b出栈	a	b	10	f出栈	ae	bdcf
4	c入栈	ac	b	11	e出栈	a	bdcfe
5	d入栈	acd	b	12	a出栈		bdcfea
6	d出栈	ac	bd	13	g入栈	g	bdcfea
7	c出栈	a	bdc	14	g出栈		bdcfeag

栈内的最大深度为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，所以选C。

发表于 2018-09-11 19:02:34 回复(1)