空の領域

又一个坑爹的神站 大人說:要清爽 要低調

0%

[大计基础]关于栈的进出

首先我们来看一个模型:

zhan-1

(这个模型我也画了好一会儿……)我们把栈想象成一段不封口的容器,元素想象成木块。

题目如:

设栈S的初始状态为空,元素a,b,c,d,e,f,g依次入栈,以下出栈序列不可能出现的是( )。

>

A.a,b,c,e,d,f,g B.b,c,a,f,e,g,d C.a,e,d,c,b,f,g

D.d,c,f,e,b,a,g E.g,e,f,d,c,b,a

这里简化为,设栈初始状态为空,元素a,b,c,d依次入栈,问出栈

这里刚开始我也没搞明白,一直觉得既然入栈顺序固定,那么出栈顺序不应该也固定下来了吗,其实并不是这个意思。

zhan-2

放入A后,我们有两种选择——放入B或者让A出栈,假设放入B,再让B出栈,那么当B出栈后,A也可以随后出栈(如同建立的模型一样,只有拿掉上面的木块才能取走下面的),入栈顺序固定了,但中间还是空白的,你可以随时选择出栈这个操作。这样题目就变成了类似树形图一样的分支讨论,作为选择题,也可以很快速的判断出结果了,而不需要画出树形图。

至于图片的英语部分,只是我觉得中文不好看……仅此而已……

欢迎关注我的其它发布渠道