问题描述
这个问题经过我的思考，其实解法更加简单
一般性的问题是：有一组数和一个栈，给定这组数的入栈顺序，判断哪些出栈序列是不可能的。
譬如，对于1 2 3 4 5， 出栈序列4 5 3 2 1就是可能的
对应的操作如下：
1.压入 1 2 3 4
2.弹出 4
3.压入 5
4.弹出剩余的元素
问题是，这些操作序列是怎么得到的？
解法
使用两个队列和一个栈实现，如下图所示
示意图
入栈序列代表了入栈的顺序，一般就是题目给定的数。队列首部是第一个入栈的数。
临时栈用来临时存放入栈但是尚未弹出栈的数。
出栈序列就是结果。
一般的问题是已知入栈序列和出栈序列，判断出栈序列是否可能。
步骤：
- 将给定的数按顺序放入入栈序列
- 依次分析出栈序列的首部（第一个数）k，为了k第一个出栈，入栈序列中k以及k之前的所有数必须入栈，然后弹出k
- 如果k不存在于入栈序列中，k必然是栈顶元素，弹出k即可
- 如果k既不在栈顶也不在入栈序列中，则出栈序列不可能
以入栈序列 1 2 3 4 5，出栈序列4 5 3 2 1为例，过程如下:
为了使4第一个出栈所做的操作
余下的操作，使5入栈，然后弹出5，然后弹出所有元素。结果就是4 5 3 2 1
网友评论