若己知一个栈的进栈序列pl,p2,p3,,pn,输出序列是1,2,3,..,n。若pn=1,则pi(1<=i<n)为(
时间: 2023-10-04 18:07:28 浏览: 134
判断出栈序列
根据题目描述,给定一个栈的进栈序列为p1,p2,p3,...,pn,其对应的出栈序列为1,2,3,...,n。如果pn=1,则pi的值可以确定。
根据栈的进出栈规则,每当一个元素被弹出栈时,其前面的所有元素都已经入栈。因此,如果pn=1,则pi必须是第一个入栈的元素,否则pi会在pn之后被弹出栈,无法满足1,2,3,...,n的出栈序列。因此,可以得出结论:如果pn=1,则pi=2。
具体证明方法如下:
1. 假设pn=1,但pi不等于2。则pi之前必须存在一个元素pj,其值大于2,否则2不能成为第一个出栈的元素,无法得到1,2,3,...,n的出栈序列。假设pj在位置k被弹出栈,则p1,p2,p3,...,pj-1均在k之前被弹出栈,pj,pj+1,...,pn均在k之后入栈。
2. 由于pi不等于2,因此pi在位置k之后入栈,那么p1,p2,p3,...,pi-1在位置k之前被弹出栈,p1,p2,p3,...,pi-1必须按照pi,p(i-1),...,p1的顺序被弹出栈,否则无法得到1,2,3,...,n的出栈序列。但是,pi在位置k之后入栈,说明在位置k之前已经存在了一个元素,其值大于pi,否则pi不会在位置k之后入栈。因此,p1,p2,p3,...,pi-1无法按照pi,p(i-1),...,p1的顺序被弹出栈,与前面的假设矛盾。
3. 综上所述,假设不成立。如果pn=1,则pi=2。
阅读全文