顺序实现

1. #ifndef STACK_H_INCLUDED 
2. #define STACK_H_INCLUDED 
3. #include "ds.h" //for Status,OK ... 
4. #ifndef ElemType 
5. #define ElemType int /* 数据元素类型默认为 int */ 
6. #define ELEMTYPE_TAG 
7. #endif 
8. #define SElemType ElemType 
9. /// 
10. //顺序栈的存储结构定义  
11. #define STACK_INIT_SIZE 100 /* 存储空间初始分配容量 */ 
12. #define STACKINCREMENT 10 /* 存储空间分配的增量 */ 
13. typedef struct { 
14.     ElemType *base; //在构造栈之前和销毁栈之后，base为NULL 
15.     ElemType *top; //栈顶指针 
16.     int stacksize; //当前已分配的存储空间(元素个数)  
17. } SqStack; 
18. /// 
19. //顺序栈的基本操作声明 
20. //构造一个空栈S  
21. Status InitStack(SqStack &S); 
22. //销毁栈S  
23. Status DestroyStack(SqStack &S); 
24. //将栈S清空  
25. Status ClearStack(SqStack &S); 
26. //若栈S为空返回TRUE，否则FALSE  
27. Status StackEmpty(SqStack S); 
28. //返回栈S中的元素个数 
29. int    StackLength(SqStack S); 
30. //用e返回栈顶元素 
31. //    前提：栈S存在且不空  
32. Status GetTop(SqStack S, ElemType &e); 
33. //元素e入栈S  
34. Status Push(SqStack &S, ElemType e); 
35. //S出栈用e返回出栈元素  
36. //    前提：栈S存在且不空  
37. Status Pop(SqStack &S, ElemType &e); 
38.  
39. /// 
40. //顺序栈的基本操作的实现 
41.  
42. //构造一个空栈S  
43. Status InitStack(SqStack &S) 
44. { 
45.     // TODO (#1#): 构造一个空栈S 
46.     S.base=(ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType)); 
47.     if(!S.base) exit(OVERFLOW); 
48.     SS.top=S.base; 
49.     S.stacksize=STACK_INIT_SIZE; 
50.     return OK; 
51.     //------------------------------------- 
52. } 
53.  
54. //销毁栈S  
55. Status DestroyStack(SqStack &S) 
56. { 
57.     // TODO (#1#):销毁栈S，相当于清空栈  
58.     free(S.base); 
59.     S.base=NULL; 
60.     return OK; 
61.     //------------------------------------- 
62. } 
63.  
64. //将栈S清空  
65. Status ClearStack(SqStack &S) 
66. { 
67.     // TODO (#1#): 将栈S清空，释放所有结点 
68.     ElemType e; 
69.     while(Pop(S,e)!=ERROR); 
70.     return OK; 
71.     //------------------------------------- 
72. } 
73.  
74. //若栈S为空返回TRUE，否则FALSE  
75. Status StackEmpty(SqStack S) 
76. { 
77.     // TODO (#1#): 若栈S为空返回TRUE，否则FALSE 
78.     if(S.top==S.base) 
79.         return OK; 
80.     return ERROR; 
81.     //------------------------------------- 
82. } 
83.  
84. //返回栈S中的元素个数 
85. int    StackLength(SqStack S) 
86. { 
87.     // TODO (#1#): 返回栈S中的元素个数 
88.     return S.top-S.base; 
89.     //------------------------------------- 
90. } 
91.  
92. //用e返回栈顶元素 
93. //    前提：栈S存在且不空  
94. Status GetTop(SqStack S, ElemType &e) 
95. { 
96.     // TODO (#1#):若栈S不空，则用e返回栈顶元素 
97.     if(S.top ==S.base) 
98.         return ERROR; 
99.     e=*(S.top-1); 
100.     return OK; 
101.     //------------------------------------- 
102. } 
103.  
104. //元素e入栈S  
105. Status Push(SqStack &S, ElemType e) 
106. { 
107.     // TODO (#1#): 插入元素e作为新的栈顶  
108.     if(S.top-S.base>=S.stacksize) 
109.     { 
110.         S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); 
111.         if(!S.base)exit(OVERFLOW); 
112.         SS.top=S.base+S.stacksize; 
113.         S.stacksize+=STACKINCREMENT; 
114.     } 
115.     *S.top++=e; 
116.     //*S.top=e; 
117.     //S.top++; 
118.     return OK; 
119.     //------------------------------------- 
120. } 
121.  
122. //S出栈用e返回出栈元素  
123. //    前提：栈S存在且不空  
124. Status Pop(SqStack &S, ElemType &e) 
125. { 
126.     // TODO (#1#):若栈S不空，则删除栈顶元素用e返回 
127.     if(S.top==S.base)  
128.     return ERROR; 
129.     e=*--S.top; 
130.     return OK; 
131.     //------------------------------------- 
132. } 
133.  
134.  
135. #ifdef ELEMTYPE_TAG 
136. #undef ElemType 
137. #undef ELEMTYPE_TAG 
138. #endif 
139.  
140. #endif 

