2.2. 栈
具有一定操作约束的线性表。 只在一端做插入和删除操作。 这一端被称为栈顶，插入称为入栈， 删除称为出栈。
抽象数据结构描述
Stack CreateStack (int MaxSize): 生成空堆栈，最大长度maxsize .
int IsFull （Stack s , int maxsize) : 判断是否已经满了。
void Push(Stack s,ElementType item): 插入元素。
void IsEmpty(Stack s): 判断是否为空栈，也就是一个元素没有。
ElementType Pop(Stack s): 从栈里面删除最顶部元素，并返回该元素。
2.2.1. 栈的顺序存储具体实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MAXSIZE 100
5#define ElementType int
6#define ERROR -9999
7
8typedef struct SNode *Stack;
9struct SNode {
10 ElementType Data[MAXSIZE];
11 int Top; // 顶部元素的下标。
12};
13
14
15Stack CreateStack() {
16 Stack s = (Stack) malloc(sizeof(struct SNode)) ;
17 s->Top =-1;
18 return s ;
19}
20
21int IsFull(Stack s) {
22 if (s->Top == MAXSIZE - 1) {
23 return 1;
24 }
25 return 0;
26}
27
28void Push(Stack s, ElementType item) {
29 if (IsFull(s) == 1) {
30 printf("is full\n");
31 return;
32 }
33 (s->Top)++;
34 s->Data[s->Top] = item;
35}
36
37
38int IsEmpty(Stack s) {
39 if (s->Top == -1) {
40 return 1;
41 }
42 return 0;
43}
44
45ElementType Pop(Stack s) {
46 if (IsEmpty(s) == 1) {
47 printf("is null\n");
48 return ERROR;
49 }
50
51 ElementType item = s->Data[s->Top];
52 (s->Top)--;
53 return item;
54}
55
56
57int main() {
58 Stack s = CreateStack();
59 ElementType item ;
60 printf("%d\n",IsEmpty(s));
61 Push(s,1);
62 printf("%d\n",IsFull(s));
63 Push(s,2);
64 Push(s,3);
65 Push(s,4);
66 Push(s,5);
67 printf("%d\n",IsFull(s));
68 Push(s,6);
69 printf("%d\n",IsFull(s));
70 item = Pop(s) ;
71 printf("%d\n",item );
72 item = Pop(s) ;
73 printf("%d\n",item );
74 item = Pop(s) ;
75 printf("%d\n",item );
76 item = Pop(s) ;
77 printf("%d\n",item );
78 item = Pop(s) ;
79 printf("%d\n",item );
80 item = Pop(s) ;
81 printf("%d\n",item );
82 return 0;
83 /*
84 1
85 0
86 1
87 is full
88 1
89 5
90 4
91 3
92 2
93 1
94 is null
95 -9999
96
97 */
98}
99
2.2.2. 栈的链式存储具体实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define ElementType int
5#define ERROR -9999
6typedef struct SNode *Stack ;
7struct SNode {
8 ElementType Data;
9 struct SNode *Next ;
10};
11
12Stack CreateStack() {
13 Stack s = (Stack)malloc(sizeof(struct SNode)) ;
14 s->Next = NULL;
15 return s ;
16}
17
18void Push(Stack s, ElementType item) {
19 struct SNode *tmpNode;
20 tmpNode = (struct SNode *)malloc(sizeof(struct SNode)) ;
21 tmpNode->Data = item ;
22 tmpNode->Next = s->Next ;
23 s->Next = tmpNode;
24}
25int StackIsEmpty(Stack s){
26 if (s->Next == NULL){
27 return 1 ;
28 }
29 return 0 ;
30}
31
32ElementType Pop(Stack s) {
33 if (StackIsEmpty(s)==1){
34 printf("null \n") ;
35 return ERROR;
36 }
37 struct SNode *firstNode;
38 ElementType itemValue ;
39 firstNode = s->Next ;
40 s->Next = firstNode->Next;
41 itemValue = firstNode->Data;
42 free(firstNode) ;
43 return itemValue;
44}
45
46int main2() {
47 Stack s = CreateStack();
48 ElementType item ;
49 printf("is empty ? %d\n",StackIsEmpty(s));
50 Push(s,1);
51 Push(s,2);
52 Push(s,3);
53 Push(s,4);
54
55 item = Pop(s) ;
56 printf("%d\n",item );
57 item = Pop(s) ;
58 printf("%d\n",item );
59 item = Pop(s) ;
60 printf("%d\n",item );
61 item = Pop(s) ;
62 printf("%d\n",item );
63 item = Pop(s) ;
64 printf("%d\n",item );
65
66 return 0;
67 /*
68
69
70 */
71}