判断出栈顺序的合法性

      ”栈“是一种限制性线性表，是将线性表的插入、删除操作限制为仅在表的一端进行，一般将能够插入、删除的一端称为栈顶，表的另一端称为栈底。当栈中没有元素时称为空栈。即就是将每次进栈的元素放在栈顶元素之上而称为新的栈顶，而每次出栈的是当前栈中“最新”的元素。因此就需要对一些出栈顺序的合法性进行判断。这个也是面试会经常问到的问题。

◆主要思路：

       首先，需要一个栈s，给定两个序列，先将入栈序列的第一个数据与出栈序列的第一个数据相比较，若两个数据相同，再次将入栈序列的第二个数据和出栈序列的第二个数据进行比较，若两个数据不相同将入栈序列中的第一个数据压入s栈中，再次比较入栈序列的第二个数据和出战序列的第一个数据，若相同则继续比较两个序列中的下一个数据，若不相同再将入栈序列的第二个数据压入栈s中，同时重复执行上述的操作比较两个数据。当入栈序列遍历完成后，栈s为空，则出栈序列的顺序是合理的，否则，就是不合理的。

      下面是简要的图示：

下面是具体的程序代码：

//判断出栈、入栈的合法性？#include 
     
      using namespace std;#include 
      
       #include 
       
        #include 
        
         template
         
          class IsLegal{public:    IsLegal(const T* s1, const T* s2)    //构造函数       :str1(new T[strlen(s1)])       , str2(new T[strlen(s2)])    {        strcpy(str1, s1);        strcpy(str2, s2);    }     ~IsLegal()      //析构函数    {        if (str1 != NULL)       {           delete str1;        }        if (str2 != NULL)       {           delete str2;        }    }     public:    void judge(const T* str1, const T* str2)    {        assert(str1);        assert(str2);        stack
          
            s1;        while (*str1 != '\0')       {           if (*str1 != *str2)           {               s1.push(*str1);               str1++;            }           else if (*str1 == *str2)           {               s1.push(*str1);               while (!s1.empty())              {                  if (s1.top() != *str2)         //防止情况12345——43565                 {                     break;                 }                 s1.pop();                 str2++;               }               str1++;               str2++;            }        }        if (*str2 == '\0')       {           cout << "This is legal." << endl;        }        else       {           cout << "This is unlegal." << endl;        }    }    private:    T* str1;    T* str2;};int main(){    char* str1 = "12345";    char* str2 = "45321";        IsLegal
           
             s(str1, str2);    s.judge(str1, str2);        system("pause");    return 0;}