设n个元素的进栈序列是p1、p2、p3、…、pn,其输出序列是1、2、3、…、n,若pn=1,则pi(1≤i≤n-1)的值是(n-i+1 ) 。
时间: 2023-12-28 07:14:13 浏览: 22
栈的顺序实现,入栈、出栈等
假设当前还未入栈的元素中,最小的元素在进栈序列中的位置是k,则前k-1个元素都已经入栈,并且已经按照从小到大的顺序出栈。因此,在输出序列中,前k-1个元素都是按照从小到大的顺序出现的,分别是1、2、3、…、k-1。
当第k个元素入栈时,由于它比前面的元素都大,因此无法出栈。因此,在输出序列中,第k个元素之前的元素都已经按照从小到大的顺序出现,而第k个元素之后的元素都是在第k个元素出栈之后才出现的。而第k个元素出栈的时机是在当前未入栈元素中,第一个比它大的元素入栈之后。因此,如果pn=1,则pi(1≤i≤n-1)的值应该是在当前未入栈元素中,第一个比pn=1大的元素在进栈序列中的位置与k的差值再加1,即n-k+1。
综上所述,如果pn=1,则pi(1≤i≤n-1)的值是n-k+1,其中k表示当前未入栈元素中,最小的比pn大的元素在进栈序列中的位置。
阅读全文