Question

数据结构题，扳道栈

2. 若对编号为1、2、3的列车车厢依次通过扳道栈进行调度，不能得到序列为（C）
A.1 2 3 B.1 3 2 C.3 1 2 D. 2 3 1

这道题晚上答案就是不能得到 312
但是我不理解什么是扳道栈？请大神清晰说一下原因？谢谢！

Answer 1

1、就是考察“栈”，所谓栈就是限定仅在表尾进行插入或删除的线性表，又称为先进后出或后进先出；

2、若对编号为1、2、3的列车车厢依次通过扳道栈进行调度，不可能得到序列 3 1 2；
因为3先出来的，表示1刚开始是没有出来的，所以1不可能比2先出来！

追问

您说的我理解了。既然是 1,2,3 依次进，按说出来应该是 3,2,1 ，那为什么 A，B，D 能够得到？想不明白这三项是怎么个出来方法？如果可以画图更好

追答

A. 1 2 3 表示的意思是：1先放进栈中再取出，依次2放进栈中再取出，依次3放进栈中再取出——得到序列 1 2 3；
B.1 3 2 表示的意思是：1先放进栈中再取出，依次把2和3都放进栈中在取出，取出顺序是后进先出，所以3先取出再取出2——得到序列1 3 2；
D.2 3 1 表示的意思是：依次把1和2放入栈中，先取出2，再把3放入栈中，取出3，再取出1——得到序列2 3 1；
C. 3 1 2 表示的意思是：依次把1和2和3放入栈中，先取出3，这时表尾是2，没办法先取出1再取出2，所以无法得到序列 3 1 2；

追问

哦，明白了，就是说先取出x，则必按照题干所说顺序先放进去x及他之前的元素，然后变通那个方法取。由衷感谢，不吝赐教！