【数据结构】一篇带你彻底了解栈

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

栈的概念及结构

栈:一种线性数据结构,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶 (Top), 另一端称为栈底 [Bottom]。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。即最后进入的元素最先被访问。

  • 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
  • 出栈:栈的删除操作叫做出栈。出数据也在栈顶。
    【数据结构】一篇带你彻底了解栈
  • 栈具有以下几个特点:
    1. 后进先出(LIFO):最后进入栈的元素最先被访问,而最先进入栈的元素最后被访问。
    2. 只允许在一端进行插入和删除操作:栈通常只允许在栈顶进行插入和删除操作,而不允许在其他位置进行操作。
    3. 栈顶指针:栈顶指针指向栈顶元素,它随着元素的插入和删除而改变。

  • 栈的结构
    对于栈来讲,理论上线性表的操作特性它都具备,可由于它的特殊性,所以针对它在操作上会有些变化。特别是插入和删除操作.那栈的结构用数组还是链表实现?

使用数组可以比链表更快,因为数组的数据在内存中是连续存储的,下标可以随机访问。而链表的数据则是分散存储的。意味着,当CPU访问数组时,它可以利用缓存行(cache line)的特性,从内存中读取多个相邻的元素到缓存中,以便更快地访问这些元素。而对于链表,则需要在内存中跳跃,以获取每个元素的地址,这可能会导致缓存未命中(cache miss),从而降低访问速度。但是数组长度是固定的,如果需要动态扩展栈的大小,需要进行复制和移动操作,比较耗费时间和空间。链表实现的栈可以动态扩展大小,但是需要额外的指针空间来存储链表节点,访问元素时速度可能会比较慢.下面我总结下用数组和链表各自的优缺点。


  • 用数组实现的优点

1 . 数组在内存中是连续存储的,因此访问元素时速度较快。CPU高速缓存命中率会更高。
2. 下标的随机访问。尾插尾删效率不错.
3. 数组实现相对简单,不需要额外的指针来维护元素之间的关系。

  • 数组实现的缺点

1 . 数组的大小是固定的,因此在栈空间不足时需要进行扩容操作,这可能会导致性能下降。
2 . 在删除元素时,需要移动数组中的其他元素,这也可能会导致性能下降。


  • 用链表实现的优点

1 .链表的大小可以动态调整,因此可以更好地利用空间。
2 . 任意位置插入删除O(1) ,链表的性能较高,因为不需要移动其他元素。

  • 链表实现的缺点

1 . CPU高速缓存命中率会更低,不是连续存储的,因此访问元素时速度较慢。
2. 不支持下标的随机访问.

  • 用链表还是用数组结构实现这个问题的答案取决于具体的应用场景和需求,本章节我们使用数组存储结构来实现.
    栈数组存储结构
typedef int STDateType; // 定义栈元素类型
typedef struct StackNode
{
	STDateType * a;  // 数组指针
	int top;		 // 栈顶
	int capacity;	// 栈的容量
}st;

a 是一个指向栈数据存储区的指针,top 是栈顶的索引值,capacity 是栈的容量。文章来源地址https://www.toymoban.com/news/detail-452550.html


栈接口的实现

栈的初始化

  • 这里讲解下有的人是把top给成-1的,栈顶指针 top 被初始化为 -1,表示栈中没有任何元素。当向栈中插入第一个元素时,我们需要将 top 的值加 1,然后将该元素存储在数组中 top 所指向的位置。此时,top 的值为 0,表示栈中有一个元素。因此,栈中有一个元素是因为插入了第一个元素。所以这里要取分一下.top给成0还是-1,根据场景应用给成多少。
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;	
	pst->top = 0;   // top 指向栈顶数据的下一个位置

	pst->capacity = 0;
}

入栈

  • 入栈步骤
    1. 首先判断栈是否已满,即栈顶指针 top 是否等于栈的容量 capacity。如果栈已满,则需要扩容,这里的扩容策略是将栈的容量翻倍,如果栈的容量为 0,则新分配的容量为 4,将扩容后的数组 tmp 赋值给原来的数组 pst->a,并更新栈的容量为 newCapacity。
    2. 将元素 x 存储在栈顶指针 top 所指向的位置,然后将栈顶指针 top 加 1,指向下一个空闲位置,以便下一次入栈操作。
void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity) //判断栈是否已满
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));//扩容
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp; //赋值给原来的数组
		pst->capacity = newCapacity; //更新栈的容量
	}

	pst->a[pst->top] = x; //入栈
	pst->top++; //+1 指向下一个空闲位置
}

出栈

  • 判断栈中是否存在元素,如存在我们将栈顶指针 top 减一,即 pst->top–,表示将栈顶元素弹出。
void STPop(ST* pst)
{
	assert(pst); //断言判断是否指针为空
	assert(!STEmpty(pst)); //判断栈中是否存在元素

	pst->top--; //将栈顶元素弹出。
}

获取栈顶元素

  • 首先确保栈不为空,如不为空返回栈顶元素的值,即数组 a 中下标为 top - 1 的元素。
