6-03 1,823 views
思路：
遍历出栈序列，对于其中任一元素k，查看当前栈是否为空，若为空或栈顶元素不等于k，则根据入栈序列进行入栈，直至入栈序列中的元素k入栈。若直至入栈序列末尾仍无k，说明出栈序列错误。入栈完成后，将k出栈。
如上述操作，直至完成出栈序列遍历，说明出栈序列正确。
代码：
|
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; } |
