题源：《数据结构1800题》第四版 P45

1. 判断题：同一组不重复输入序列执行不同的出入栈组合操作，所得结果也可能相同。（北京邮电大学，2005）

答案：√

分析：这道题之前已经有人讨论过，可以参考：《V2EX：一个算法题请教…》，看来确实有一些争议，下面以我的理解分析一下。

首先，本题 并未说明说初态和终态是否为空，而在 终态栈非空 的情况下，也就是说，并不需要所有元素都出栈，这样的话，留给我们的发挥空间就比较大了。

例如，输入序列为：1 2 3 4

操作①：push pop，输出序列：1
操作②：push pop push push，输出序列：1

你看，确实是两种不同的操作序列吧，也确实得到了相同的输出序列吧。那么本题的这句话确实是正确的，书上给的答案是没问题的。

---

2. 判断题：即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（北京邮电大学，1999；中国海洋大学，2005）

答案：×

分析：本题在答案上没有什么争议，肯定是选 ×，就不举例说明了。但是估计很多人看到 也一定相同 这个描述会感到疑惑，给人感觉如果写成 可能相同 ，这句话就应该是对的。实际上如果改成 可能相同 的话，本题就与上一题一样了。再一次印证了上一题答案是 √。

---

3. 应用题：

假设以 S 和 X 分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由 S 和 X 组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）（东南大学，1992）

（1）试给出区分给定序列为合法序列或非法序列的一般准则

（2）两个不同的合法（栈操作）序列（对同一输入序列）能否得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列？如能得到，请举例说明。

《1800题》书上的答案：

对于以上答案第（2）问我不认同，因为题目中已经明确说明了是 对同一输入序列，但答案说的是 两个不同的输入序列，明显是答非所问了。

一个在我看来较为合理的解答：

（1）区分准则：

• 给定序列中 S 的个数和 X 的个数相等
• 从给定序列开始，到给定序列中的任一位置，S 的个数要大于等于 X 的个数。

（2）不能得到相同的输出元素序列。证明过程如下：

思路来源：《数据结构习题集》答案解析-严蔚敏吴伟民版，第3章 栈和队列

设两个合法序列为：

T1 = S……X……S……
T2 = S……X……X……

假定前 n 个操作都相同，从第 n+1 个操作开始，为序列不同的起始操作点。由于前 n 个操作相同，故此时两个栈（不妨为栈 A、B）的存储情况完全相同，假设此时栈顶元素均为 a。

第 n+1 个操作不同，不妨 T1 的第 n+1 个操作为 S，T2的第 n+1 个操作为 X。T1 为入栈操作，假设将 b 压栈，则 T1 的输出顺序一定是先 b 后 a；而 T2 将 a 退栈，则其输出顺序一定是先 a 后b。

由于 T1 的输出为……ba……，而 T2 的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。