c语言实现栈(顺序栈,链栈)网站首页 技术教程

c语言实现栈(顺序栈,链栈)

初阶牛 2024-06-17 10:20:02

简介c语言实现栈(顺序栈,链栈)

在这里插入图片描述

?个人主页:? :✨✨✨初阶牛✨✨✨
?推荐专栏: ???C语言进阶
?个人信条: ?知行合一
?本篇简介:>:讲解用c语言实现:“数据结构之"栈”,分别从"顺序栈"和"链栈"的接口讲解.
金句分享:
✨不是每一场雨后都有彩虹,但是晴天总是会到来!✨

前言

栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

在这里插入图片描述

"栈"的常见接口实现

InitST:初始化栈
STPush:入栈
STPop:出栈
STEmpty:判空(判断是否为空栈)
PrintSTTop:打印栈顶元素
STTop:返回栈顶元素(返回值类型:stacktype)

一、顺序栈

"顺序栈"的类型定义

如果友友们学过顺序表,这种类型可以随便拿捏.??

代码:

typedef struct stack
{
	stacktype* data;//一个指向连续内存空间的指针
	int top;//记录栈顶元素的下标
	int capacaity;
}ST;

在这里插入图片描述

1.1 初始化栈

top指针:
由于数组的下标是从0开始,所以我们初始化"栈"时,可以将top指针(栈顶指针)初始化为-1,这样即可代表"栈"中无数据.

capacaity :
同顺序表一样,我们可以设置初始最大容量,后续不够可以扩容.

void InitST(ST* ps)
{
	assert(ps);
	ps->top = -1;//此时栈中无数据
	ps->capacaity = 4;//设置初始最大容量
	ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

此处初始化后:
在这里插入图片描述

1.2 入栈(压栈,向"栈"中插入数据)

学到这里(顺序表和链表),对于"栈"的压栈操作很简单.

由于是顺序表实现栈,所以在进行插入操作之前要先进行"判满"操作,如果栈满了,要进行扩容.
top是指向栈顶下标,需要将其往后移动一位,使其指向待插入位置.
将新元素插入.此时刚好top为新的栈顶的下标.

图解:
在这里插入图片描述

代码:

void STPush(ST* ps, stacktype x)//压栈
{
	assert(ps);
	if (ps->top+1 == ps->capacaity)//检查"栈"满
	{
		ps->capacaity *= 2;//扩容
		ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
		if(tmp == NULL)
		{
			printf("增容失败
");
		}
		ps->data = tmp;
	}
	//将"栈顶指针"指向待插入位置
	ps->top++;
	//将元素压栈
	ps->data[ps->top] = x;
	
}

1.3 “出栈”,删除"栈"中的数据

步骤:

删除数据时,需要判断"栈"是否为空.
将top向前(下)移动一位,即表示有效数据位减1.

代码:

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

1.4 判空(判断"栈"是否为空)

当栈为空时,top为初始状态-1.

bool STEmpty(ST* ps)//判断是否为空栈,是空返回真
{
	assert(ps);
	if (ps->top == -1)
	{
		return true;
	}
	return false;
}

1.5 打印"栈顶"元素

void PrintSTTop(ST* ps)
{
	assert(ps);
	printf("%d", ps->data[ps->top]);
}

1.6 返回"栈顶"元素

stacktype STTop(ST* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data[ps->top];
}

1.7 "栈"的销毁

栈的销毁操作,因为malloc开辟出来的是连续的空间,所以只需要释放一次即可.

void STDestory(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = -1;
	ps->capacaity = 0;
}

二、链栈

"链栈"的类型定义

typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
    stacktype data;
    struct SLStackNode* next;
}SLStackNode;

其实我们不难发现,"链栈"的类型与单链表很相似,通过对"栈"的基本知识了解,"栈"只在一端进行"插入"和"删除"操作,为了用单链表实现这一要求.

同时为了提高效率:

链表	分析
尾插，尾删	效率低，因为需要找尾巴
头插，头插	效率高,只需要改变头指针的指向

综上:我们利用不带头单链表的"头插(入栈)和头删(出栈)"来完成栈的各项基本操作.并且"栈"不需要进行随机访问其中的元素,只能从栈顶访问,链表是可以完成的.

2.1 初始化"链栈"

对于链表实现的栈,如果不带头结点:
我们不需要特意去写一个初始化函数.只需要创建一个栈顶指针,将其初始化指向NULL即可.(下面的代码是采用这种形式)

//创建一个栈顶指针,并完成初始化
SLStackNode* SLStack = NULL;

如果是带头结点的单链表:
我们可以定义一个初始化函数,申请一个头结点(头结点的数据域不存数据),将头结点返回.

//stack.c
SLStackNode* InitStack()
{
	SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
	if (newnode == NULL)
	{
		perror("newnode malloc fail");
	}
	return newnode;
}

//test.c
SLStackNode* SLStack = InitStack();

2.2 入栈(压栈,向"栈"中插入数据)

步骤:(与单链表的头插类似)

创建一个新节点.
将新节点的next指针指向原"栈"的顶点
更新栈顶指针(将栈顶指针指向新节点)

图解:
在这里插入图片描述

代码:

//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
	assert(pps);
	//获取新的结点
	SLStackNode* newnode = BuyNode(x);
	newnode->next = *pps;//将新节点的next指针指向原"栈"的顶点
	*pps = newnode;//更新栈顶
}

