链式栈的原理与实现（C语言版）
链式栈的原理与实现（C语言版）
链式栈是一种基于单向链表实现的栈数据结构，由栈头和若干节点组成。本文将详细介绍链式栈的创建、入栈出栈操作以及最终的释放过程，并通过C语言代码实现这些功能。
链式栈是一种基于单向链表实现的栈数据结构，由栈头和若干节点组成。栈头包含指向栈顶结点的指针和一个计数器。创建链式栈时，首先为栈头分配内存，并将其初始化。入栈操作通过为新结点分配内存并插入到栈顶来实现；出栈操作则先判断栈是否为空，然后移除栈顶结点并返回其值。释放链式栈时，需依次释放所有结点，并最终释放栈头。正确初始化栈顶指针为 NULL 能避免释放过程中出现死循环。
1 链式栈的创建
与单向链表类似，链式栈可看作栈头 + 若干普通结点。下图中，红色部分为指针域：
代码定义如下：
// 链式栈的普通结点
typedef struct _node {
struct _node* next;
Value_t data;
} node_t;
// 链式栈的栈头
typedef struct {
node_t* top;
int count;
} LinkStack;
有了结点后，就可以继续创建链式栈了。与顺序栈不同的是，链式栈创建时先为栈头部分开辟内存空间，等到入栈（push）操作时，再为待插入结点开辟相应空间。链式栈的创建代码如下（注意一定要初始化）：
LinkStack* createLinkStack() {
LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
if (NULL == stack) {
return NULL;
}
stack->count = 0;
stack->top = NULL;
return stack;
}
2 链式栈的入栈与出栈
2.1 入栈
相信有了前面单向链表插入的基础，入栈操作应该简单多了。
单向链表的相关内容：单向链表原理及实现（C语言版）-CSDN博客
如下图所示，为了保证能够找到原有结点，应先将 stack->top 赋值给 node_t* next，这一步相当于备份，同时也让 top 指向了栈顶元素；如果先执行操作 (2) ，就会丢失原有结点地址，导致内存泄漏。
代码实现如下：
int pushLinkStack(LinkStack* stack, Value_t e) {
node_t* new_node = (node_t*)malloc(sizeof(node_t));
if (NULL == new_node) {
return -1;
}
new_node->data = e;
new_node->next = stack->top;
stack->top = new_node;
++stack->count;
return 0;
}
2.2 出栈
出栈时，需要先判断一下 top->next 是否为 NULL 。
代码实现如下：
int popLinkStack(LinkStack* stack, Value_t* e) {
if (NULL == stack->top) {
printf("LinkStack is empty\n");
return -1;
}
Value_t x1 = stack->top->data;
node_t* tmp = stack->top;// 备份
stack->top = tmp->next;
free(tmp);
--stack->count;
if (e) {
*e = x1;
}
return 0;
}
3 链式栈的释放
与出栈操作类似，只要 top 不为 NULL（证明栈内还有元素），就一直执行出栈操作，最后释放栈头部分即可。代码实现如下：
void releaseLinkStack(LinkStack* stack) {
if (NULL == stack->top) {
printf("LinkStack is empty\n");
return;
}
if (stack) {
while (stack->top) {
node_t* tmp = stack->top;
stack->top = tmp->next;
free(tmp);// 依次释放每个结点
--stack->count;
}
}
printf("The number of node in LinkStack is :%d\n ", stack->count);
free(stack);// 最后释放栈头
}
前面有提到，创建链式栈时，一定要将 stack->top 初试化为 NULL 。如果忘记初始化，那么此处释放栈空间时就会出错，因为 while 语句将无法终止，陷入死循环。