最近在准备软中,复习一下数据结构

 

作者:xiaoyuntech
链接:https://blog.csdn.net/xiaoyuntech/article/details/68485689
來源:CSDN

 

Q:ABCDE入栈,不可能的出栈次序是?

 

如果要列出所有可能的次序再去判断不可能的次序是一件成本非常高的事情。

所以这里面一定是有规律的。

试想,如果A是要在第一个出栈要怎么做:那定是A入栈,下一步就得立即出栈;如果B是要在第一出栈怎么做,那定是AB一起入栈后立即把B出栈。

所以规律是:

答案中出栈的第一个元素是在原来的次序中是第几个,那么他的前面的元素必然都还在栈中。

如EDCBA是可能的,因为E在第一个,E是原序列中的最后一个,那ABCD必在栈中只能按栈规则出,即DCBA。

如DCEAB的顺序是不可能的,因为如果D是首个,那么ABC必在栈中,无论E在什么时候入栈和出栈,D之后的出栈顺序必有CBA的大致顺序,而非CAB。

 

分类: 学习

发表评论

电子邮件地址不会被公开。 必填项已用*标注