2.3 “出栈”,删除"栈"中的数据

步骤:(与链表的头删操作类似)

判空,防止空链栈的删除操作
记录原栈顶元素的地址.
更新栈顶.(将栈顶指针指向原栈顶的下一个结点↓).
释放原栈顶空间

图解:
在这里插入图片描述

void STPop(SLStackNode** pps)//出栈
{
	assert(pps);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pps);//防止空链栈的删除操作
	SLStackNode* head = *pps;//记录栈顶元素的地址
	*pps = (*pps)->next;//更新栈顶,即原来栈顶的下一个结点
	free(head);//释放原栈顶空间
}

2.4 判空(判断"栈"是否为空)

链栈(不带头版本的)的初始状态是栈顶指针指向NULL.

bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
	if (ps == NULL)
	{
		return true;
	}
	else
		return false;
}

2.5 打印"栈顶"元素

栈顶元素即,栈顶指针指向的结点的数据域.

void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
	assert(ps);
	printf("%d ", ps->data);
}

2.6 返回"栈顶"元素

stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data;
}

2.7 返回"链栈"的长度(有效数据的个数)

遍历这个栈即可求出栈的长度.(但其实一般情况下,栈是不允许遍历的,栈顶元素不出去,我们原则上不能访问栈顶下面的元素).

代码:

int LengthStack(SLStackNode* ps)
{
	int count = 0;
	if (ps == NULL)//如果栈顶指针指向NULL,表示栈中没有元素
	{
		return 0;
	}
	SLStackNode* tail = ps;//代替头指针遍历
	while (ps)
	{
		count++;//如果该结点不为空,则有效数据个数+1
		ps = ps->next;
	}
	return count;//返回有效数据的个数
}

2.8 "链栈"的销毁

与"链表"销毁类似.

void STDestory(SLStackNode* ps)//栈的销毁
{
	SLStackNode* del = ps;
	SLStackNode* next = ps;//用于记录下一个结点
	while (next)
	{
		next = next->next;
		free(del);
		del = next;

	}
	//保持习惯置空
	next == NULL;
	del = NULL;
}

总结:

虽然链表和顺序表可以实现"栈",并且效率上,二者差距不大.

但是如果了解过寄存器的小伙伴,应该知道,如果数据在物理上是连续存储的,更加有利于数据的读取.

寄存器:

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。

因为cpu不是直接从硬盘读取数据的(嫌弃硬盘太慢了),而是通过寄存器(访问速度很快).

数据先被加载到缓存,此时如果数据在物理上是连续存储的,则在加载数据到缓存时,刚好将后面要读的数据也读走了,这样再读下一个数据时,就不需要再去硬盘读了.

?栗子:
在这里插入图片描述

综上,还是稍微建议使用顺序栈有一点点优势.

希望这篇文章对大家有帮助。欢迎小伙伴们私信提意见和提问哦！
最后，小伙伴们的点赞就是给牛牛最大的支持，能不能给牛牛来一个一键三连呢？谢谢支持。
在这里插入图片描述

总代码

"顺序栈"总代码

声明区(stack.h)

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef  int stacktype;
typedef struct stack
{
	stacktype* data;
	int top;
	int capacaity;
}ST;
void InitST(ST* ps);
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
void PrintSTTop(ST* ps);//打印栈顶元素

bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁

接口实现区( stack.c)

#include "stack.h"
//初始化栈
void InitST(ST* ps)
{
	assert(ps);
	ps->top = -1;
	ps->capacaity = 4;
	ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

//压栈
void STPush(ST* ps, stacktype x)
{
	assert(ps);
	if (ps->top+1 == ps->capacaity)
	{
		ps->capacaity *= 2;
		ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
		if(tmp == NULL)
		{
			printf("增容失败
");
		}
		ps->data = tmp;
	}
	ps->top++;
	ps->data[ps->top] = x;
	
}

//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

//打印栈顶元素
void PrintSTTop(ST* ps)
{
	assert(ps);
	printf("%d", ps->data[ps->top]);
}

//判断是否为空栈,是空返回真
bool STEmpty(ST* ps)
{
	assert(ps);
	if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1;
	{
		return true;
	}
	return false;
}

//返回栈顶元素
stacktype STTop(ST* ps)
{
	assert(ps);
	return ps->data[ps->top];//反追栈顶元素
}

//栈的销毁
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->data);//释放栈空间
	ps->data = NULL;
	ps->top = -1;
	ps->capacaity = 0;
}

测试区(test.c)

