数据结构---链式栈及其入栈、出栈等 *** 作的实现（C语言）

文章目录

• 🎄链式栈
• 🎄链式栈的基础 *** 作实现
• • ⭐1.链式栈的初始化
  • ⭐2.链式栈入栈 *** 作
  • ⭐3.链式栈出栈 *** 作
  • ⭐4.判断链式栈是否空
  • ⭐5.遍历打印链式栈中元素
  • ⭐6.计算链式栈元素个数
  • ⭐7.动态内存释放
• 🎄栈

---

本文中涉及的完整代码及各 *** 作测试代码均已提交至Gitee，大家可以点击链接参考。

因本人为编程初学者，文中及代码中难免出错，请同志们批评指正！

---

🎄链式栈

上文我们讲述了顺序栈的实现，既然有顺序存储的栈，那么肯定就有链式存储的栈，本文将简要介绍链式栈的实现。

其实，和单链表的实现几乎一模一样，所不同的只是链表中插入、删除被限定在链表的一端。

那么把栈顶放在链表的头部还是尾部呢?由于单链表有头指针，而栈则需要栈顶指针，所以可以直接把栈顶放在单链表的头部。

另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

所以本文中的链表是没有头结点的。

这一点在编程的时候需要注意与带头结点的链表是不同的。

带头结点的单链表初始化时开辟一个动态内存的结点作为头结点，这个头结点在初始化时数据域是不需要存储数据的，指针域要置NULL。

最后返回开辟的头结点的指针。

不带头结点的单链表初始化时无需开辟动态空间，只需要返回NULL即可。

但也正因为如此，在main函数中如果要调用其他函数，那函数中链表指针需要考虑传址调用。

这一点我在代码中使用了二级指针来实现，具体可以看看下面的代码。

🎄链式栈的基础 *** 作实现

这里，最主要的是实现入栈、出栈的 *** 作，具体地我们来实现下面几个功能：

1. 链式栈的初始化；linkStack stack_init();
2. 链式栈入栈 *** 作；int stack_push(linkStack *s, data_t val);
3. 链式栈出栈 *** 作；data_t stack_pop(linkStack *s);
4. 判断链式栈是否空；int stack_empty(linkStack *s);
5. 遍历打印链式栈中元素；void stack_show(linkStack *s);
6. 计算链式栈元素个数；int stack_len(linkStack *s);
7. 动态内存释放；int stack_free(linkStack *s);

---

⭐1.链式栈的初始化

初始化之前，我们考虑一下链栈的结点模型，其实和单链表完全一样。

需要一个数据域和指针域。

typedef struct stackNode
{
	data_t data;
	struct stackNode* next;
}stackNode, * linkStack;

因为我们准备采用不带头结点的链表，所以初始化时也不需要创建头结点，直接返回个空指针就行了：

//1. 链式栈的初始化；
linkStack stack_init()
{
	linkStack s = NULL;
	return s;
}

在主函数中是这样定义一个链表的：
linkStack pstack = stack_init();

也正是因为在初始化时没有开辟空间，而只返回了空指针，所以main函数中的代表栈的地址的指针变量pstack也是空指针，如果在其他函数调用传参时直接传入pstack，那么就是传值传参，那样的话即使在某个函数内部为pstack开辟了空间，函数结束后，pstack在主函数中还是变回了NULL。

所以需要注意在其他功能函数调用参数时应使用传址传参，即传入&pstack。

这一点请看下面的代码中是怎么写的。

---

⭐2.链式栈入栈 *** 作

因为栈只允许一端插入，所以这里我们固定在链表头插入新数据。

那么在函数内部应该考虑这样的步骤：

1. 判断链表是不是空的，如果是空的，就创建一个结点；
2. 不是空的，就新建一个结点放在链表头最前面。
   

//2. 链式栈入栈 *** 作；
int stack_push(linkStack *s, data_t val)
{

	//先判断栈空不空,如果空的，先创建第一个结点：
	if (*s == NULL)
	{
		*s = (linkStack)malloc(sizeof(stackNode));
		if (*s == NULL)
		{
			return -1;
		}
		(*s)->data = val;
		(*s)->next = NULL;
		return 0;
	}
	//不空就在链表头前面加上一个结点
	linkStack p = (linkStack)malloc(sizeof(stackNode));
	if (p == NULL)
	{
		return -1;
	}
	p->next = *s;
	p->data = val;
	*s = p;
	return 0;
}

---

⭐3.链式栈出栈 *** 作

1. 判断是不是空的，是空的就提示用户并退出函数；
2. 不是空的，就把链表头结点的数据返回，并将链表头指针后移一个结点；
3. 将之前的链表头那个结点free掉。
   

//3. 链式栈出栈 *** 作；
data_t stack_pop(linkStack *s)
{
	//先判断栈是不是空栈（即栈顶指针存不存在）：
	if (*s == NULL) {
		printf("\nstack is empty");
		return -1;
	}

	//如果不是空的，就把*s对应的那个结点的数据传出去
	//接着把*s这个结点给free掉
	//需要通过tmp把(*s)->next赋值*s
	data_t ret = (*s)->data;
	linkStack tmp = (*s)->next;
	free(*s);
	*s = tmp;
	return ret;
}

---

⭐4.判断链式栈是否空

只需查看链表是不是NULL

//4. 判断链式栈是否空；
int stack_empty(linkStack *s)
{
	//只需要判断栈顶指针是不是空
	if (*s == NULL)
	{
		printf("\nstack is empty");
		return 0;
	}
	else
	{
		printf("\nstack has data\n");
		return -1;
	}
}

---

⭐5.遍历打印链式栈中元素

注意，因为没有头结点，所以循环的停止条件应该是 *s != NULL 而非（*s）->next != NULL。

//5. 遍历打印链式栈中元素；
void stack_show(linkStack *s)
{
	//先判断栈空不空：
	if (*s == NULL)
	{
		printf("\nstack error\n");
		return;
	}

	//不空，开始循环遍历打印：
	linkStack p = *s;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	return;
}

---

⭐6.计算链式栈元素个数

循环停止条件和5中相同。

这里考虑使用一个计数器变量cnt，循环一次++。

//6. 计算链式栈元素个数；
int stack_len(linkStack *s)
{
	//先判断栈空不空：
	if (*s == NULL)
	{
		printf("\nstack is empty\n");
		return -1;
	}
	int cnt = 0;
	linkStack p = *s;
	while (p != NULL)
	{
		cnt++;
		p = p->next;
	}
	printf("\nlen = %d\n", cnt);
	return cnt;
}

---

⭐7.动态内存释放

和单链表的释放一样，要从第一个结点开始将每个结点都释放。

//7. 动态内存释放；
int stack_free(linkStack *s)
{
	if (*s == NULL)
	{
		printf("\nstack is empty\n");
		return -1;
	}
	linkStack p = (*s);
	while ((*s) != NULL)
	{
		p = (*s);
		*s = (*s)->next;
		printf("\nfree:%d", p->data);//为了观察释放的是哪一个元素的结点，释放成功了没
		free(p);
	}
	return 0;
}

---

🎄栈

栈因为其独特的插入、删除规则，相较于顺序表和单链表来说 *** 作简单一些。

那么栈有什么应用呢？其实有很多，比如递归其实就是一种栈的结构来实现，还有计算机处理四则混合运算中的中缀表达式等。

具体的可以参考《大话数据结构》这本书的第100~110页。