栈的链式存储实现
栈的链式存储也称为链栈，它和链表的存储原理一样，都可以利用闲散空间来存储元素，用指针来建立各结点之间的逻辑关系。链栈也会设置一个栈顶元素的标识符top，称为栈顶指针。它和链表的区别是，只能在一端进行各种操作。如图1所示。
图1 链栈
链栈就是一个单端操作的链表，它的插入删除操作就是在链表的一端进行。接下来我们就来实现一个链栈，其功能如下：
● 创建一个链栈。
● 判断链栈是否为空。
● 压栈、弹栈。
● 获取栈顶元素。
● 销毁链栈。
然后在main.c文件中完成此链栈的测试，具体如例1所示。
例1
linkstack.h //头文件
1 #ifndef _LINKSTACK_H_
2 #define _LINKSTACK_H_
3
4 typedef struct Node * pNode;
5 typedef struct Stack * LinkStack;
6 struct Node //数据结点
7 {
8 int data; //数据
9 pNode next; //指针
10 };
11
12 struct Stack //此结构记录栈的大小和栈顶元素指针
13 {
14 pNode top; //栈顶元素指针
15 int size; //栈大小
16 };
17
18 LinkStack Create(); //创建栈
19 int IsEmpty(LinkStack lstack); //判断栈是否为空
20 int getSize(LinkStack lstack); //获取栈的大小
21 int Push(LinkStack lstack, int val); //元素入栈
22 pNode getTop(LinkStack lstack); //获取栈顶元素
23 pNode Pop(LinkStack lstack); //弹出栈顶元素
24 void Destory(LinkStack lstack); //销毁栈
25
26 #endiflinkstack.c //操作函数实现文件
27 #include "linkstack.h"
28 #include <stdio.h>
29 #include <stdlib.h>
30
31 LinkStack Create() //创建栈
32 {
33 LinkStack lstack = (LinkStack)malloc(sizeof(struct Stack));
34 if (lstack != NULL)
35 {
36 lstack->top = NULL;
37 lstack->size = 0;
38 }
39 return lstack;
40 }
41
42 int IsEmpty(LinkStack lstack) //判断栈是否为空
43 {
44 if (lstack->top == NULL || lstack->size == 0)
45 return 1;
46 return 0;
47 }
48
49 int getSize(LinkStack lstack)
50 {
51 return lstack->size; //获取栈的大小
52 }
53
54 int Push(LinkStack lstack, int val)
55 {
56 pNode node = (pNode)malloc(sizeof(struct Node)); //为元素val分配结点
57 if (node != NULL)
58 {
59 node->data = val;
60 node->next = getTop(lstack); //新元素结点指向下一个结点,链式实现
61 lstack->top = node; //top指向新结点
62 lstack->size++;
63 }
64 return 1;
65 }
66
67 pNode getTop(LinkStack lstack) //获取栈顶元素
68 {
69 if (lstack->size != 0)
70 return lstack->top;
71 return NULL;
72 }
73
74 pNode Pop(LinkStack lstack) //弹出栈顶元素
75 {
76 if (IsEmpty(lstack))
77 {
78 return NULL;
79 }
80 pNode node = lstack->top; //node指向栈顶元素
81 lstack->top = lstack->top->next; //top指向下一个元素
82 lstack->size--;
83 return node;
84 }
85
86
87 void Destory(LinkStack lstack) //销毁栈
88 {
89 if (IsEmpty(lstack))
90 {
91 free(lstack);
92 printf("栈已为空，不必再行销毁！\n");
93 return;
94 }
95 //如果栈不为空，需要把栈中的结点都删除释放
96 do
97 {
98 pNode pTmp;
99 pTmp = Pop(lstack);
100 free(pTmp);
101 }while (lstack->size > 0);
102 printf("栈销毁成功！\n");
103 }main.c //测试文件
104 #include <stdio.h>
105 #include <stdlib.h>
106 #include "linkstack.h"
107
108 int main()
109 {
110 srand((unsigned)time(0));
111 LinkStack lstack = NULL;
112 lstack = Create(); //创建一个栈
113
114 //判断栈是否为空
115 int ret;
116 ret = IsEmpty(lstack);
117 if (ret)
118 printf("栈为空！\n");
119 else
120 printf("栈不为空！\n");
121
122 //向栈中插入元素
123 for (int i = 0; i < 10; i++)
124 {
125 Push(lstack, rand() % 100); //插入的是随机产生的数
126 }
127
128 //再次判断栈是否为空
129 ret = IsEmpty(lstack);
130 if (ret)
131 printf("栈为空！\n");
132 else
133 printf("栈不为空！\n");
134
135 //求栈的长度
136 printf("栈的长度：%d\n", getSize(lstack));
137
138 //获取栈顶元素
139 //返回的是pNode结点类型，要转换为int类型
140 printf("栈顶元素：%d\n", *((int*)getTop(lstack)));
141
142 //打印栈中的元素
143 while (lstack->size > 0)
144 {
145 //Pop()返回的是pnode结点类型，也要转换为int类型
146 printf("%d ", *((int*)Pop(lstack)));
147 }
148 printf("\n");
149
150 //销毁栈
151 Destory(lstack);
152
153 system("pause");
154 return 0;
155 }运行结果如图2所示。
图2 例1运行结果
在例1中，代码6-16行定义了链栈的数据结点与头结点，这与链表的定义方式相同，但有时在链栈的实现中，通常不定义头结点，而是直接把栈顶放在单链表的头部。
创建好栈之后，先调用IsEmpty()函数判断栈是否为空，结合代码，由图3-7中的代码执行结果可知：初始时栈为空；代码123-126行，向栈中存入元素，再次进行判断时，由图3-7可知，，此时栈不为空；代码136行中代码输出栈的长度为10；代码140行求栈顶元素，由图3-7可知此时栈顶元素为46；代码143-147行打印栈中的元素，即将元素逐一弹出。由代码可知，栈中的元素是随机产生的数，由图中输出结果可知，第一个元素为46，与求得的栈顶元素相同；代码151行销毁栈，因为在打印时已经将栈中元素全部弹出，所以在销毁之时栈已空，等同已经销毁。
点击此处
隐藏目录
隐藏目录
