手撕数据结构—栈

news/2024/10/22 13:17:25/

Tips

  1. 不得不再次提一下这个语法问题,当数组创建的时候,进行初始化的时候,分为全部初始化或者说部分初始化,对于不完全初始化而言,剩下的部分就全部默认为零。现在比如说你想对整型数组的1万个元素把它全部变成-1,不能够仅仅在一个花括号里面写个-1,只是第一个元素变成-1,然后其他的都变成0了。之后你只能用memset

栈以及先进后出原则

  1. 栈和队列其实也是一个线性表。线性表也就是说你这个数据至少在逻辑上都是依次线性存储,一个一个挨着挨着这样存储这么一个概念。

  1. 栈作为一种特殊的线性表,它只允许在固定的一端进行数据的插入或删除元素操作。进行数据插入和删除操作的那一端就被称为栈顶。因此很容易理解栈中的数据元素遵守后进先出原则。

压栈与出栈

  1. 栈的插入操作叫做进栈/压栈/入栈,这是在栈顶完成的。

  1. 栈的删除操作叫做出栈,这也是在栈顶完成的。所以说它是在同一端进行操作。

  1. 在这边值得一提的是,比如说现在有一堆元素,对于同一进栈的顺序,但是出栈序列可以多种多样,因为并没有规定什么时候可以出栈,你可以使所有元素放进栈里面之后再依次出栈;当然你也可以是在边进栈的过程中可以出栈。我随便举个例子好了:比如说进栈序列为1234,那么出栈序列可以比如为1432,2341,3421,但是断然断然不可能是3124。


栈的实现

  1. 栈的话可以用数组去实现,也可以用链表去实现。肯定是数组,用数组来实现栈的话嘎嘎香啊,比如说你就可以把数组的右端当成一个栈的栈顶。如果要说真有一个弊端的话,那就是说用数组来模拟栈的话需要扩容。

  1. 那如果非要用链表去实现,也是完全可以的:能用单链表就用单链表,你用双向链表的话,还多一个指针呢,能省一点就是一点。

  1. 但是用单链表的话由于尾删啊尾插啊这些操作都需要去从phead开始去往后去遍历去找尾(注意链表不支持下标访问操作),这会相当的麻烦,因此就想了一个办法。把整个链表的左端当成栈顶,那么这样子的话,我的入栈与出栈相当于单链表的头插头删,效率非常之高。

  1. 但如果说非要选一个的话,用数组和链表来模拟的话都非常可以,因为都是O(1)的插入删除(数组的话可以支持下标访问,把数组的右端当成栈顶;链表的话把他的左端当成栈顶,头插头删也是O(1))。可能你还是会选择链表,但是别忘了数组的缓存命中率与利用率比链表要高


栈的创建(创建结构体)

  1. 凡是有多个数据,都放到一个结构体里面。

  1. 对于这个结构体有三个要素,一个是容量,一个是栈顶top,还有一个我是等会儿从堆区开辟内存空间之后返回来的地址,需要用一个指针接收一下,标记一下地址。

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

栈的初始化

  1. 在初始化的时候有一个比较容易出错的地方,就是必须得先搞清楚这个top到底是什么东西,我就假定这个top指向此时此刻的栈顶元素。那么这时候由于要初始化,此时栈顶也压根儿没有任何元素,因此top就指向-1/那如果我说这个top是栈顶元素的下一个位置,那此时此刻初始化的时候,这个top应该指向0。

  1. 我们为了跟之前的顺序表保保持一致,初始化的时候,这个top就给他弄成0。此时此刻,你只需要记住top的一个含义:他现在就表示栈中的元素个数

#define INIT_CAPACITY 5
void STInit(ST* ps)
{assert(ps);ps->p = (STDataType*)malloc(sizeof(STDataType) * INIT_CAPACITY);if (ps->p == NULL){perror("STInit::Malloc");return;}ps->top = 0;ps->capacity = INIT_CAPACITY;
}

栈的销毁

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

入栈

