栈结构是计算机语言实现中的一种重要的数据结构，对于任意栈，进行插入和删除操作的一端称为栈顶，而另一端成为栈底。栈的基本操作为：创建栈(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 }
编译gcc -Wall -o stack1 stack1.c
然后运行得
24 4
注意：
在linux的C环境中，不支持
Stack* myStack语法，也不支持
typedef struct Stack {
......
} Stack;
这会被认为循环定义。
