【数据结构】C语言实现链栈

蒙奇D索隆

发布于 2024-01-18 08:33:11

1920

发布于 2024-01-18 08:33:11

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

链栈的C语言实现

前言

大家好，很高兴又和大家见面啦！！！在上一篇内容中，我们简单介绍了一下如何解决顺序栈空间不够的方法：

在创建顺序栈前，提前在空间内容申请一篇足够大的空间；
创建一个动态的链栈；

当我们使用第一种方式时，如果我们此时需要创建的是两个同类型的顺序栈，那么就会造成很严重的空间浪费，为了解决这个问题，我们则是通过将需要创建的两个顺序栈共享同一块空间，于是便有了共享站。之后我们也是详细的介绍了如何通过C语言来实现一个共享栈。

在今天的内容中，我们将来探讨一下对内存空间的使用更为灵活的链栈，以及如何通过C语言来实现一个链栈。下面我们就一起来看一下吧！！！

一、栈的链式存储

采用顺序存储的栈称为顺序栈，共享同一块空间的两个顺序栈称为共享栈。不管是顺序栈，还是共享栈，它们在创建好后，栈的大小是不能改变的，也就是说，顺序栈与共享栈都是有栈溢出的风险的，为了解决这个问题，我们就可以通过采用链式存储的方式来创建一个动态栈。 采用链式存储的栈称为链栈。

相比于顺序栈，链栈就不存在栈溢出的问题。通常我们采用不带头结点的单链表来实现链栈，为了复合栈的操作特性，于是规定了单链表的所有操作都只能在表头进行，头指针指向栈顶元素，如下所示：

既然是单链表，那我们就可以仿照单链表的数据类型格式来定义链栈的数据类型，如下所示：

//链栈的数据类型
typedef int ElemType;//将数据元素对应的数据类型重命名
typedef struct LinkNode {
	ElemType data;//数据域
	struct LinkNode* next;//指针域
}StackNode, * LinkStack;//重命名后的数据类型名
//StackNode——强调的是链栈的结点
// LinkStack——强调的是整个链栈

PS：这里我还是以整型为例，不过今天我将int类型通过typedef重命名为ElemType，这样如果我们后期想要将数据元素的数据类型修改为其它类型的话，我们只需要将重命名这一行修改就行了，也就不需要额外再写代码了。

既然是单链表，那我们就可以通过StackNode与LinkStack来区分整个链栈与链栈的结点，下面我们就来看一下如何通过C语言实现链栈的基本操作；

二、链栈的初始化

这里我们想要通过不带头结点的单链表来实现一个链栈，因此，我们在进行初始化时，只需要将头指针进行初始化即可，如下所示：

//链栈的初始化
void InitStack(LinkStack* S) {
	assert(S);
	*S = NULL;//初始化头指针
}

这里我是定义的一个无返回类型的函数，为了提高代码的健壮性，这里我们也可以通过定义一个返回类型为布尔类型的函数来告知使用者是否初始化成功。

因为初始化是对实参本身进行的修改，所以这里我们在传参时选择的是传址传参，形参通过指针来接收实参。因为涉及到指针，所以我们在初始化前一定要先对指针进行判空操作，可以像我一样直接通过assert进行断言，也可以通过其它方式；

三、链栈的进栈

根据链栈的操作特性——后进先出（LIFO），因此我们在实现时是将表头视为栈顶，这样的话头指针就变成了链栈的栈顶指针，那我们在进行插入时只需要通过头插法来进行进栈操作就行，如下所示：

//链栈的进栈
bool Push(LinkStack* S, ElemType x) {
	if (!S)
		return false;
	StackNode* p = (StackNode*)calloc(1, sizeof(StackNode));
	if (!p)
		return false;
	p->data = x;//将数据存入数据域中
	p->next = *S;//新结点从栈顶入栈
	*S = p;//栈顶指针指向新栈顶
	return true;
}

进栈函数，我将其返回值设置为布尔类型，这样用户就可以通过返回的结果来判断是否成功进行入栈，当然，我们也可以像共享栈一样，返回一个整型值，通过具体的值来确定问题，这样更加便于我们查找与修改错误。提高代码健壮性的方式很多，选择一款适合自己的方式即可。

对于入栈的编码逻辑，从代码中可以看到，我们是先将新的结点指向头指针，之后再移动头指针，将头指针指向新的结点，如下图所示：

这就是入栈的整个过程，接下来我们来看一下链栈的出栈操作；

四、链栈的出栈

链栈的出栈操作实质上就是单链表的头删操作，实现起来也是比较容易的，如下所示：

//链栈的出栈
bool Pop(LinkStack* S, ElemType* x) {
	if ((!S) && (!x))
		return false;
	//判空
	if (!(*S))
		return false;
	StackNode* p = *S;//指向进行出栈结点的指针
	*x = p->data;//将出栈的元素放入x
	*S = p->next;//栈顶指针指向新的栈顶
	p->next = NULL;//p结点出栈
	free(p);//释放结点p的内存空间
	return true;
}

如果我们需要将出栈的元素打印出来，那我们就需要将该数据带回给实参，因此，这里是通过指针接收的实参x；由于出栈也是对链栈的修改，因此我们也是通过指针接收的实参S；既然这里的形参有存在指针，那么我们就需要先对这两个指针进行判空，确保此时的两个形参都是有效的；

