1 #include<stdio.h>
2 #include<malloc.h>
3 #include<stdlib.h>
4
5 typedef struct Node{
6 int data;//数据域
7 struct Node * pNext;
8 }NODE,*PNODE;
9
10 typedef struct Stack{
11 PNODE pTop;//指向栈的顶部节点
12 PNODE pBottom;//指向栈的底部节点
13 }STACK,* PSTACK;
14
15 //函数声明
16 void init(PSTACK);//初始化一个空栈,使pTop和pBottom都指向头结点
17 void push(PSTACK,int);//存元素,压栈
18 void traverse(PSTACK);//遍历
19 bool pop(PSTACK,int *);//出栈并且返回出栈元素,还要判断出栈是否成功
20 bool empty(PSTACK);//判断栈是否为空
21 void clear(PSTACK);//清空数据
22
23 int main(){
24 STACK S;//等价于struct Stack S,分配一块内存空间名为S
25 //里面有pTop和pBottom,暂时是垃圾值
26 int val;
27
28 init(&S);//初始化一个空栈,使pTop和pBottom都指向头结点
29 push(&S,1);//存元素,压栈
30 push(&S,2);//存元素,压栈
31 traverse(&S);//遍历
32 clear(&S);//清空
33
34 if(pop(&s,&val)){//删元素,出栈
35 printf("出栈成功,出栈元素的是%d\n",val);
36 }
37 else{
38 printf("出栈失败");
39 }
40
41 return 0;
42 }
43
44 void init(PSTACK pS){
45 pS->pTop = (PNODE)malloc(sizeof(NODE));
46
47 if(pS->pTop==NULL){
48 printf("动态内存分配失败");
49 exit(-1);//程序终止
50 }
51 else{
52 pS->pBottom=pS->pTop;//空栈情况下,栈顶和栈底都指向同一个地址
53 //即最后一个有效节点的下一个节点
54 pS->pTop->pNext=NULL;//pS->pBottom->pNext==NULL
55 //pS的成员pTop指向的头结点的指针域为空
56 }
57 }
58
59 void push(PSTACK pS,int val){
60 PNODE pNew = (PNODE)malloc(sizeof(NODE));//创建新结点
61 pNew->data = val;
62 pNew->pNext = pS->pTop;//使新节点的指针域指向原来的栈顶节点,
63 //不能是ps->pBottom
64 pS->pTop = pNew;//使栈顶指向新节点地址
65
66 return ;
67 }
68
69 void traverse(PSTACK pS){
70 PNODE p = pS->PTop;//临时指针指向栈顶
71 while(p != pS->pBototm){//若p还没有栈底pBottom,则遍历输出
72 printf("%d ",p->data);//从栈顶开始输出
73 p=p->pNext;
74 }
75 printf("\n");
76 return ;
77 }
78
79 bool empty(PSTACK pS){
80 if(pS->pTop == pS->pBottom) return true;//当栈底和栈顶指向同一块地址,为空栈
81 esle return false;
82 }
83
84 //把pS所指向的栈出栈一次,并把出栈的元素存入val形参所指向的变量中,
85 //出栈成功返回true,失败返回false
86 bool pop(PSTACK pS,int * val){
87 if(empty(pS)) return false;
88 els{
89 *val = pS->data;//主函数里输出出栈元素
90 PNODE r = pS->pTop;//临时指针r指向出栈元素位置:栈顶,方便最后释放内存
91 ps->pTop = r->pNext;//栈顶指针指向原来栈顶的下一个节点地址
92 free(r);
93 r = NULL;
94 return true;
95 }
96 }
97
98 void clear(PSTACK pS){//清空数据,最终使栈顶和栈底指向同一个地址
99 if(empty(pS)){//如果栈本身为空,不需要清空
100 return ;
101 }
102 else{
103 PNODE p = pS->pTop;//临时指针P指向栈顶
104 PNODE q = NULL;//临时指针q暂时设为NULL
105 while(p != pS->pBottom){//当栈顶指针不指向栈底时,栈不为空
106 q = p->pNext;//临时指针q指向下一个节点
107 free(p);//释放p的内存
108 p = q;//再使p指向下一节点地址
109 }
110 }
111 pS->pTop = pS->pBottom;//最后数据全部清空,栈顶和栈底指向同一个地址
112 }