设有n个元素进栈序列是P1，P2，P3，…，Pn，其输出序列是1，2，3

问题单项选择题

设有n个元素进栈序列是P1，P2，P3，…，Pn，其输出序列是1，2，3，…，n，若P3=3，则P1的值( )。

A．可能是2

B．一定是2

C．不可能是1

D．一定是1

答案

参考答案：A

解析：当P3=3时，进栈序列是P1，P2，P3，…，Pn，由输出序列可知，只有以下两种情况：P1进栈后出栈，P2进栈后出栈，或P1、P2都进栈然后出栈，因此P1的值可能为1，也可能为2。故选A。