【数据结构】栈的详解

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

☃️个人主页: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)
  • 【数据结构】栈的实现

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

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

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

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

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

    2023年04月08日
    浏览(36)
  • 数据结构:线性表(栈的实现)

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

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

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

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

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

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

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

    2024年01月20日
    浏览(35)
  • 数据结构-栈的实现(C语言版)

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

    2024年02月13日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包