【栈】基于顺序表的栈功能实现

叫我龙翔

发布于 2024-01-30 13:58:43

950

发布于 2024-01-30 13:58:43

文章被收录于专栏：就业 C++ 综合学习

1 栈是什么

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

1.1 基本功能

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

栈可以形象得想象成一个高高的箱子，只能从上面放入与拿出。

1.2 为什么选择“顺序表”为基础

根据对顺序表的了解，顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。这样操作简单快速就可以实现“栈”的功能。

因为“栈”只能在栈顶进行操作，如果使用链表就需要频繁找尾，导致时间复杂度较高而使用顺序表，通过“size”变量的使用可以快速找到尾部，更加方便。

2 功能实现

这是“栈”的功能概况，下面予以实现：

2.1 初始化与销毁

//初始化
void StackInit(Stack* ps) {

	assert(ps);
	ps->a = NULL;
	//栈顶元素的下一个元素
	ps->top = 0;
	ps->capacity = 0;
}
//销毁
void StackDestroy(Stack* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

与顺序表一致，多加了一个"top"变量的初始化。 top : 记录栈顶位置。 (与顺序表的“size”本质相同)

2.2 入栈与出栈

//入栈
void StackPush(Stack* ps, STDataType data) {
	assert(ps);
	//容量检查
	if (ps->top == ps->capacity) 
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	    STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity)；

	    if (tmp == NULL) {
		   perror("relloc failed");
		   exit(-1);
	    }

		ps->a = tmp;
	    ps->capacity = newcapacity;
	}
	

	
	ps->a[ps->top] = data;
	ps->top++;

}

与顺序表的尾插功能一致。进行容量检查之后，就可以在尾部进行插入，并将“top”++。

//出栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

出栈的功能更加简单，将“top”–即可。

2.3 获取栈顶元素与获取有效元素个数

//获取栈顶元素
STDataType StackTop(Stack* ps) {
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top-1];
}

返回“top”前一个即可。

//获取栈中有效元素个数
int StackSize(Stack* ps) {
	assert(ps);
	return ps->top;
}

返回“top”就好。

2.4 检查是否为空

//检测是否为空
bool StackEmpty(Stack* ps) {
	assert(ps);
	
	return ps->top == 0;
}

判断"top"是否等于初始值即可。

3 总结

栈可以用来快速解决一些特殊化问题，它独特的性质值得我们学习使用。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-16，如有侵权请联系 cloudcommunity@tencent.com 删除

存储

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度