void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* pp = (STDataType*)realloc(ps->p, sizeof(STDataType) * (ps->capacity) * 2);if (pp == NULL){perror("STPush::Realloc");return;}ps->p = pp;ps->capacity *= 2;}ps->p[ps->top] = x;ps->top++;
}

栈的判断是否为空

bool STEmpty(ST* ps)
{assert(ps);return ps->top==0;
}

栈的求元素个数

int STSize(ST* ps)
{assert(ps);return ps->top;
}

出栈

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

栈的求栈顶元素

int STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->p[ps->top - 1];
}

注:

  1. 虽然从代码上看起来与顺序表非常非常的相像。但是栈的话一定要记住他的特性,那就是后进先出。比如说:23458,我如果要访问5,那么8就必须先出去,如果说我要访问3,那么458就必须先出去。正是因为这种后进先出的特性,这也导致了我们没有写打印栈这种函数,因为栈这种玩意儿,他是不支持去遍历的,这是规定死的。

  1. 这些都是由栈的性质决定的,否则他就不叫做栈了。对于先进栈的数据,想要对他进行任何的操作,包括访问与打印,都必须把它之前栈顶的元素全部弹出去才可以,不然永远只能对栈顶的那个元素动手。


http://www.ppmy.cn/news/33739.html

相关文章

用Pytorch构建一个喵咪识别模型

本文参加新星计划人工智能(Pytorch)赛道:https://bbs.csdn.net/topics/613989052 目录 一、前言 二、问题阐述及理论流程 2.1问题阐述 2.2猫咪图片识别原理 三、用PyTorch 实现 3.1PyTorch介绍 3.2PyTorch 构建模型的五要素 3.3PyTorch 实现的步骤 3.3.…

Mybatis(一):环境搭建

Mybatis(一):环境搭建前言一、MyBatis简介1、MyBatis历史2、MyBatis特性3、MyBatis下载4、和其它持久化层技术对比二、搭建MyBatis1、开发环境2、创建maven工程2.1 打包方式:jar2.2 引入依赖3、创建MyBatis的核心配置文件4、创建m…

hash值——软件中的唯一标识符

在软件中,“ hash”这个词有多种含义,但是我们在这里讨论的是维基百科所谓的 “cryptographic hash function”.。 hash是什么 简而言之,hash是字母和数字的字符串,意味着通过一个较小的、唯一的代码来识别一组信息。您可能在其…

RapidAI/paddleocr_convert:PaddleOCR中模型快速转换为ONNX格式

目录RapidAI/paddleocr_convert使用步骤更新日志RapidAI/paddleocr_convert 本仓库主要是针对性地将PaddleOCR中推理模型转换为ONNX格式。注意: 输入:推理模型的url或者本地tar路径输出:转换后的ONNX模型如果是识别模型,需要提供对…

图形视图框架 事件处理(item)

在图形界面框架中的事件都是先由视图进行接收,然后传递给场景,再由场景传递给图形项。通过键盘处理的话,需要设置焦点,在QGraphicsScene中使用setFoucesItem()函数可以设置焦点,或者图形项使用s…

技术分享 | PBM备份恢复

作者:张洪 爱可生南区 DBA 团队成员,主要负责mysql故障处理及相关技术支持。爱好旅游,摄影。 本文来源:原创投稿 *爱可生开源社区出品,原创内容未经授权不得随意使用,转载请联系小编并注明来源。 概述 Per…

下载并导入MySQL示例数据库employees

MySQL示例数据库employees一、下载employees数据库二、MySQL官方参考手册三、具体步骤3.1 下载test_db3.2 在test_db-master中打开cmd(进入test_db-master目录)3.3 run-install3.4 验证employee数据3.5 show databases\tables & select * from departments**3.6 select * f…

前端git必备技能,如何合并分支以及出现合并冲突后如何解决

文章目录一、合并分支二、可能出现的冲突和解决三、过程分享一、合并分支 注意,我们常说的master或main主干也可以理解为分支,可以是分支合并到主干,或分支合并到分支。 需求:cloudweb的2.6.0和2.6.1是并行开发的,现…