验证栈的出栈序列是否正确

发表于 | 分类于 | | 阅读次数:

思路：

遍历出栈序列，对于其中任一元素k，查看当前栈是否为空，若为空或栈顶元素不等于k，则根据入栈序列进行入栈，直至入栈序列中的元素k入栈。若直至入栈序列末尾仍无k，说明出栈序列错误。入栈完成后，将k出栈。
如上述操作，直至完成出栈序列遍历，说明出栈序列正确。
005203287

代码：

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
#include <stdlib.h> 
#include <stdio.h> 

struct Stack 
{ 
    int* base; 
    int* top; 
    int size;    
}; 

//初始化栈 
void Init(Stack &s) 
{ 
    s.base = (int*)malloc(sizeof(int)*100); 
    s.top = s.base; 
    s.size = 100; 
} 

//入栈 
bool Push(Stack &s,int n) 
{ 
    if (s.top-s.base >= s.size) 
    { 
        s.size = s.size + 10; 
        s.base = (int*)realloc(s.base,sizeof(int)*s.size); 
    } 
    *s.top = n; 
    s.top++; 
    return true; 
} 

//出栈 
bool Pop(Stack &s,int &n) 
{ 
    if (s.top==s.base) return false; 
    s.top--; 
    n = *s.top; 
    return true; 
} 

bool Top(Stack &s,int &n) 
{ 
    if (s.top==s.base) return false; 
    n = *(s.top-1); 
    return true; 
} 

bool Empty(Stack s) 
{ 
    if (s.top == s.base) return true; 
    else return false; 
} 

int main() 
{ 
    int i,number; 
    int* input; 
    int* output; 
    printf("input the number of the elements:\n"); 
    scanf("%d",&number); 
    input = (int*)malloc(sizeof(int)*number); 
    output = (int*)malloc(sizeof(int)*number); 
    printf("input the sequence of the elements:\n"); 
    for (i=0;i<number;i++) scanf("%d",&output[i]); 
    for (i=0;i<number;i++) input[i] = i+1; 

    Stack s; 
    Init(s); 
    int inIndex = 0; 
    int outIndex = 0; 
    //遍历出栈序列 
    while (outIndex<number) 
    { 
        int temp; 
        if (!Empty(s)) Top(s,temp); 
        //若栈为空或栈顶元素不等于出栈序列中当前元素，执行入栈操作 
        if (Empty(s)||temp!=output[outIndex]) 
        { 
            while(inIndex<number&&input[inIndex]!=output[outIndex])  
            { 
                Push(s,input[inIndex]); 
                inIndex++; 
            } 
            if (inIndex == number)  
            { 
                printf("wrong output sequece\n"); 
                return -1; 
            } 
            Push(s,input[inIndex]); 
            inIndex++; 
        } 
        Pop(s,temp); 
        if (temp!=output[outIndex]) 
        {            
            printf("wrong output sequece\n"); 
            return -1; 
        } 
        outIndex++; 
    } 
    printf("rignt output sequece\n"); 
    return 0; 
}

005521875