数据结构堆栈

 1 /* Stack.h */
 2 #ifndef _Stack_H
 3 #define _Stack_H
 4 
 5 struct NodeStack;
 6 typedef struct NodeStack *PtrToNode;
 7 typedef PtrToNode Stack;
 8 typedef char ElementType;
 9 
10 int StackIsEmpty(Stack S);
11 Stack CreateStack(void);
12 void DisposeStack(Stack S);
13 void MakeEmpty(Stack S);
14 void Push(ElementType X, Stack S);
15 ElementType Top(Stack S);
16 void Pop(Stack S);
17 
18 // Stack implementation is a linked list with a header
19 struct NodeStack
20 {
21     ElementType Element;
22     PtrToNode Next;
23 };
24 
25 #endif

 1 /* Stack.cpp */
 2 #include "Stack.h"
 3 #include <stdlib.h>
 4 #include <stdio.h>
 5 
 6 int StackIsEmpty(Stack S)
 7 {
 8     return S->Next == NULL;
 9 }
10 
11 // 创建一个空栈, 只需创建一个头结点
12 Stack CreateStack(void)
13 {
14     Stack S;
15 
16     S = (struct NodeStack*)malloc(sizeof(struct NodeStack));
17     if(S == NULL)
18         printf("Fatal Error: Out of space!!");
19     S->Next = NULL;
20     MakeEmpty(S);
21     return S;
22 }
23 // 清空栈
24 void MakeEmpty(Stack S)
25 {
26     if(S == NULL)
27         printf("Must use CreateStack first");
28     else
29         while(!StackIsEmpty(S))
30             Pop(S);
31 }
32 
33 // Push 操作, 在链表的前端插入
34 void Push(ElementType X, Stack S)
35 {
36     PtrToNode TmpCell;
37 
38     TmpCell = (struct NodeStack*)malloc(sizeof(struct NodeStack));
39     if(TmpCell == NULL)
40         printf("Fatal Error: Out of space!!");
41     else
42     {
43         TmpCell->Element = X;
44         TmpCell->Next = S->Next;
45         S->Next = TmpCell;
46     }
47 }
48 
49 // Top 操作, 返回栈顶元素
50 ElementType Top(Stack S)
51 {
52     if (!StackIsEmpty(S))
53         return S->Next->Element;
54 
55     printf("Empty stack\n");
56     return 0;
57 }
58 
59 // Pop 操作, 通过删除表的前端元素实现
60 void Pop(Stack S)
61 {
62     PtrToNode FirstCell;
63 
64     if(StackIsEmpty(S))
65          printf("Empty stack\n");
66     else
67     {
68         FirstCell = S->Next;
69         S->Next = FirstCell->Next;
70         free(FirstCell);
71     }
72 }

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "Stack.h"
 4 void main()
 5 {
 6     // 创建一个堆栈
 7     Stack stackchar;
 8     stackchar = CreateStack();
 9     for (int i=0; i< 5; ++i)
10     {
11         char cstr = '(';
12         Push(cstr+i, stackchar);
13     }
14     while(!StackIsEmpty(stackchar))
15     {
16         printf("%c ", Top(stackchar));
17         Pop(stackchar);
18     }
19 }

参考：