栈的进出序列问题

       一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是(     )

B. 5 4 1 3 2    C. 2 3 1 4 5 D. 1 5 4 3 2

      入栈序列为 1 ，2 ，3， 4， 5，其出栈序列不止一个，这五个元素中的任意一个都可以作为第一个出栈的元素，假设3是第一个出栈的元素，可以肯定，第二个出栈的元素可以为4,5中的任意一个，也可以为2，但不能为1，因为3出栈后，栈顶元素是2。

      本篇文章要介绍的算法很简单

      首先，将出栈序列反向的压入一个栈，称之为s2，这时，第一个出栈的元素就在栈顶

      接下来，将入栈序列的元素逐个压入栈s1，每一次压入一个元素后，就检查s1,和s2的栈顶元素是否相同，如果相同，则两个栈都将栈顶元素弹出，直到两个栈的栈顶元素不相同

      入栈序列都压入后，如果两个栈都是空的，说明，出栈序列正确，反之错误

bool MyAlgorithm::IsPopOrder(int order1[],int iLen1,int order2[],int iLen2)
  {
    stack<int> s1;
    stack<int> s2;

    // 出栈序列反向入栈
    for(int i=iLen2-1;i>=0;i--)
    {
      s2.push(order2[i]);
    }

    for(int i =0;i<iLen1;i++)
    {
      s1.push(order1[i]);
      // 如果当前入栈序列的栈顶和出栈序列的栈顶相同，则两个栈都向外弹
      while(!s1.empty()&&!s2.empty()&&s1.top()==s2.top())
      {
        s1.pop();
        s2.pop();
      }
    }

    if(s1.empty() && s2.empty())
    {
      return true;
    }

    return false;
  }