单选题
设n个元素的进栈序列为1，2，3，…，n，其出栈序列是p
1
，p
2
，p
3
，…，p
n
，若p
1
=3，则p
2
的值为______；设n个元素的进栈序列为p
1
，p
2
，p
3
，…，p
n
，其出栈序列是1，2，3，…，n，若p
3
=1，则p
1
的值为______。
【正确答案】
B
【答案解析】[解析] 若用S表示进栈操作，用X表示出栈操作。在(1)的情形，如果进栈/出栈顺序是SSSXX…，则当p
1
=3时，p
2
=2；如果进栈/出栈顺序是SSSXSX…，类似情况还有，当p
1
=3时，p
2
=4，所以选B，p
2
可能是2，也可能是别的大于3的值。在(2)的情形，由于进栈序列是p
1
，p
2
，p
3
，…，且p
3
=1，而出栈序列是1，2，3，…，则下一个出栈的2可能是p
2
，也可能是p
4
，p
5
，…，但绝不可能是p
1
，所以选C。