数据结构---栈的实现

这篇具有很好参考价值的文章主要介绍了数据结构---栈的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章目录

  • 前言
  • 一、什么是栈?
  • 二、栈的实现
    • 1.栈的结构
    • 2.栈的接口实现过程
  • 总结

前言

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。


一、什么是栈?

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。

数据结构---栈的实现

二、栈的实现

1.栈的结构

//栈--用数组实现,后进先出
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈元素的下标
	int capacity;//栈元素的个数
}ST;

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

2.栈的接口

1.初始化

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (pst->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	pst->capacity = 4;

	//top不同的初始化方式导致了不同的栈顶元素下标的表示
	//1.top初始化为0,则最终top代表栈顶元素的下一个位置的下标
	//2.top初始化为-1,则最终top代表栈顶元素的下标
	pst->top = 0;
}

2. 销毁

//销毁
void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;

}

3. 插入--入栈

//扩容
void CheckCapacity(ST* pst)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc
		(pst->a, sizeof(STDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
}

//插入数据
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	CheckCapacity(pst);
	pst->a[pst->top] = x;
	pst->top++;
}

插入数据,需要对数组容量进行判断,检测是否需要进行扩容

4. 删除--出栈

//判空
bool STEmpty(ST* pst)
{
	//空的话,返回true
	assert(pst);

	return pst->top == 0;
}


//删除
void STPop(ST* pst)
{
	assert(pst);
	//空的栈,不能删除
	assert(STEmpty(pst) != true);
	pst->top--;
}

删除一般配合判空使用,因为空的栈无法进行删除操作

5. 返回栈顶元素

//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	//空的栈不能返回
	assert(STEmpty(pst) != true);
	STDataType ret = pst->a[pst->top - 1];
	return ret;
}

top不同的初始化方式导致了不同的栈顶元素下标的表示
1.top初始化为0,则最终top代表栈顶元素的下一个位置的下标
2.top初始化为-1,则最终top代表栈顶元素的下标

6.返回元素个数及打印

//返回元素个数
int STSize(ST* pst)
{
	assert(pst);
	//top初始化为0,则最终top代表栈顶元素的下一个位置的下标
	//同时,也代表前面的元素的个数
	return pst->top;
}

//打印
void Print(ST* pst)
{
	while (!STEmpty(pst))
	{
		printf("%d ", STTop(pst));
		STPop(pst);
	}
	printf("\n");

}

栈的性质,导致其无法进行普通的打印,需要利用其接口实现


总结

栈,数据结构的基本结构,它的特殊性质,导致其有着独特的使用场景,后进先出的方式,适用于各种情境,身为学习者的我们,需要充分了解其接口的实现,做到可以独立完成其复刻过程。文章来源地址https://www.toymoban.com/news/detail-434710.html

到了这里,关于数据结构---栈的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-栈的实现

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

    2024年02月05日
    浏览(47)
  • 【数据结构】栈的实现

    栈:是一种受限制的线性表,即只能在尾部进行插入、删除的线性表,而且是一种先进后出的数据结构。尾部这一端又叫做栈顶,另一端叫做栈底。 入栈:向一个栈内插入元素叫做入栈或压栈,它把新元素放到栈顶元素的上面,是它成为新的栈顶元素。 出栈:在栈内删除元

    2024年02月01日
    浏览(41)
  • 数据结构:栈的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 栈:一种特殊的线性结构,其只允许在一端进行插入,删除数据。允许操作数据的一端被称为 栈顶 ,另一端被称为 栈底 。 本篇博客将要实现的是 数组栈 。 对于栈的特殊性,用数组(在数组尾部插入删除数据) 和

    2024年02月13日
    浏览(63)
  • 【数据结构—栈的实现(数组栈)】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、栈 1.1栈的概念及结构 二、栈的实现 2.1头文件的实现—Stack.h 2.2源文件的实现—Stack.c 2.3源文件的测试—test.c 三、栈的实际测试数据展示 3.1正常的出入栈展示: 3.2进栈同时也在出栈的

    2024年02月04日
    浏览(48)
  • 数据结构:线性表(栈的实现)

    栈(Stack)是只允许在一端进行插入或删除操作的线性表.首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作. 进行 数据插入和删除操作的一端 叫 栈顶 ,另一端称为 栈底 . 栈中的元素遵循 后进先出 LIFO(Last In First Out)的原则 压栈 :栈的插入操作叫做进栈/压栈

    2024年02月09日
    浏览(40)
  • 【数据结构】栈的实现(C语言)

    文章目录 1.栈 1.1 栈的定义 1.2 C语言实现栈 1.2.1接口函数 1.2.2栈的创建 1.2.3栈的初始化  1.2.4栈的销毁 1.2.5压栈 1.2.6出栈 1.2.7判断栈是否为空 1.2.8取栈顶元素 1.2.9 栈有多少个数据  1.3 C语言实现栈的具体代码 头文件stack.h 接口函数stack.c 测试函数test.c         栈(stack)又名堆

    2024年02月05日
    浏览(47)
  • 【算法与数据结构】栈的实现详解

    栈的概念: 栈 :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:

    2024年03月11日
    浏览(55)
  • 数据结构-栈的实现(C语言版)

    前言         栈是一种特殊的线性表,只允许在固定的一端进行插入和删除的操作, 进行数据插入和删除的一端叫做栈顶,另一端叫做栈底。  栈中的数据元素遵循后进先出的的原则。 目录 1.压栈和出栈 2. 栈的实现 3.测试代码         压栈:栈的插入操作叫 压栈,入数

    2024年02月13日
    浏览(50)
  • 数据结构之栈的实现(附源码)

    目录 一、栈的概念及结构 ​二、栈的实现 三、初学栈的练习题 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插

    2024年02月07日
    浏览(49)
  • 初阶数据结构(五) 栈的介绍与实现

    💓博主csdn个人主页:小小unicorn💓 ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 栈 :一种特殊的 线性表 ,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数

    2024年02月11日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包