1. #include <stdio.h> 
2. #include <stdlib.h> //for system() 
3. #include "stack.h" //for SqStack  
4.  
5. //测试顺序栈的主程序 
6. int main() 
7. { 
8.     SqStack s; 
9.     int x; 
10.     //输入若干正整数以0结束，依次入栈，然后依次出栈并打印 
11.     InitStack(s); 
12.      
13.     printf("输入若干正整数以0结束:"); 
14.     scanf("%d",&x); 
15.     while(x!=0) { 
16.         Push(s,x); 
17.         scanf("%d",&x); 
18.     } 
19.      
20.     printf("\n出栈结果:"); 
21.     while(!StackEmpty(s)) { 
22.         Pop(s,x); 
23.         printf("%4d",x); 
24.     } 
25.      
26.      
27.     //------------------------------------- 
28.     // TODO (#1#): 其它测试程序  
29.      
30.     //------------------------------------- 
31.      
32.     DestroyStack(s); //销毁栈  
33.      
34.     system("PAUSE");     
35.     return 0; 
36. } 

链式实现

1. #ifndef STACK_H_INCLUDED 
2. #define STACK_H_INCLUDED 
3.  
4. #include "ds.h" //for Status,OK ... 
5.  
6. #ifndef ElemType 
7. #define ElemType int /* 数据元素类型默认为 int */ 
8. #define ELEMTYPE_TAG 
9. #endif 
10.  
11.  
12. /// 
13. //链栈的存储结构定义  
14. typedef struct LNode { 
15.     ElemType data; 
16.     struct LNode *next; 
17. } LNode, *LinkList; 
18.  
19. typedef LinkList LinkStack; //链栈类型  
20.  
21. /// 
22. //链栈的基本操作声明 
23.  
24. //构造一个空栈S  
25. Status InitStack(LinkStack &S); 
26. //销毁栈S  
27. Status DestroyStack(LinkStack &S); 
28. //将栈S清空  
29. Status ClearStack(LinkStack &S); 
30. //若栈S为空返回TRUE，否则FALSE  
31. Status StackEmpty(LinkStack S); 
32. //返回栈S中的元素个数 
33. int    StackLength(LinkStack S); 
34. //用e返回栈顶元素 
35. //    前提：栈S存在且不空  
36. Status GetTop(LinkStack S, ElemType &e); 
37. //元素e入栈S  
38. Status Push(LinkStack &S, ElemType e); 
39. //S出栈用e返回出栈元素  
40. //    前提：栈S存在且不空  
41. Status Pop(LinkStack &S, ElemType &e); 
42.  
43. /// 
44. //链栈的基本操作的实现 
45.  
46. //构造一个空栈S  
47. Status InitStack(LinkStack &S) 
48. { 
49.     // TODO (#1#): 构造一个空栈S，不带头结点 
50.     S=(LinkStack)malloc(sizeof(LNode)); 
51.     if(!S) return ERROR; 
52.     S->next=NULL; 
53.     return OK; 
54.     //------------------------------------- 
55. } 
56.  
57. //销毁栈S  
58. Status DestroyStack(LinkStack &S) 
59. { 
60.     // TODO (#1#):销毁栈S，相当于清空栈 
61.     LinkStack p; 
62.     while(S) 
63.     { 
64.        p=S->next; 
65.        free(S); 
66.        S=p; 
67.     } 
68.     return OK; 
69.     //------------------------------------- 
70. } 
71.  
72. //将栈S清空  
73. Status ClearStack(LinkStack &S) 
74. { 
75.     // TODO (#1#): 将栈S清空，释放所有结点 
76.     LinkStack p,q; 
77.     p=S->next; 
78.     while(p) 
79.     { 
80.        q=p->next; 
81.        free(p); 
82.        p=q; 
83.     } 
84.     S->next=NULL; 
85.     return OK; 
86.     //------------------------------------- 
87. } 
88.  
89. //若栈S为空返回TRUE，否则FALSE  
90. Status StackEmpty(LinkStack S) 
91. { 
92.     // TODO (#1#): 若栈S为空返回TRUE，否则FALSE 
93.     if(S==NULL) 
94.     return 1; 
95.     else 
96.         return 0; 
97.     //------------------------------------- 
98. } 
99.  
100. //返回栈S中的元素个数 
101. int    StackLength(LinkStack S) 
102. { 
103.     // TODO (#1#): 返回栈S中的元素个数 
104.     LinkStack p; 
105.     int x=0; 
106.     p=S->next; 
107.     while(p!=NULL) 
108.     { 
109.        x++; 
110.        pp=p->next; 
111.     } 
112.     return x; 
113.     //------------------------------------- 
114. } 
115.  
116. //用e返回栈顶元素 
117. //    前提：栈S存在且不空  
118. Status GetTop(LinkStack S, ElemType &e) 
119. { 
120.     // TODO (#1#):若栈S不空，则用e返回栈顶元素 
121.     if(S==NULL) exit(OVERFLOW); 
122.     e=S->data; 
123.     return OK; 
124.     //------------------------------------- 
125. } 
126.  
127. //元素e入栈S  
128. Status Push(LinkStack &S, ElemType e) 
129. { 
130.     // TODO (#1#): 插入元素e作为新的栈顶  
131.     LinkStack p; 
132.     p=(LinkStack)malloc(sizeof(LNode)); 
133.     if(!p)exit(OVERFLOW); 
134.     p->data=e; 
135.     p->next=NULL; 
136.     p->next=S->next; 
137.     S->next=p; 
138.     return OK; 
139.     //------------------------------------- 
140. } 
141.  
142. //S出栈用e返回出栈元素  
143. //    前提：栈S存在且不空  
144. Status Pop(LinkStack &S, ElemType &e) 
145. { 
146.     // TODO (#1#):若栈S不空，则删除栈顶元素用e返回  
147.     if(S==NULL) return ERROR; 
148.     e=S->data; 
149.     SS=S->next; 
150.     return OK; 
151.     //------------------------------------- 
152. } 
153.  
154.  
155. #ifdef ELEMTYPE_TAG 
156. #undef ElemType 
157. #undef ELEMTYPE_TAG 
158. #endif 
159.  
160. #endif 

1. #include <stdio.h> 
2. #include <stdlib.h> //for system() 
3. #include "stack.h" //链栈  
4.  
5. //测试链栈的主程序 
6. int main() 
7. { 
8.     LinkStack s; 
9.     int x; 
10.     //输入若干正整数以0结束，依次入栈，然后依次出栈并打印 
11.     InitStack(s); 
12.      
13.     printf("输入若干正整数以0结束:"); 
14.     scanf("%d",&x); 
15.     while(x!=0) { 
16.         Push(s,x); 
17.         scanf("%d",&x); 
18.     } 
19.      
20.     printf("\n出栈结果:"); 
21.     while(!StackEmpty(s)) { 
22.         Pop(s,x); 
23.         printf("%4d",x); 
24.     } 
25.      
26.      
27.     //------------------------------------- 
28.     // TODO (#1#): 其它测试程序  
29.      
30.     //------------------------------------- 
31.      
32.     DestroyStack(s); //销毁栈  
33.      
34.     system("PAUSE");     
35.     return 0; 
36. }