#include "stack.h"
void test1()
{
	ST st1;
	InitST(&st1);
	STPush(&st1, 1);//压栈
	STPush(&st1, 2);//压栈
	STPush(&st1, 3);//压栈
	STPush(&st1, 4);//压栈
	int a=STTop(&st1);
	printf("栈顶元素为%d
", a);
	while (!STEmpty(&st1))
	{
		PrintSTTop(&st1);//打印栈顶元素
		STPop(&st1);
	}

	STDestory(&st1);
	
}
int main()
{
	test1();
	return 0;
}

"链栈"总代码:

声明区(SLStack.h)

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
    stacktype data;
    struct SLStackNode* next;
}SLStackNode;


//SLStackNode* InitStack();

void STPush(SLStackNode** pps, stacktype x);//压栈
void STPop(SLStackNode** pps);//出栈
void PrintSTTop(SLStackNode* ps);//打印栈顶元素

bool STEmpty(SLStackNode* ps);//判断是否为空栈
stacktype STTop(SLStackNode* ps);//返回栈顶元素

int LengthStack(SLStackNode* ps);//返回栈的长度

void STDestory(SLStackNode* ps);//栈的销毁

接口实现区(SLStack.c)

#include "SLStack.h"

//SLStackNode* InitStack()
//{
//	SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
//	if (newnode == NULL)
//	{
//		perror("newnode malloc fail");
//	}
//	return newnode;
//}

SLStackNode* BuyNode(stacktype x)//创建新结点
{
	SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
	assert(newnode);//防止申请结点失败
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}


//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
	assert(pps);
	//获取新的结点
	SLStackNode* newnode = BuyNode(x);
	newnode->next = *pps;
	*pps = newnode;
}

void STPop(SLStackNode** pps)//出栈
{
	assert(pps);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pps);//防止空链栈的删除操作
	SLStackNode* head = *pps;//记录栈顶元素的地址
	*pps = (*pps)->next;//将栈顶向下移动一位
	free(head);//释放栈顶空间
}

void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
	assert(ps);
	printf("%d ", ps->data);
}

bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
	if (ps == NULL)
	{
		return true;
	}
	else
		return false;
}

stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data;
}

int LengthStack(SLStackNode* ps)
{
	int count = 0;
	if (ps == NULL)
	{
		return 0;
	}
	SLStackNode* tail = ps;
	while (ps)
	{
		count++;
		ps = ps->next;
	}
	return count;
}

void STDestory(SLStackNode* ps)//栈的销毁
{
	SLStackNode* del = ps;
	SLStackNode* next = ps;//用于记录下一个结点
	while (next)
	{
		next = next->next;
		free(del);
		del = next;

	}
	//保持习惯置空
	next == NULL;
	del = NULL;
}

测试区(test.c)

#include "SLStack.h"

void test1()
{
	SLStackNode* SLStack = NULL;
	//SLStackNode* SLStack = InitStack();

	STPush(&SLStack, 1);//压栈
	STPush(&SLStack, 2);//压栈
	STPush(&SLStack, 3);//压栈
	STPush(&SLStack, 4);//压栈
	STPush(&SLStack, 5);//压栈
	STPush(&SLStack, -1);//压栈
	STPush(&SLStack, -2);//压栈
	int a = STTop(SLStack);
	printf("栈顶元素为%d
", a);

	int length = LengthStack(SLStack);
	printf("链表的长度为:%d
", length);

	while (!STEmpty(SLStack))
	{
		PrintSTTop(SLStack);//打印栈顶元素
		STPop(&SLStack);
	}
	
	STDestory(SLStack);

}
int main()
{
	test1();
	return 0;
}

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
Shell脚本文本三剑客之sed编辑器(拥明月入...

下一篇
HashMap 扰动函数、负载因子、扩容链表拆...

站长推荐

U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》

您现在的位置是：首页 >技术教程 >c语言实现栈(顺序栈,链栈)网站首页技术教程

c语言实现栈(顺序栈,链栈)

前言

目录

栈

"栈"的常见接口实现

一、顺序栈

"顺序栈"的类型定义

1.1 初始化栈

1.2 入栈(压栈,向"栈"中插入数据)

1.3 “出栈”,删除"栈"中的数据

1.4 判空(判断"栈"是否为空)

1.5 打印"栈顶"元素

1.6 返回"栈顶"元素

1.7 "栈"的销毁

二、链栈

"链栈"的类型定义

2.1 初始化"链栈"

2.2 入栈(压栈,向"栈"中插入数据)

2.3 “出栈”,删除"栈"中的数据

2.4 判空(判断"栈"是否为空)

2.5 打印"栈顶"元素

2.6 返回"栈顶"元素

2.7 返回"链栈"的长度(有效数据的个数)

2.8 "链栈"的销毁

总结:

总代码

"顺序栈"总代码

声明区(stack.h)

接口实现区( stack.c)

测试区(test.c)

"链栈"总代码:

声明区(SLStack.h)

接口实现区(SLStack.c)

测试区(test.c)

上一篇 Shell脚本文本三剑客之sed编辑器(拥明月入...

下一篇 HashMap 扰动函数、负载因子、扩容链表拆...

站长推荐

上一篇
Shell脚本文本三剑客之sed编辑器(拥明月入...

下一篇
HashMap 扰动函数、负载因子、扩容链表拆...