栈的压入与弹出序列

要求：

给定压栈序列，如何判断弹栈序列是否合法，例如：
压栈序列：1，2，3，4，5
弹栈序列：4，5，3，2，1 就是合法
弹栈序列：4，5，3，1，2 就是不合法

做法：

1. 初始化一个栈s和指针k，k用于遍历压栈序列，遍历弹栈序列，如果s非空且弹栈序列元素与s栈顶元素相同，就弹栈；
2. 如果上述条件不成立，遍历压栈序列，如果压栈序列元素与弹栈序列元素相同时，则k++，跳出当前循环；否则将压栈元素压入栈中，k++,继续遍历；当k大于等于数组长度时，则返回false；
3. 如果压栈序列遍历完成，则返回true；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <stack>
using namespace std;
class Solution{
public:
    bool TestValidPushAndPop(int pushSequence[],int popSequence[],int n){
        int k = 0;
        stack<int> s;
        for (int i=0; i<n; i++) {
            if (!s.empty()&&popSequence[i]==s.top()) {
                s.pop();
            }else{
                while (true) {
                    if (k >= n) {
                        return false;
                    }else{
                        if (pushSequence[k]==popSequence[i]) {
                            k++;
                            break;
                        }else{
                            s.push(pushSequence[k]);
                            k++;
                        }
                    }
                }

            }
        }
        return true;
    }


};
int main(int argc, const char * argv[]) {
    Solution* s = new Solution();
    int push[] = {1,2,3,4,5};
    int pop[] = {4,5,3,2,1};
    cout<<s->TestValidPushAndPop(push, pop, 5)<<endl;
    return 0;
}

Comments