栈的顺序结构表示

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define TRUE 1
  5 #define FALSE 0
  6 #define OK 1
  7 #define ERROR 0
  8 #define OVERFLOW -2
  9 #define INIT_SIZE 20
 10 #define INCREMENT_SIZE 5
 11 
 12 typedef int SElemType;
 13 typedef int Status;
 14 
 15 /*
 16  * 存储结构
 17  */
 18 typedef struct
 19 {
 20     SElemType *base;    //栈尾指针
 21     SElemType *top;        //栈顶指针
 22     int size;            //栈的大小
 23 }SqStack;
 24 
 25 /*
 26  * 初始化栈
 27  */
 28 Status InitStack(SqStack *S)
 29 {
 30     S->base = (SElemType*) malloc(INIT_SIZE * sizeof(SElemType));
 31     if (!S->base)
 32     {
 33         exit(OVERFLOW);
 34     }
 35     S->top = S->base;
 36     S->size = INIT_SIZE;
 37     return OK;
 38 }
 39 
 40 /*
 41  * 销毁栈
 42  */
 43 Status DestroyStack(SqStack *S)
 44 {
 45     S->base = NULL;
 46     S->top = NULL;
 47     S->size = 0;
 48     free(S->base);
 49     return OK;
 50 }
 51 
 52 /*
 53  * 清空栈
 54  */
 55 Status ClearStack(SqStack *S)
 56 {
 57     S->top = S->base;
 58     return OK;
 59 }
 60 
 61 /*
 62  * 判断栈是否为空
 63  */
 64 Status IsEmpty(SqStack S)
 65 {
 66     if (S.top == S.base)
 67     {
 68         return TRUE;
 69     }
 70     else
 71         return FALSE;
 72 }
 73 
 74 /*
 75  * 获取栈的长度
 76  */
 77 int GetLength(SqStack S)
 78 {
 79     return (S.top - S.base) / sizeof(SElemType);
 80 }
 81 
 82 /*
 83  * 获取栈顶元素
 84  */
 85 Status GetTop(SqStack S, SElemType *e)
 86 {
 87     if (S.top > S.base)
 88     {
 89         *e = *(S.top - sizeof(SElemType));
 90         return OK;
 91     }
 92     else
 93     {
 94         return ERROR;
 95     }
 96 }
 97 
 98 /*
 99  * 压栈
100  */
101 Status Push(SqStack *S, SElemType e)
102 {
103     if ((S->top - S->base) / sizeof(SElemType) >= S->size)
104     {
105         S->base = (SElemType*) realloc(S->base, (S->size + INCREMENT_SIZE) * sizeof(SElemType));
106         if (!S->base)
107         {
108             exit(OVERFLOW);
109         }
110         S->top = S->base + S->size * sizeof(SElemType);
111         S->size += INCREMENT_SIZE;
112     }
113     *S->top = e;
114     S->top += sizeof(SElemType);
115     return OK;
116 }
117 
118 /*
119  * 退栈
120  */
121 Status Pop(SqStack *S, SElemType *e)
122 {
123     if (S->top == S->base)
124     {
125         return ERROR;
126     }
127     S->top -= sizeof(SElemType);
128     *e = *S->top;
129     return OK;
130 }
131 
132 /*
133  * 访问元素
134  */
135 void visit(SElemType e)
136 {
137     printf("%d ", e);
138 }
139 
140 /*
141  * 遍历栈
142  */
143 Status TraverseStack(SqStack S, void (*visit)(SElemType))
144 {
145     while (S.top > S.base)
146     {
147         visit(*S.base);
148         S.base += sizeof(SElemType);
149     }
150     return OK;
151 }
152 
153 int main()
154 {
155     SqStack S;
156     if (InitStack(&S))
157     {
158         SElemType e;
159         int i;
160 
161         printf("init_success
");
162 
163         if (IsEmpty(S))
164         {
165             printf("Stack is empty
");
166         }
167 
168         for (i = 0; i < 10; i++)
169         {
170             Push(&S, i);
171         }
172 
173         GetTop(S, &e);
174         printf("The first element is %d
", e);
175         printf("length is %d
", GetLength(S));
176         Pop(&S, &e);
177         printf("Pop element is %d
", e);
178         TraverseStack(S, *visit);
179         if (DestroyStack(&S))
180         {
181             printf("
destroy_success
");
182         }
183     }
184 }