如果我们要进行出栈操作的话，首先的一点就是链栈不能是一个空栈，因此我们需要对链栈进行判空操作，判空的条件就是栈顶指针是否为空指针，如果是就返回false，否则继续后续的出栈操作；

在进行出栈操作时，我们是只将栈顶指针移动就行了，我们还需要将出栈的结点的内存空间给释放掉，因此这里定义了一个指向栈顶结点的指针，在完成出栈操作后，通过free函数将该结点的空间还给内存，最后再反馈给用户。

五、链栈的查找

在链栈中，我们能查找的就是栈顶元素，这里的栈顶元素也就是头指针指向的结点的数据域中存储的元素，因此我们要读取这个元素的操作也是很容易实现的，如下所示：

//链栈的查找
bool GetTop(LinkStack S, ElemType* x) {
	if (!x)
		return false;
	if (!S)//判空
		return false;
	*x = S->data;
	return true;
}

因为此时我们并不需要修改链栈，所以此时我们只需要通过传值传参在内存空间中复制一份链栈S就行；通过因为我们需要将查找到的元素带回，所以这里是通过指针接收的实参x；当然，我们要查找栈顶元素的前提是得有这个元素，即链栈不为空栈，所以我们还得对链栈进行判空操作，如果是空栈的话直接返回false；在这个函数中我们是通过布尔值来告诉用户，是否完成了查找任务；

六、链栈的销毁

对于链栈的销毁操作而言，就是重复进行出栈操作，知道栈为空栈，因此我们可以通过重复调用出栈操作来完成销毁，如下所示：

//链栈的销毁
bool DestroyStack(LinkStack* S) {
	if (!S)
		return false;
	while (*S) {
		int x = 0;
		Pop(S, &x);//这里的S已经是二级指针了，所以我们直接通过传值传参就行
		printf("栈顶元素%d已完成出栈\n", x);
	}
	return true;
}

在进行销毁操作时，因为我们本身就是通过传址传参进行的销毁操作，所以在调用出栈操作时，我们只需要将形参S直接进行传值传参就行；我们销毁的条件就是链栈不为空栈，当链栈为空栈时，我们就不需要继续进行销毁操作；我们这里依旧是通过函数的返回值来告诉用户销毁操作是否完成。

下面我们就一起来看一下我们有没有实现链栈；

七、链栈的实现

我们先来看一下测试的代码：

//链栈的数据类型
typedef int ElemType;//将数据元素对应的数据类型重命名
typedef struct LinkNode {
	ElemType data;//数据域
	struct LinkNode* next;//指针域
}StackNode, * LinkStack;//重命名后的数据类型名
//StackNode——强调的是链栈的结点
// LinkStack——强调的是整个链栈
//链栈的初始化
void InitStack(LinkStack* S) {
	assert(S);
	*S = NULL;//初始化头指针
}
//链栈的进栈
bool Push(LinkStack* S, ElemType x) {
	if (!S)
		return false;
	StackNode* p = (StackNode*)calloc(1, sizeof(StackNode));
	if (!p)
		return false;
	p->data = x;//将数据存入数据域中
	p->next = *S;//新结点从栈顶入栈
	*S = p;//栈顶指针指向新栈顶
	return true;
}
//链栈的出栈
bool Pop(LinkStack* S, ElemType* x) {
	if ((!S) && (!x))
		return false;
	//判空
	if (!(*S))
		return false;
	StackNode* p = *S;//指向进行出栈结点的指针
	*x = p->data;//将出栈的元素放入x
	*S = p->next;//栈顶指针指向新的栈顶
	p->next = NULL;//p结点出栈
	free(p);//释放结点p的内存空间
	return true;
}
//链栈的查找
bool GetTop(LinkStack S, ElemType* x) {
	if (!x)
		return false;
	if (!S)//判空
		return false;
	*x = S->data;
	return true;
}
//链栈的销毁
bool DestroyStack(LinkStack* S) {
	if (!S)
		return false;
	while (*S) {
		int x = 0;
		Pop(S, &x);//这里的S已经是二级指针了，所以我们直接通过传值传参就行
		printf("栈顶元素%d已完成出栈\n", x);
	}
	return true;
}
int main() {
	LinkStack S;
	InitStack(&S);
	int x = 0;
	//通过多组输入进行入栈操作
	while (scanf("%d", &x) == 1) {
		if (Push(&S, x))
			printf("数据%d已成功入栈\n", x);
		else
			printf("数据%d入栈失败\n", x);
	}
	if (Pop(&S, &x))
		printf("栈顶元素%d已成功出栈\n", x);
	else
		printf("栈顶元素出栈失败\n");
	if (GetTop(S, &x))
		printf("此时的栈顶元素为%d\n", x);
	else
		printf("栈顶元素读取失败\n");
	if (DestroyStack(&S))
		printf("链栈已成功销毁\n");
	else
		printf("链栈销毁失败\n");
	return 0;
}

下面我们来看一下测试结果如何，这里因为是通过多组输入完成的入栈，因此我们是通过输入一个非整数来结束入栈操作，测试结果如下所示：