【数据结构】栈的详解

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

☃️个人主页:fighting小泽
🌸作者简介:目前正在学习C语言和数据结构
🌼博客专栏:数据结构
🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻

1.栈

1.1栈的概念及结构

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

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

我们的顺序表链表的作用就是单纯的增删查改数据,但是栈除了存储数据还有一个后进先出的性质。

假如说我们要在栈中存储1、2、3、4,那么它们就会依次入栈,1在栈底,4在栈顶
【数据结构】栈的详解
但是当我们想出栈的时候是不是只能4、3、2、1呢?
其实不是的,我们可以入一个元素出一个元素,也可以入一个出两个,总之按自己的需求来定,但也要确保出栈顺序正确。
【数据结构】栈的详解
我们来看两个题:

  1. 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出
    栈的顺序是( )。
    A 12345ABCDE
    B EDCBA54321
    C ABCDE12345
    D 54321EDCBA
  2. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
    A 1,4,3,2
    B 2,3,4,1
    C 3,1,4,2
    D 3,4,2,1

大家可以仔细想一想哦
【数据结构】栈的详解
【数据结构】栈的详解

1.2栈的实现

我们实现栈可以用两种方式,一种是通过顺序表来实现,一种是通过链表来实现。哪种方式好呢?

  • 在前面线性表的学习中我们知道,顺序表的优点是尾插尾删很方便,但是链表想要尾插尾删还要遍历一遍链表,效率就会很低。
  • 顺序表虽然存在空间不足问题,需要不断扩容。但是扩容的代价很低,而且到后面扩的会越来越慢

这样想一想用顺序表来实现栈是不是更好一些。

如果想用链表来实现栈,可以用链表尾当栈底,链表头当栈顶。插入删除数据就进行头插头删,感兴趣的朋友可以试一试。
【数据结构】栈的详解

栈的结构体的定义

栈的结构体其实和顺序表差不多,一个动态开辟的数组,一个栈的容量。

  • 注意 top 我们要决定它指向栈顶还是栈顶的下一个元素。如果top初始化为0,则它指向栈顶的下一个元素。如果top初始化为-1,则它指向栈顶元素。
  • 我比较喜欢初始化为0,1是top还可以表示元素的个数,可以用来判断栈是否满了。2是插入元素的时候直接在top的位置插入就行,然后再top++即可。

这里根据大家喜好设定就行。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

Stack.h

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


typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst);//初始化栈

void STDestroy(ST* pst);//销毁栈

void STPush(ST* pst, STDataType x);//栈顶插入元素

void STPop(ST* pst);//栈顶删除元素

STDataType STTop(ST* pst);//获得栈顶元素

bool STEmpty(ST* pst);//判断栈是否为空

int STSize(ST* pst);//获得栈的元素个数

Stack.c

1.初始化栈和销毁栈

初始化的时候要注意参数传的是形参,要用assert判断一下。
初始化时我们可以先给栈开辟一些空间,也可以不开辟,等到要插入数据时再开辟。

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

对栈进行销毁,我们只需要把动态开辟的空间a给释放置空了,把其它数据置为0即可。


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

2.栈顶插入元素

首先我们要判断栈是否满了,若栈的容量为0,则开辟一部分空间。若栈的空间满了,就将栈的空间扩大二倍。
如果栈没满,我们可以直接在top位置插入我们想插入的元素,然后top++即可。

void STPush(ST* pst, STDataType x)
{
	assert(pst);

	if (pst->capacity == pst->top)
	{
		pst->capacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		pst->a = (STDataType*)realloc(pst->a,sizeof(STDataType) * pst->capacity);
	}
	pst->a[pst->top] = x;
	pst->top++;
}

3.栈顶删除元素

删除元素的话,我们直接让top 减一即可。
注意当top为0,即没有元素的时候我们就不能再减下去了,不然会访问到不属于我们的空间。所以我们可以用一个STEmpty函数判断栈是否为空。

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

如果栈为空,就返回真。如果栈不为空,就返回假

bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

4.获得栈顶元素和元素个数

我们直接返回栈顶的前一个元素即可。
注意:若栈为空,则不能获得栈的元素。所以要判断栈是否为空。

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}

直接返回栈顶的下标即可。之所以写这个函数,是因为别人不知道我们的top指向栈顶还是栈顶的下一个元素。所以直接让别人用就完了。

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

5.结尾

这些就是我给大家分享的关于栈的知识啦,是不是很简单啊。希望我们都能有所收获!
先赞后看,养成习惯!!^ _ ^
码字不易,大家的支持就是我坚持下去的动力,点赞后不要忘了关注我哦!

如有错误,还请您批评改正(。ì _ í。)文章来源地址https://www.toymoban.com/news/detail-450190.html

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

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

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

相关文章

  • 数据结构---栈的实现

    前言 一、什么是栈? 二、 栈的实现 1. 栈的结构 2. 栈的接口实现过程 总结 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是

    2024年02月02日
    浏览(65)
  • 数据结构-栈的实现

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

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

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

    2024年02月01日
    浏览(41)
  • 【数据结构与算法】栈的讲解

    栈(stack)是限定仅在表尾进行插入和删除操作的线性表。 我们把 允许插入和删除的一段称为栈顶(top) , 另一端称为栈底 , 不含任何数据元素的栈称为空栈 。 栈又称为后进先出的线性表 。 进一步理解栈,栈首先他是一个 线性表 ,所以栈元素具有前驱后继关系。 栈的插入操

    2023年04月08日
    浏览(39)
  • 【数据结构—栈的实现(数组栈)】

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

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

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

    2024年02月09日
    浏览(39)
  • 【数据结构】栈的实现(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)
  • 数据结构:栈的实现(C实现)

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

    2024年02月13日
    浏览(63)
  • 【数据结构】栈的远房亲戚——队列

    大家好,很高兴又和大家见面啦!!! 在经过前面内容的介绍,我们已经知道了什么是栈,以及栈的一些基本操作。在介绍完如何通过C语言实现顺序栈之后,我们又详细介绍了顺序栈中的共享栈以及链栈的C语言实现,相信大家现在对栈已经有了一定的理解了。今天我们将来

    2024年01月20日
    浏览(38)
  • 数据结构之栈的基本操作

    该顺序栈涉及到了存储整型数据的顺序栈还有存储字符型数据的顺序栈 实现的功能有:入栈、出栈、判断是否为空栈、求栈的长度、清空栈、销毁栈、得到栈顶元素 此外根据上述功能,编写了数值转换(十进制转化八进制)方法、括号匹配方法。 控制台界面展示: 进栈展示

    2024年01月23日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包