链栈

  1 /*
  2 链栈
  3 LJK 2018-07-04
  4 */
  5 #include<stdio.h>
  6 #include<stdlib.h>
  7 
  8 #define MAXSIZE 15
  9 #define OK 1
 10 #define ERROR 0
 11 #define TRUE 1
 12 #define FALSE 0
 13 
 14 typedef int SElemType;
 15 typedef int Status;
 16 
 17 // 链栈结点
 18 typedef struct stackNode
 19 {
 20     SElemType data;
 21     struct  stackNode *next;
 22 }StackNode;
 23 
 24 // 链栈结构
 25 typedef struct linkStack
 26 {
 27     StackNode *top;
 28     int count;
 29 }LinkStack;
 30 
 31 // 构造一个空栈
 32 Status InitStack(LinkStack *S)
 33 {
 34     S->top = NULL;
 35     S->count = 0;
 36     return OK;
 37 }
 38 
 39 // 插入 e 为新的栈顶元素
 40 Status Push(LinkStack *S, SElemType e)
 41 {
 42     StackNode *s = (StackNode*)malloc(sizeof(StackNode));
 43     s->data = e;
 44     s->next = S->top;
 45     S->top = s;
 46     S->count++;
 47     return OK;
 48 }
 49 
 50 // 遍历显示链栈
 51 Status StackTraverse(LinkStack S)
 52 {
 53     StackNode *p = S.top;
 54     while (p)
 55     {
 56         printf("%d ", p->data);
 57         p = p->next;
 58     }
 59     printf("
");
 60     return OK;
 61 }
 62 
 63 // 若栈不空，则删除栈顶元素，用e返回其值
 64 Status Pop(LinkStack *s, SElemType *e)
 65 {
 66     StackNode *p;
 67     if (s->top == NULL) return ERROR;
 68     *e = s->top->data;
 69     p = s->top;
 70     s->top = s->top->next;
 71     free(p);
 72     s->count--;
 73     return OK;
 74 }
 75 
 76 Status StackEmpty(LinkStack S)
 77 {
 78     if (S.count == 0) return TRUE;
 79     else return FALSE;
 80 }
 81 
 82 Status GetTop(LinkStack S, SElemType *e)
 83 {
 84     if (S.top == NULL) return ERROR;
 85     *e = S.top->data;
 86     return OK;
 87 }
 88 
 89 int StackLength(LinkStack S)
 90 {
 91     return S.count;
 92 }
 93 
 94 // 将S设置为空栈
 95 Status ClearStack(LinkStack *S)
 96 {
 97     StackNode *p, *q;
 98     p = S->top;
 99     while (p)
100     {
101         q = p;
102         p = p->next;
103         free(q);
104     }
105     S->top = NULL;
106     S->count = 0;
107     return OK;
108 }
109 
110 int main()
111 {
112     LinkStack s;
113     int j;
114     SElemType e;
115 
116     if (InitStack(&s) == OK)
117     {
118         for ( j = 1; j <= 10; j++)
119             Push(&s, j);
120     }
121     printf("Stack:");
122     StackTraverse(s);
123 
124     Pop(&s, &e);
125     printf("栈顶 e = %d
", e);
126     printf("Stack:");
127     StackTraverse(s);
128     printf("
");
129 
130     printf("栈空否：%d (1:空 0:否)
", StackEmpty(s));
131     printf("
");
132 
133     printf("Len(stack) = %d
", StackLength(s));
134     printf("
");
135 
136     ClearStack(&s);
137     printf("清空栈后：
");
138     printf("栈空否：%d (1:空 0:否)
", StackEmpty(s));
139     printf("Len(stack) = %d
", StackLength(s));
140     printf("
");
141 
142     getchar();
143     return 0;
144 }