单项选择(2014年秋程序员软考)

对于一个初始为空的栈,其入栈序列为abc时,其出栈序列可以有【 】种。

A、3

B、4

C、5

D、6

答案解析

C

【解析】

入栈序列为abc时,出栈序列可以为abc、acb、bac、bca、cba,以I表示入栈、O对应出栈,原则是:每个元素仅入栈、出栈各1次;一次出栈操作的条件是栈不为空且只

能让栈顶元素出栈。

出栈序列为abc时,对应的操作序列为 IOIOIO。

出栈序列为acb时,对应的操作序列为 IOIIOO。

出栈序列为bac时,对应的操作序列为 IIOOIO。

出栈序列为bca时,对应的操作序列为IIOIOO。

出栈序列为cba时,对应的操作序列为IIIOOO。

在栈的合法操作序列中,其任何前缀部分中,出栈操作的次数都不多于入栈操作。

讨论