程序员社区

初阶数据结构——栈

🎉🎉想快速入门数据结构,推荐订阅作者的初阶数据结构专栏!此专栏预计更新:顺序表,链表,栈,队列,二叉树,排序算法等等

🎉🎉初阶数据结构我们通过c语言实现,所以此专栏也可以帮助大家巩固大家的c语言知识

🎉🎉源代码已上传至我的码云

🎉🎉博主的微信公众号关注啦,关注我每天学习一道题,点我关注

知识引入

其实栈这个概念,我们早在c语言阶段就了解过了。

像啥函数栈帧呀,压栈啊啥的,我们都已经了解并掌握过了。

我们今天实现的数据结构,也叫做栈,特征其实是跟函数压栈差不多的道理

为了形象地了解栈的特性,我们可以打一个比方,假设有一把枪,你在进行射击训练

你肯定首先是要装子弹进弹夹的

在这里插入图片描述
肯定是先装的在弹夹的底部,而后装的在弹夹的顶部,这是显而易见的

我们装完了子弹,肯定要把它给打出去

在这里插入图片描述
这一步我们发现,子弹一定是先从顶部打出去

所以我们发现,子弹满足后进先出的特征,即后面进入的子弹会先被打出去

这也是我们栈的特征后进先出


初步了解

栈:本质是一种操作受限线性表

它只能支持在某一端的插入,删除与访问,与我们知识引入的子弹夹本质相同,都是后进先出

操作的一端我们叫做栈顶

不能操作的一端叫栈底

在这里插入图片描述

既然是线性表,我们就可以使用链表或者顺序表实现

但笔者认为栈用顺序表实现要好一些

理由如下

  1. 顺序表的尾部插入与删除的复杂度为O(1),我们可以选择把尾部作为栈顶
  2. 我们不需要特意去查找顺序表的尾部

相比与链表,既然插入删除的复杂度都达到了O(1),克服了顺序表最大的缺点,我们就不需要使用链表了


栈的定义

头文件定义

既然我们要使用顺序表要实现栈,我们就用顺序表的定义方式定义栈就行了

没看过顺序表文章的小伙伴,点此直达

typedef int STDataType;//方便存储各种各样的数据

typedef struct Stack
{
	STDataType* a;//顺序表数组
	int top;//这里记录栈顶
	int capacity;//这里记录数组容量
}ST;

栈的初始化

刚开始,数组还没有开辟,就为NULL,capacity为0

top为0或-1都可以

为0的情况:始终指向栈顶的下一个元素
为-1的情况:始终指向栈顶

图示

在这里插入图片描述

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

作者使用top=0的方式初始化

栈的插入

我们在这里直接选择在尾部进行插入,与顺序表的插入方式一样,这里不再阐述

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (!tmp)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}//以上是检查增容
	ps->a[ps->top] = x;
	ps->top++;//增加元素
}

栈的弹出

同样与顺序表的尾删方式一样

但是我们要检查,如果top=0了,就代表删除完了,就不能再删除了

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

返回栈顶元素

因为初始化的是top=0,所以我们访问时要把top减一,才能访问到栈顶

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

栈判空

我们同样使用top来判断,如果top=0,就代表为空

我们为了简化代码,可以直接使用条件表达式来判断

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

栈销毁

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

使用示例

由于栈的特性,我们不能直接遍历这个顺序表,只能访问栈顶的元素,然后再弹出,再访问下一个元素,以此类推,直到栈为空

void STTest()
{
	ST st;
	StackInit(&st);//定义栈并将其初始化
	
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	//插入元素
	while (!StackEmpty(&st))//如果栈不为空,继续访问
	{
		printf("%d ", StackTop(&st));//访问栈顶元素
		StackPop(&st);//访问完后弹出,方便访问下一个元素
	}
	StackDestory(&st);//使用完后将栈销毁
}

运行截图

在这里插入图片描述

后记

其实栈的实现真的不难,难的是关于栈的oj题!

不过没关系,作者后续的力扣每日一题会与这篇文章梦幻联动的,所以不妨订阅一波哦!

力扣每日一题专栏

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 初阶数据结构——栈

一个分享Java & Python知识的社区