JZ-C-22

剑指offer第二十二题:栈的压入、弹出序列

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//============================================================================
// Name        : JZ-C-22.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 栈的压入、弹出序列
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include <stack>
using namespace std;
/**
 *给定两个整数序列,第一个序列表示栈的压入顺序,判断第二个序列是否会是该栈的弹出顺序
 */
bool IsPopOrder(const int* pPush, const int* pPop, int nLength) {
    std::stack<int> StackData; //辅助栈
    if (pPush != NULL && pPop != NULL && nLength != 0) {
        int pLength = nLength-1;//pLength指的是压入栈剩余未进辅助栈的数目
        StackData.push(*pPush);
        while (!StackData.empty()) { //每次将辅助栈的栈顶元素和弹出栈序列第一个数比较,直至全部比较完毕
            if (StackData.top() != *pPop && pLength > 0) {
                pPush++;
                StackData.push(*pPush);
                pLength--;
            } else if (StackData.top() != *pPop && pLength <= 0) {
                return false; //弹出栈序列有错误,直接退出循环
            } else {
                StackData.pop();
                pPop++;
                if(StackData.empty() && pLength > 0){//出栈后若辅助栈为空,继续压入‘压入栈序列’后续元素
                    StackData.push(*pPush);
                }
            }
        }
    } else {
        return false;
    }
    return true;
}
 
// ====================测试代码====================
void Test(char* testName, const int* pPush, const int* pPop, int nLength,
        bool expected) {
    if (testName != NULL)
        printf("%s begins: ", testName);
 
    if (IsPopOrder(pPush, pPop, nLength) == expected)
        printf("Passed.\n");
    else
        printf("failed.\n");
}
 
void Test1() {
    const int nLength = 5;
    int push[nLength] = { 1, 2, 3, 4, 5 };
    int pop[nLength] = { 4, 5, 3, 2, 1 };
 
    Test("Test1", push, pop, nLength, true);
}
 
void Test2() {
    const int nLength = 5;
    int push[nLength] = { 1, 2, 3, 4, 5 };
    int pop[nLength] = { 3, 5, 4, 2, 1 };
 
    Test("Test2", push, pop, nLength, true);
}
 
void Test3() {
    const int nLength = 5;
    int push[nLength] = { 1, 2, 3, 4, 5 };
    int pop[nLength] = { 4, 3, 5, 1, 2 };
 
    Test("Test3", push, pop, nLength, false);
}
 
void Test4() {
    const int nLength = 5;
    int push[nLength] = { 1, 2, 3, 4, 5 };
    int pop[nLength] = { 3, 5, 4, 1, 2 };
 
    Test("Test4", push, pop, nLength, false);
}
 
// push和pop序列只有一个数字
void Test5() {
    const int nLength = 1;
    int push[nLength] = { 1 };
    int pop[nLength] = { 2 };
 
    Test("Test5", push, pop, nLength, false);
}
 
void Test6() {
    const int nLength = 1;
    int push[nLength] = { 1 };
    int pop[nLength] = { 1 };
 
    Test("Test6", push, pop, nLength, true);
}
 
void Test7() {
    Test("Test7", NULL, NULL, 0, false); //这里若两栈均为空,判断为false
}
 
void Test8() {
    const int nLength = 5;
    int push[nLength] = { 1, 2, 3, 4, 5 };
    int pop[nLength] = { 1, 5, 4, 3, 2 };
 
    Test("Test8", push, pop, nLength, true);
}
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    Test8();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注