进栈序列为1, 2, 3, 4, 进栈过程中可以出栈, 则下列不可能的出栈序列是(C)
A、1,2,3,4 B、2,3,1,4 C、3,1,2,4 D、4,3,2,1
[========]
栈是先进后出。
如果4先出,那么就是全部入栈了,只有4321一种情况。
如果3先出,那么4还没有入栈,此时栈内只有1,2,3,出栈必有3→2→1的顺序,4可以在3,2,1任意一个出栈后入栈,就有3421,3241,3214。
如果2先出,那么必有2→1的顺序,21都出栈后34才入栈,那么有2143和2134。2出栈后34都入栈,那么有2431和2341,2出栈后只有3入栈,那么是2314。
如果1先出,剩下的:2先出栈→243,234;3先出栈→342,324;4先出栈→432,那么就有1243,1234,1342,1324,1432。
答案是C,进栈的时候可以出栈,所以c选项3124,先进去123,然后出来3,再出来2,但是答案出来了1所以错
作者:知乎用户
链接:https://www.zhihu.com/question/432960938/answer/1606600651
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
标签:先出,进栈,出栈,入栈,进出,知乎,那么,数据结构
From: https://www.cnblogs.com/reallife/p/17277475.html