Question

对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有（ ）种。

A.3
B.4
C.5
D.6

Answer 1

【答案】：C
本题考查数据结构基础知识。
入栈序列为abc时，出栈序列可以为abc、acb、bac、bca、cba，以I表示入栈、O对应出栈，原则是：每个元素仅入栈、出栈各1次；一次出栈操作的条件是栈不为空且只能让栈顶元素出栈。
出栈序列为abc时，对应的操作序列为IOIOIO。
出栈序列为acb时，对应的操作序列为IOIIOO。
出栈序列为bac时，对应的操作序列为IIOOIO。
出栈序列为bca时，对应的操作序列为IIOIOO。
出栈序列为cba时，对应的操作序列为IIIOOO。
在栈的合法操作序列中，其任何前缀部分中，出栈操作的次数都不多于入栈操作。