已知一个栈的进栈序列是 1、2、3、…、n，其输出序列为 p₁、p₂、p₃、…、pₙ，若 p₁=3，则 p₂ 为（ ）。

A. 2 或 4、5、…、n 都有可能 B. 可能是 1 C. 一定是 2 D. 只可能是 2 或 4

栈 入栈出栈序列

[tag_link]

正确答案：A

已知进栈序列为1,2,3,…,n，且第一个出栈元素p₁=3。 根据栈的后进先出特性，为了使得3第一个出栈，操作序列必须是：先将1和2依次进栈，然后将3进栈并立即出栈。 此时栈中剩余元素为1和2（2在栈顶），且后续元素4,5,…,n尚未进栈。

对于第二个出栈元素p₂，存在两种可能：一是直接出栈当前栈顶元素2，则p₂=2； 二是暂不出栈2，而是将后续元素4,5,…,n依次进栈，并在进栈过程中或进栈后出栈某个元素，此时p₂可以是4,5,…,n中的任意一个。 需要注意的是，p₂不可能是1，因为1位于栈底，必须等待其上方所有元素出栈后才能出栈，而p₂是第二个出栈元素，若不出栈2则无法触及1。 因此，p₂可能是2或4,5,…,n中的任意值，与选项A相符。