习题三
(1)给定操作序列P1P2P3…P i…P n（P k为S或X，k=1,2,…n ）是合法
的，当且仅当满足下列条件：
a. 序列中包含的S的个数和X的个数相等；
b. 对于任意的j（1≤j≤n）；有P1P2P3…P j子序列中所包含的S
的个数大于等于X的个数；
(2)
证明：设P1P2P3…P i…P n ，Q1Q2Q3…Q i…Q n是两个不同的合法序列；
∵两者不同，
∴ k=min{i| P i≠Q i , 1≤i≤n }且k>1，P k≠Q k（因P1，Q1肯定是S，否则不合法！）
即，P1P2P3…P k-1 和Q1Q2Q3…Q k-1是相等的，但P k≠Q k
由此可知：两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同，由于P k≠P k不妨设P k=X，而Q k=S；
这样，在操作序列P1P2P3…P i…P n中的第k-1步后输出的第一个元素是目前栈中的元素，而对于操作序列Q1Q2Q3…Q i…Q n中的第k-1步后输出的第一个元素是目前还在栈外的元素。

所以输出序列不同。

即两个不同的合法操作序列，不可能得到相同的输出序列。

证毕！
用反证法
证明：假设存在这样的输出序列，P1…P i…P j…P k…Pn，满足i<j<k,使P j<P k<P i;
因P i在这三个数中最大，且P i最先出栈，按照题意所给进栈顺序，在P i 出栈时P j和P k都还在栈中；
又因，P j<P k，所以P j比P k先进栈，则出栈顺序应该是P k先出栈而不是P j先出栈，矛盾！
证毕！
(1) 输出序列为：0,5,9,12,14,15
(2)由于输入的数据个数不定，采用单链表存储输入的元素，又因是先输入的，后累加到累加器里，所以用链栈的形式存储。

（类型定义与书本上第二章相同）void test( )
{
LinkList L ,P;
int x,sum;
L=NULL;。