linux下C语言栈的使用

时间：2011-05-16 来源：孤独的猫

栈结构是计算机语言实现中的一种重要的数据结构，对于任意栈，进行插入和删除操作的一端称为栈顶，而另一端成为栈底。栈的基本操作为：创建栈(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 }