问题

判断一数字序列是否为这些数字入栈的一种出栈方式（前提：栈中的数字不重复）

例如

假设入栈的序列为：1 2 3 4 5

那么4 5 3 2 1为一种弹出序列， 4 3 5 1 2不是

思路

开辟一个辅助栈，模拟入栈出战过程(假设pa为入栈序列，pb为出战序列)

• pa中的元素依次压入辅助栈
• 新压入的元素与弹出序列的栈底相同，辅助栈弹出，同时pb向上移动
• 不相同了pa中的元素继续入辅助栈

参考代码

#include 
     
      #include 
      
       using namespace std;bool IsPopOrder(const int *a, const int *b, int lena, int lenb){    if(lena != lenb || lena == 0)        return false;    bool rev = false;    int pa = 0;    int pb = 0;    int *newa = new int[lena];    int top = -1;    for(pa = 0; pa < lena; ++pa)    {        ++top;        newa[top] = a[pa];        while(newa[top] == b[pb])        {            --top;            ++pb;        }    }    if(top == -1)        rev = true;    delete []newa;    return rev;}int main(){    int a[] = {
   1, 2, 3, 4, 5};    int b[] = {
   4, 5, 3, 2, 1};    int c[] = {
   4, 3, 5, 1, 2};    int d[] = {
   4, 5, 9, 2, 1};    int lena = sizeof(a) / sizeof(int);    int lenb = sizeof(b) / sizeof(int);    int lenc = sizeof(c) / sizeof(int);    int lend = sizeof(d) / sizeof(int);    cout << IsPopOrder(a, b, lena, lenb) << endl;    cout << IsPopOrder(a, c, lena, lenc) << endl;    cout << IsPopOrder(a, d, lena, lend) << endl;}
      
     

结果

1

0

0