思路：

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

如上述操作，直至完成出栈序列遍历，说明出栈序列正确。

代码：

1. #include <stdlib.h> 
2. #include <stdio.h> 
3.  
4. struct Stack 
5. { 
6.     int* base; 
7.     int* top; 
8.     int size;    
9. }; 
10.  
11. //初始化栈 
12. void Init(Stack &s) 
13. { 
14.     s.base = (int*)malloc(sizeof(int)*100); 
15.     s.top = s.base; 
16.     s.size = 100; 
17. } 
18.  
19. //入栈 
20. bool Push(Stack &s,int n) 
21. { 
22.     if (s.top-s.base >= s.size) 
23.     { 
24.         s.size = s.size + 10; 
25.         s.base = (int*)realloc(s.base,sizeof(int)*s.size); 
26.     } 
27.     *s.top = n; 
28.     s.top++; 
29.     return true; 
30. } 
31.  
32. //出栈 
33. bool Pop(Stack &s,int &n) 
34. { 
35.     if (s.top==s.base) return false; 
36.     s.top--; 
37.     n = *s.top; 
38.     return true; 
39. } 
40.  
41. bool Top(Stack &s,int &n) 
42. { 
43.     if (s.top==s.base) return false; 
44.     n = *(s.top-1); 
45.     return true; 
46. } 
47.  
48. bool Empty(Stack s) 
49. { 
50.     if (s.top == s.base) return true; 
51.     else return false; 
52. } 
53.  
54. int main() 
55. { 
56.     int i,number; 
57.     int* input; 
58.     int* output; 
59.     printf("input the number of the elements:\n"); 
60.     scanf("%d",&number); 
61.     input = (int*)malloc(sizeof(int)*number); 
62.     output = (int*)malloc(sizeof(int)*number); 
63.     printf("input the sequence of the elements:\n"); 
64.     for (i=0;i<number;i++) scanf("%d",&output[i]); 
65.     for (i=0;i<number;i++) input[i] = i+1; 
66.  
67.     Stack s; 
68.     Init(s); 
69.     int inIndex = 0; 
70.     int outIndex = 0; 
71.     //遍历出栈序列 
72.     while (outIndex<number) 
73.     { 
74.         int temp; 
75.         if (!Empty(s)) Top(s,temp); 
76.         //若栈为空或栈顶元素不等于出栈序列中当前元素，执行入栈操作 
77.         if (Empty(s)||temp!=output[outIndex]) 
78.         { 
79.             while(inIndex<number&&input[inIndex]!=output[outIndex])  
80.             { 
81.                 Push(s,input[inIndex]); 
82.                 inIndex++; 
83.             } 
84.             if (inIndex == number)  
85.             { 
86.                 printf("wrong output sequece\n"); 
87.                 return -1; 
88.             } 
89.             Push(s,input[inIndex]); 
90.             inIndex++; 
91.         } 
92.         Pop(s,temp); 
93.         if (temp!=output[outIndex]) 
94.         {            
95.             printf("wrong output sequece\n"); 
96.             return -1; 
97.         } 
98.         outIndex++; 
99.     } 
100.     printf("rignt output sequece\n"); 
101.     return 0; 
102. }