问题描述：12345按顺序入栈，合法的的出栈顺序？                    元素的出栈、入栈顺序的合法性。           如： 入栈序列（1，2，3，4，5）                   出栈序列（4，5，3，2，1）

• 顺序入栈 

该数据入栈前 已入栈 待入栈 1   2，3，4，5 2 1 3，4，5 3 1，2 4，5 4 1，2，3 5 5 1，2，3，4  

• 合法出栈    

出栈序列的第一个元素 含义 1 1入栈即出栈 2 1，2入栈后才有出栈行为 3 1，2，3入栈后有出栈行为 4 1，2，3，4入栈后有出栈行为 5 1，2，3，4，5入栈后有出栈行为
      本题的难点在于元素入栈后是立即出栈还是接着入栈。

• 当入栈序列为（1，2，3，4，5）时，计算一下有多少种合法出栈序列——42种？

• 1入栈即出栈——14种

1-2-3-5-4    1-2-3-4-5 1-2-4-3-5 1-2-5-4-3 1-2-4-5-3
1-3-2-4-5 1-3-2-5-4 1-3-4-5-2 1-3-5-4-2 1-3-4-2-5
1-4-3-2-5 1-4-3-5-2 1-4-5-3-2
1-5-4-3-2

• 1，2入栈有出栈动作——14种

2-1-3-4-5 2-1-3-5-4 2-1-4-5-3 2-1-4-3-5 2-1-5-4-3
2-3-1-5-4 2-3-1-4-5 2-3-4-1-5 2-3-4-5-1 2-3-5-4-1
2-4-3-1-5 2-4-5-3-1 2-4-3-5-1
2-5-4-3-1

• 1，2，3入栈有出栈动作——9种

3-2-1-4-5 3-2-1-5-4   3-2-4-5-1 3-2-5-4-1 3-2-4-1-5
3-4-5-2-1 3-4-2-1-5 3-4-2-5-1
3-5-4-2-1

• 1，2，3，4入栈有出栈动作——4种

4-3-2-1-5 4-3-5-2-1 4-3-2-5-1
4-5-3-2-1

• 1，2，3，4，5入栈有出栈动作——1种

          5-4-3-2-1

• 合法出栈序列的规律  

         ·对于出栈序列中的每一个数字，在它后面&比它小的所有数字——按递减顺序排列。

• 实现思路  

• 最初栈为空，1入栈  sourse++

         

• 此时栈顶元素不等于出栈序列的首位元素，并且入栈序列不为空，继续入栈，直至匹配。

          

• 此时栈顶元素等于出栈序列首位元素，当前出入栈匹配。  

          

• 进行出栈操作，出栈序列指针向后指一位。

         

• 判断当前栈顶元素不等于出栈序列首位元素且入栈序列不为空，继续入栈。此时栈顶元素等于出栈序列首位元素，栈进行出栈操作。直至匹配完毕。

         

• 如下图所示

                 可见出入栈序列匹配必须保证栈为空，入栈序列为空，出栈序列为空。                  若入栈序列为空，栈顶元素不等于出栈序列第一个元素，即不匹配。该出栈序列不是入栈序列的合法出栈。
         

• 代码

#include #include using namespace std ; #define MAX_SIZE 10 template < class T > class SeqStack { public : SeqStack () : _top(- 1 ) , _capacity ( MAX_SIZE) { _stack = new T [_capacity ]; if ( NULL == _stack) { exit (-1 ); } } ~SeqStack () { delete []_stack ; } public : T Pop () { //栈空结束程序 if ( Empty ()) { exit (-1 ); } //若栈不空返回栈顶元素 return _stack [ _top--]; } void Push ( const T & elem ) { //栈满结束程序 if ( Full ()) { exit (-1 ); } _stack [++_top ] = elem; } T GetTop () { //若栈不空返回栈顶元素 if ( Empty ()) { exit (-1 ); } return _stack [ _top]; } bool Empty () const { return _top == - 1; } bool Full () const { return _top == _capacity - 1; } private : int _top ; //栈顶指示 T * _stack ; //顺序栈 int _capacity ; //栈可容纳元素 }; bool IsLegal( char * sourse , char * dest ) { SeqStack ss ; if ( strlen (sourse ) != strlen( dest )) { return false ; } ss .Push (* sourse++); //第一个元素入栈 while (* dest != '