栈的应用实例-C++语言

例12－1　已知栈S的入栈序列为{'a'，'b'，'d'，'c'，'e'}，求其出栈序列。分析:根据栈的“先进后出”的特点可知，出栈序列应为'e'，'c'，'d'，'b'，'a'。

例12－2　已知一个栈的入栈序列为{1，2，3，4，5，6，7}，经过如下对该栈的操作:

入栈、入栈、入栈、出栈、入栈、入栈、出栈，求出栈序列。

分析:根据题意可知，入栈和出栈操作如下:

入栈　入栈　入栈　出栈　入栈　入栈　出栈

1　 2　 3　 3　 4　 5　 5

所以出栈序列为{3，5}。

例12－3　给定一个栈，入栈序列为{1，2，3，4，5}，则不可能的出栈序列为(　)。

A.{1，2，3，4，5}　 B.{2，1，4，3，5}

C.{5，4，3，2，1}　 D.{4，2，3，1，5}

分析:根据栈的先进后出的特点可知，

A选项对应的操作序列为:

入栈　出栈　入栈　出栈　入栈　出栈　入栈　出栈　入栈　出栈(www.xing528.com)

1　 1　 2　 2　 3　 3　 4　 4　 5　 5

B选项对应的操作序列为:

入栈　入栈　出栈　出栈　入栈　入栈　出栈　出栈　入栈　出栈

1　 2　 2　 1　 3　 4　 4　 3　 5　 5

C选项对应的操作序列为:

入栈　入栈　入栈　入栈　入栈　出栈　出栈　出栈　出栈　出栈

1　 2　 3　 4　 5　 5　 4　 3　 2　 1

D选项，要想4先出栈，操作序列必须为:

入栈　入栈　入栈　入栈　出栈

1　 2　 3　 4　 4

而下一个出栈的只能为3或者5，所以{4，2，3，1，5}序列不可能，因此本题选D。

例12－4　利用栈完成十进制数转换为二进制数。