数据结构 | 每日一练（90）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1. 假设以 S 和 X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由 S 和 X 组成的序列表示（SXSX）。

（1）试指出判别给定序列是否合法的一般规则。

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。

2. 有 5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈（即C 第一个且 D 第二个出栈）的次序有哪几个？

3. 如果输入序列为 1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2 和 1 3 5 4 2 6;请说明为什么不能或如何才能得到。

正确答案

PS：||代表注释

1、（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。

（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列；对于合法序列BAC，我们使用SS××S×操作序列。

2、三个：CDEBA，CDBEA，CDBAE

3、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。