STDataType STTop(ST* pst)
{
	assert(pst);  //断言判断是否指针为空
	assert(!STEmpty(pst)); //判断栈中是否存在元素

	return pst->a[pst->top - 1]; //返回栈顶元素的值
}

判断栈是否为空

  • 如果栈顶值为0,就代表栈为空.返回真,反之返回假.
bool STEmpty(ST* pst)
{
	assert(pst);  //断言判断是否指针为空
	return pst->top == 0; //判断是否为空
}

获取栈中有效元素个数

  • 该代码没有什么可说的…直接看吧
int STSize(ST* pst)
{
	assert(pst);   //断言判断是否指针为空

	return pst->top; //返回栈的元素个数
}

栈的销毁

  • 当我们不打算使用这个栈时,我们需要把它销毁,其实也就是在内存中将它释放掉,以便于留出空间给其他程序或软件使用。 我们只需要把栈的数组空间释放,避免内存泄漏。同时将指向数组的指针 a 置为 NULL,避免出现野指针。最后,将栈的容量 capacity 和栈顶指针 top 置为 0,表示栈已经被销毁。
void STDestroy(ST* pst)
{
	assert(pst); //断言判断是否指针为空

	free(pst->a); //函数释放栈的数组空间
	pst->a = NULL; //置为NULL,避免出现野指针
	pst->top = pst->capacity = 0;  //将栈的容量 capacity 和栈顶指针 top 置为 0
}

总结

  • 栈是一种简单但非常有用的数据结构,掌握它的基本概念、操作和实现方式对于编程学习和刷题,后面的面试都非常重要。

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

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

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

相关文章

  • 【C语言】-- 一篇带你了解指针,内存,解引用

    目录 1、什么是指针? 1.1 内存 1.2 指针变量 二、指针和指针类型 1、指针类型 2、指针+整数 3、指针的解引用 三、野指针 1、野指针成因 (1) 指针未初始化 (2) 指针越界访问 (3) 指针指向的空间释放 2、如何规避野指针 四、指针运算 1、指针-指针        本篇文章我们来了解C语

    2024年02月16日
    浏览(56)
  • [ C++ ] 一篇带你了解C++中隐藏的this指针

    本篇文章我们将一起讨论在有趣的知识点--隐藏的this指针。本篇我们要使用到之前我们所学习到的C++类与对象(1),如果有各位小伙伴还不曾了解类与对象的简单思想,可以访问上篇博客:[ C++ ] 带你一篇了解什么是OOP(面向对象编程),什么是封装? -- 类与对象(上) 目录 1.

    2024年02月07日
    浏览(56)
  • [C++] 一篇带你了解C++中动态内存管理,new让大家都有对象

      目录 1、C/C++内存分布 2.、C语言中动态内存管理方式:malloc、calloc、realloc 3、C++内存管理方式 3.1 new/delete操作内置类型 3.2 new和delete操作自定义类型 3.3 malloc与new的异常处理机制 4、operator new与operator delete函数 4.1 operator new与operator delete函数 4.1.1 operator new源码 4.1.2 operator del

    2024年02月13日
    浏览(79)
  • 【C语言】-- 一篇带你了解C语言内存五大区——栈区,堆区,全局区,常量区,代码区

    目录 1 C语言的内存分区 1.1 内存五大分区 1.2 内存分区简介 1.2.1 栈区(stack) 1.2.2 堆区(heap) 1.2.3 (全局)静态区 1.2.4 常量区 1.2.5 代码区 创作不易,如果本篇博客对您有一定的帮助,大家记得留言+点赞哦。 C语言已经持续学习一段时间了,今天特此总结一下关于C语言内存的五大区

    2024年02月16日
    浏览(48)
  • [C++]类与对象(下) -- 初始化列表 -- static成员 -- 友元 -- 内部类,一篇带你深度了解。

      目录 1、再谈构造函数 1.1 构造函数体赋值 1.2 初始化列表 1.2.1 初始化列表的意义 1.3 explicit 2、static成员 2.1 问题引入 2.2 特性 3、友元 3.1 友元函数 3.2 友元类 4、内部类 在创建对象时,编译器通过调用构造函数,给对象中各个成员变量一个合适的初始值。 我们构造函

    2024年02月12日
    浏览(43)
  • 【Python】一篇带你掌握数据容器之列表

    目录 前言: 一、列表 1.列表的定义 2.列表的下标索引 3.列表的常用操作 (1)index方法:查找某元素的下标 (2)修改特定位置下标的元素 (3)insert(下标,元素)方法:插入元素 (4)append(元素)方法:追加元素1 (5)extend(其他数据容器)方法:追加元素2 (6)del(列表

    2024年02月05日
    浏览(51)
  • 手把手教你 ,带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法,其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 可以理解为一遍摸扑克牌,一边进行排序 在待排序的元素中,假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(60)
  • 【数据结构】一篇文章带你彻底学会《后缀表达式》

    创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡𖥦)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 🔥c语言系列专栏:c语言之路重点知识整合 🔥 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ 后缀表

    2024年02月05日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包