顺序栈

首先定义顺序栈的存储结构

 1 /* 栈的顺序存储结构
 2 **/
 3 #define STACK_INIT_SIZE 100 //存储空间的初始分配量
 4 #define STACK_INCREMENT 10  //存储空间的分配增量
 5 typedef int SElemType;
 6 typedef struct {
 7     SElemType *bottom;//栈底元素指针
 8     SElemType *top;   //栈顶元素指针
 9     int size;//栈空间最大容量
10 }SqStack;

顺序栈支持的基本操作如下：

 1 #include "sqstack_algo.h"
 2 #include <stdlib.h>
 3 
 4 /*
 5 ** 初始化
 6 */
 7 void SqStack_Init(SqStack *s)
 8 {
 9     s->bottom = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
10     if (!s->bottom) exit(EXIT_FAILURE);
11     s->top = s->bottom;//栈顶指针指向栈底(空栈)
12     s->size = STACK_INIT_SIZE;
13 }
14 
15 /*
16 ** 清空
17 */
18 void SqStack_Clear(SqStack *s)
19 {
20     s->top = s->bottom;//栈顶指针指向栈底(空栈)
21 }
22 
23 /*
24 ** 销毁
25 */
26 void SqStack_Destroy(SqStack *s)
27 {
28     free(s->bottom);//释放栈空间
29     s->top = s->bottom = NULL;
30     s->size = 0;
31 }
32 
33 /*
34 ** 获取长度
35 */
36 int SqStack_Length(SqStack s)
37 {
38     return s.top - s.bottom;
39 }
40 
41 /*
42 ** 返回栈顶元素
43 */
44 int SqStack_GetTop(SqStack s, SElemType *e)
45 {
46     if (s.top > s.bottom){
47         *e = *(--s.top);
48         return 1;
49     }
50     return 0;
51 }
52 
53 /*
54 ** 入栈
55 */
56 void SqStack_Push(SqStack *s, SElemType e)
57 {
58     if (s->top - s->bottom == s->size){
59         s->bottom = (SElemType*)realloc(s->bottom, 
60             (s->size + STACK_INCREMENT)*sizeof(SElemType));
61         if (!s->bottom) exit(EXIT_FAILURE);
62         s->top = s->bottom + s->size;//修改栈顶指针,指向新的栈顶
63         s->size += STACK_INCREMENT;//更新当前可用的最大容量
64     }
65     *(s->top)++ = e;//将e入栈，栈顶指针后移
66 }
67 
68 
69 /*
70 ** 出栈
71 */
72 int SqStack_Pop(SqStack *s, SElemType *e)
73 {
74     if (s->top == s->bottom) return 0;//栈空
75     *e = *(--s->top);
76     return 1;
77 }

以下给出测试程序：

 1 /*
 2 ** @brief This file is used for testing data structure and algorithms
 3 ** @data 2015-05-25
 4 */
 5 #include <stdio.h>
 6 #include "sqstack_algo.h"
 7 
 8 int main(int argc, char **argv)
 9 {
10     SqStack s;
11     SElemType e;
12 
13     SqStack_Init(&s);
14     scanf("%d", &e);
15     while (e > 0){
16         SqStack_Push(&s, e);
17         scanf("%d", &e);
18     }
19 
20     while (SqStack_Pop(&s, &e)){
21         printf("Pop: %d -> ", e);
22         if (SqStack_GetTop(s, &e)){
23             printf("Top: %d
", e);
24         }else{
25             printf("Top: NULL
");
26         }
27     }
28     SqStack_Destroy(&s);//销毁
29 
30     return 0;
31 }