栈结构是计算机语言实现中的一种重要的数据结构，对于任意栈，进行插入和删除操作的一端称为栈顶，而另一端成为栈底。栈的基本操作为：创建栈(NewStack)，判断栈是否为空(IsEmpty)，判断栈是否满(IsFull)，获取栈顶元素(Top)，压栈/入栈(Push)，弹栈/出栈(Pop).
栈的存储方式有多种，其中，采用链式栈存储结构实现可不必连续存储，以下为C代码采用链式栈实现一个整数栈操作(vim stack1.c):
1
#include
<
stdio.h
>
2 #include < malloc.h >
3
4 typedef struct List {
5 int data; /* 栈数据 */
6 struct List * next; /* 上次入栈的数据地址 */
7 }dList;
8
9 typedef struct Stack {
10 dList * pTop; /* 当前栈顶指针 */
11 }dStack;
12
13 dStack * NewStack() { return (dStack * )calloc( 1 , sizeof (dStack));}
14
15 int IsEmpty(dStack * S) { /* 判断栈S是否为空栈 */
16 if ( ! S ||! S -> pTop) return 1 ;
17 return 0 ;
18 }
19
20 int Top(dStack * S) {
21 if (IsEmpty(S)) return - 10000 ;
22 return S -> pTop -> data;
23 }
24
25 void Push(dStack * S, int theData) { /* 将数据theData压栈 */
26 dList * newNode;
27 newNode = (dList * )calloc( 1 , sizeof (dList));
28 newNode -> data = theData;
29 newNode -> next = S -> pTop;
30 S -> pTop = newNode;
31 }
32
33 void Pop(dStack * S) { /* 弹栈 */
34 dList * lastTop;
35 if (IsEmpty(S)) return ;
36 lastTop = S -> pTop;
37 S -> pTop = S -> pTop -> next;
38 free(lastTop);
39 }
40
41 #define MD(a) a<<2
42 int main()
43 {
44 int i;
45 dStack * myStack;
46 myStack = NewStack();
47 Push(myStack,MD( 1 ));
48 Push(myStack,MD( 2 ));
49 Pop(myStack);
50 Push(myStack,MD( 3 ) + 1 );
51 while ( ! IsEmpty(myStack)) {
52 printf( " %d " ,Top(myStack));
53 Pop(myStack);
54 }
55 printf( " \n " );
56 return 0 ;
57 }
2 #include < malloc.h >
3
4 typedef struct List {
5 int data; /* 栈数据 */
6 struct List * next; /* 上次入栈的数据地址 */
7 }dList;
8
9 typedef struct Stack {
10 dList * pTop; /* 当前栈顶指针 */
11 }dStack;
12
13 dStack * NewStack() { return (dStack * )calloc( 1 , sizeof (dStack));}
14
15 int IsEmpty(dStack * S) { /* 判断栈S是否为空栈 */
16 if ( ! S ||! S -> pTop) return 1 ;
17 return 0 ;
18 }
19
20 int Top(dStack * S) {
21 if (IsEmpty(S)) return - 10000 ;
22 return S -> pTop -> data;
23 }
24
25 void Push(dStack * S, int theData) { /* 将数据theData压栈 */
26 dList * newNode;
27 newNode = (dList * )calloc( 1 , sizeof (dList));
28 newNode -> data = theData;
29 newNode -> next = S -> pTop;
30 S -> pTop = newNode;
31 }
32
33 void Pop(dStack * S) { /* 弹栈 */
34 dList * lastTop;
35 if (IsEmpty(S)) return ;
36 lastTop = S -> pTop;
37 S -> pTop = S -> pTop -> next;
38 free(lastTop);
39 }
40
41 #define MD(a) a<<2
42 int main()
43 {
44 int i;
45 dStack * myStack;
46 myStack = NewStack();
47 Push(myStack,MD( 1 ));
48 Push(myStack,MD( 2 ));
49 Pop(myStack);
50 Push(myStack,MD( 3 ) + 1 );
51 while ( ! IsEmpty(myStack)) {
52 printf( " %d " ,Top(myStack));
53 Pop(myStack);
54 }
55 printf( " \n " );
56 return 0 ;
57 }
编译gcc -Wall -o stack1 stack1.c
然后运行得
24 4
注意：
在linux的C环境中，不支持
Stack* myStack语法，也不支持
typedef struct Stack {
......
} Stack;
这会被认为循环定义。
