【数据结构】关于进出栈的问题

来源：百度知道 编辑：UC知道 时间：2024/05/15 09:00:00
对于一个栈，给出输入项A、B、C，如果输入项序列
由ABC组成，试给出所有可能的输出序列。
A进 A出 B进 B出 C进 C出 ABC
A进 A出 B进 C进 C出 B出 ACB
A进 B进 B出 A出 C进 C出 BAC
A进 B进 B出 C进 C出 A出 BCA
A进 B进 C进 C出 B出 A出 CBA

不可能产生输出序列CAB

为什么不可能产生输出序列CAB，这个是怎么判断的

先假设输出就是CAB：
那么在C出栈之前不能有任何数据出栈，也就是说第一个出栈的应是C
出栈后新的栈的栈顶为B，
则根据FILO（先进后出）原则这样，第二个出栈的必为B，最后一个为A

C出时，栈中必然有AB，其中B是栈顶，所以此时C后只能弹出B，因此CAB不成立。