数据结构——栈的基本操作
前言
介绍
🍃数据结构专区:数据结构
参考
该部分知识参考于《数据结构(C语言版 第2版)》55 ~ 59页
🌈每一个清晨,都是世界对你说的最温柔的早安:ૢ(≧▽≦)و✨
1、栈的基本概念
栈(Stack)是一种遵循后进先出(LIFO, Last In First Out)原则的有序集合。
- 数组实现:使用数组的一个连续空间来存储栈中的元素,通常使用一个指针(或索引)来指示栈顶的位置。数组实现的栈在添加和删除元素时,如果数组已满或为空,可能需要进行扩容或缩容操作,这可能会涉及到额外的性能开销。
- 链表实现:使用链表的头部(或尾部,取决于具体实现)作为栈顶,通过修改链表的头指针(或尾指针)来实现元素的添加和删除。链表实现的栈在添加和删除元素时,不需要进行扩容或缩容操作,因此通常具有更好的性能。
2、数组栈的实现
2.1 宏定义
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
2.2 数组栈的结构体定义
#define MAXSIZE 100 //顺序表的存储范围
#define STACK_INCREMENT 2 //存储空间分配增量//这里假定SElemType是int类型
typedef int SElemType;typedef struct
{SElemType* base; //栈底指针SElemType* top; //栈顶指针int stacksize; //栈可用的最大容量
}SqStack;
2.3 初始化数组栈
//初始化栈
Status InitStack(SqStack& S)
{S.base = new SElemType[MAXSIZE];if (!S.base)exit(OVERFLOW);S.top = S.base; //top初始化为base,空栈S.stacksize = MAXSIZE; //stacksize的最大容量为MAXSIZEreturn OK;
}
2.4 销毁数组栈
//销毁栈
Status DestroyStack(SqStack& S)
{free(S.base);S.base = NULL;S.top = NULL; //规范指针S.stacksize = 0;return OK;
}
2.5 清空数组栈
//清除栈
Status CleanStack(SqStack& S)
{S.top = S.base; //让top指针指回栈底即可return OK;
}
2.6 判空
//判空
Status StackEmpty(SqStack S)
{if (S.top == S.base) //如果栈顶和栈底指向同一个位置则证明栈为NULLreturn OK;elsereturn ERROR;
}
2.7 获取栈内元素个数
//获取栈内元素数量
int StackLength(SqStack S)
{return S.top - S.base;
}
2.8 获取栈顶元素
//获取栈顶元素
SElemType GetTop(SqStack S)
{//判断栈是否为空if (!StackEmpty(S))//不为空即可获取元素{return *(--S.top);}else{return ERROR;}
}
2.9 入栈
//入栈
Status Push(SqStack& S, SElemType e)
{//插入元素为新的栈顶元素if (S.top - S.base == S.stacksize)//满栈{S.base = (SElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));//判断是否扩容成功if (!S.base)exit(OVERFLOW);//如果扩容失败,退出程序S.top = S.base + S.stacksize;}*(S.top)++ = e; //这里是先对S.top解引用后存入数据e,随后将top指针向后移动一位
}
2.10 出栈
//出栈
Status Pop(SqStack& S, SElemType &e)
{//删除栈顶元素,并返回其值if (!StackEmpty(S)) //栈不为空进行操作{e = *(--S.top);return OK;}elsereturn ERROR;
}
2.11 visit()函数
// 定义一个函数visit,用于打印元素
void visit(SElemType e)
{std::cout << e << " ";
}
2.12 遍历数组栈
// 定义一个函数用于遍历栈中的元素并对每个元素执行visit函数
void StackTraverse(SqStack S, void(*visit)(SElemType))
{SElemType* p = S.base;while (S.top > p) //p指向栈元素visit(*p++); //对该栈调用visit(),p指针上移一个存储单元printf("\n");
}
2.13 整体代码(含测试代码)
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;#define MAXSIZE 100 //顺序表的存储范围
#define STACK_INCREMENT 2 //存储空间分配增量//这里假定SElemType是int类型
typedef int SElemType;typedef struct
{SElemType* base; //栈底指针SElemType* top; //栈顶指针int stacksize; //栈可用的最大容量
}SqStack;//SqStack S; //声明该栈//初始化栈
Status InitStack(SqStack& S)
{S.base = new SElemType[MAXSIZE];if (!S.base)exit(OVERFLOW);S.top = S.base; //top初始化为base,空栈S.stacksize = MAXSIZE; //stacksize的最大容量为MAXSIZEreturn OK;
}//销毁栈
Status DestroyStack(SqStack& S)
{free(S.base);S.base = NULL;S.top = NULL; //规范指针S.stacksize = 0;return OK;
}//清除栈
Status CleanStack(SqStack& S)
{S.top = S.base; //让top指针指回栈底即可return OK;
}//判空
Status StackEmpty(SqStack S)
{if (S.top == S.base) //如果栈顶和栈底指向同一个位置则证明栈为NULLreturn OK;elsereturn ERROR;
}//获取栈内元素数量
int StackLength(SqStack S)
{return S.top - S.base;
}//获取栈顶元素
SElemType GetTop(SqStack S)
{//判断栈是否为空if (!StackEmpty(S))//不为空即可获取元素{return *(--S.top);}else{return ERROR;}
}//入栈
Status Push(SqStack& S, SElemType e)
{//插入元素为新的栈顶元素if (S.top - S.base == S.stacksize)//满栈{S.base = (SElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));//判断是否扩容成功if (!S.base)exit(OVERFLOW);//如果扩容失败,退出程序S.top = S.base + S.stacksize;}*(S.top)++ = e; //这里是先对S.top解引用后存入数据e,随后将top指针向后移动一位
}//出栈
Status Pop(SqStack& S, SElemType &e)
{//删除栈顶元素,并返回其值if (!StackEmpty(S)) //栈不为空进行操作{e = *(--S.top);return OK;}elsereturn ERROR;
}// 定义一个函数visit,用于打印元素
void visit(SElemType e)
{std::cout << e << " ";
}// 定义一个函数用于遍历栈中的元素并对每个元素执行visit函数
void StackTraverse(SqStack S, void(*visit)(SElemType))
{SElemType* p = S.base;while (S.top > p) //p指向栈元素visit(*p++); //对该栈调用visit(),p指针上移一个存储单元printf("\n");
}int main() {int j;SqStack s;SElemType e;InitStack(s);for (j = 1; j <= 12; j++)Push(s, j);printf("栈中元素依次为\n");StackTraverse(s, visit);Pop(s, e);printf("弹出的栈顶元素e = %d\n", e);printf("栈空否? %d (1:空 0:否)\n", StackEmpty(s));e = GetTop(s);printf("栈顶元素e = %d,栈的长度为%d\n", e, StackLength(s));CleanStack(s);printf("清空栈后,栈空否? %d (1:空 0:否)\n", StackEmpty(s));DestroyStack(s);printf("销毁栈后,s.top = %u,s.base = %u,s.stacksize = %d\n", s.top, s.base, s.stacksize);
}
3、链表栈的实现
3.1 宏定义
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
3.2 链表栈的结构体定义
typedef int SElemType;
typedef struct StackNode
{SElemType data;struct StackNode* next;
}StackNode, *LinkStack;
3.3 初始化链表栈
//初始化
Status InitStack(LinkStack& S)
{//让栈顶指针指向NULL即可S = NULL;return OK;
}
3.4 清空栈
//清空栈
Status ClearStack(LinkStack& S)
{//创建一个临时指针,遍历该链表后依次释放各个节点StackNode* p;while (S){p = S;S = S->next;delete p;}return OK;
}
3.5 判空
//判空
Status StackEmpty(LinkStack S)
{return S == NULL;
}
3.6 销毁链表栈
//销毁
Status DestroyStack(LinkStack& S)
{ClearStack(S);S = NULL;return OK;
}
3.7 入栈
//入栈
Status Push(LinkStack& S, SElemType e)
{//在栈顶位置插入元素eStackNode* p = new StackNode;p->data = e;p->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}
3.8 出栈
//出栈
Status Pop(LinkStack &S, SElemType& e)
{//删除栈顶元素,并返回该元素if (S == NULL)return ERROR;StackNode * p = S;e = p->data;S = S->next;delete p;return OK;
}
3.9 获取栈顶元素
//获取栈顶元素
SElemType GetTop(LinkStack S)
{//返回S的栈顶元素,并不改变栈顶指针的位置if (S != NULL){return S->data;}
}
3.10 遍历打印
// 遍历栈并打印
void StackTraverse(LinkStack S)
{StackNode* p = S;while (p) {printf("%d ", p->data);p = p->next;}printf("\n");
}
3.11 整体代码(含测试代码)
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;typedef int SElemType;
typedef struct StackNode
{SElemType data;struct StackNode* next;
}StackNode, *LinkStack;//初始化
Status InitStack(LinkStack& S)
{//让栈顶指针指向NULL即可S = NULL;return OK;
}//清空栈
Status ClearStack(LinkStack& S)
{//创建一个临时指针,遍历该链表后依次释放各个节点StackNode* p;while (S){p = S;S = S->next;delete p;}return OK;
}//判空
Status StackEmpty(LinkStack S)
{return S == NULL;
}//销毁
Status DestroyStack(LinkStack& S)
{ClearStack(S);S = NULL;return OK;
}//入栈
Status Push(LinkStack& S, SElemType e)
{//在栈顶位置插入元素eStackNode* p = new StackNode;p->data = e;p->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}//出栈
Status Pop(LinkStack &S, SElemType& e)
{//删除栈顶元素,并返回该元素if (S == NULL)return ERROR;StackNode * p = S;e = p->data;S = S->next;delete p;return OK;
}//获取栈顶元素
SElemType GetTop(LinkStack S)
{//返回S的栈顶元素,并不改变栈顶指针的位置if (S != NULL){return S->data;}
}// 遍历栈并打印
void StackTraverse(LinkStack S)
{StackNode* p = S;while (p) {printf("%d ", p->data);p = p->next;}printf("\n");
}int main()
{LinkStack S;InitStack(S);int e;Push(S, 1);Push(S, 2);Push(S, 3);printf("现在栈内元素为(后进先出):");StackTraverse(S);printf("栈顶元素为:%d\n", GetTop(S));Pop(S, e);printf("现在栈内元素为(后进先出):");StackTraverse(S);printf("弹出一个元素后,栈顶元素为:%d\n", GetTop(S));ClearStack(S);if (StackEmpty(S)) {printf("清空栈后,栈为空\n");}else {printf("清空栈后,栈不为空,证明有问题\n");}DestroyStack(S);return 0;
}
结语
到此我们的两种栈的实现代码就完成了,我们可以发现,在实现栈的过程中远没有当初学习顺序表那么困难,那是因为栈其实就是一种特殊结构的顺序表,并且在前面的学习顺序表过程中,我故意将ElemType写为一种结构体类型,让我们在学习顺序表时写起来就有些困难,在前面学会之后看到这里就游刃有余了!
相关文章:

数据结构——栈的基本操作
前言 介绍 🍃数据结构专区:数据结构 参考 该部分知识参考于《数据结构(C语言版 第2版)》55 ~ 59页 🌈每一个清晨,都是世界对你说的最温柔的早安:ૢ(≧▽≦)و✨ 1、栈的基本概念 栈&#x…...

Chainlit集成LlamaIndex实现知识库高级检索(组合对象检索)
检索原理 对象组合索引的原理 是利用IndexNode索引节点,将两个不同类型的检索器作为节点对象,使用 SummaryIndex (它可以用来构建一个包含多个索引节点的索引结构。这种索引通常用于从多个不同的数据源或索引方法中汇总信息,并能…...

万界星空科技铜拉丝行业MES系统,实现智能化转型
一、铜拉丝行业生产管理的难点主要体现在以下几个方面: 1、标准严格:铜线产品对质量的要求极高,特别是在电气性能、导电性、耐腐蚀性等方面,任何微小的瑕疵都可能影响产品的使用效果和安全性。 2、过程监控:生产过程…...

ECCV 2024 现场:参会者付高价、跨万里,却无法入场?
ECCV(European Conference on Computer Vision,欧洲计算机视觉国际会议)是计算机视觉领域的重要国际会议之一,与CVPR和ICCV并称为计算机视觉的三大顶级会议。 ECCV2024是该系列会议的第18届会议,2024年9月29日至10月4…...

使用rsync+jenkins实现服务自动部署全流程
项目背景:城市政务云服务器没有上k8s,所有后端服务都是原始方式部署启动 (java -jar xxx.jar),那么有没有方式简化部署难度,实现自动部署?当然是有的,下面详细介绍(以Cen…...
python 实现decision tree决策树算法
decision tree决策树算法介绍 决策树算法(Decision Tree Algorithm)是一种基于输入特征对实例进行分类的树结构模型,主要用于分类和回归任务。其基本原理是根据训练数据的特征属性和类别标签之间的关系,生成一个能够对新样本进行…...

前端大模型入门:实战篇之Vue3+Antdv+transformers+本地模型实现增强搜索
本文将之前的文章,实现一个场景的实战应用,包含代码等内容。利用纯前端实现增强的列表搜索,抛弃字符串匹配,目标是使用番茄关键字可以搜索到西红柿 1 准备工作 1.1 了解llm和web开发 web端的ai开发参考 前端大模型入门ÿ…...

《向量数据库指南》——Fivetran 的 Partner SDK:构建自定义连接器和目标
哈哈,说到 Fivetran 的 Partner SDK,这可真是个好东西啊!作为向量数据库领域的“老司机”,我今天就来给大家详细讲讲这个 SDK 的厉害之处,以及如何用它来构建自定义连接器和目标,实现与 Fivetran 自动化数据移动平台的无缝集成。 一、Fivetran Partner SDK:开启自定义连…...

微信小程序的 button 标签的边框如何去除?
目录 问题描述: 问题原因: 解决办法: 方案一 方案二 问题描述: 实际开发中会发现这个 button 自带有样式,当背景颜色设置为白色的时候还有一个黑色的边框,刚开始那个边框怎么都去不掉 无法去除的边框…...

20240926 关于Goland处理wsl-GOROOT原理猜测
GOROOT的原理 go sdk与java jdk类似,是go的编译工具链的集合。 在windows上,我们通过在系统环境变量中添加GOROOT并设置为go sdk地址,使得命令行可以访问到go sdk并执行go test、build等命令,这样设置的变量是全局生效的&#x…...

Anki 学习日记 - 卡片模版 - 单选ABCD(纯操作)
摘要:在不懂前端语言的情况下自定义卡片模版,卡片模版的字段 安装(官网):Anki - powerful, intelligent flashcards (ankiweb.net) 一、在哪能修改卡片模版 管理笔记模板 - > 添加 -> 问答题 -> 设置名称 二…...
钉钉x昇腾:用AI一体机撬动企业数字资产智能化
“走红”近两年后,大模型正在加速走进千行万业。 由于大模型的主要模态是文字和图片,恰好是数字化办公最基础的内容要素,办公于是成了离AI最近的场景。 公文写作、表格生成、提炼大纲、文本翻译、代码润色、数据统计、智能问答……越来越多…...

【C/C++】 秋招常考面试题最全总结(让你有一种相见恨晚的感觉)
目录 1.C程序编译链接过程 2.浅拷贝和move有区别吗 3.深拷贝和浅拷贝的区别 4.空类的大小 5.类的继承有几种方式,区别是什么? 六、extern 关键字的作用 七、static关键字的作用 八、指针和引用的区别 九、C内存分配方式 十、结构体对齐…...

CSS面试真题 part1
CSS面试真题 part1 1、说说你对盒子模型的理解2、谈谈你对BFC的理解3、什么是响应式设计?响应式设计的基本原理是什么?如何做?4、元素水平垂直居中的方法有哪些?如果元素不定宽高呢?5、如何实现两栏布局,右…...

针对考研的C语言学习(定制化快速掌握重点5)
顺序表 特点: 写代码主要就是增删改查!!! 写代码的边界性非常重要以及考研插入和删除的位置都是从1开始,而数组下标是从0开始 【注】下标和位置的关系 线性表最重要的是插入和删除会涉及边界问题以及判断是否合法 …...

构建高效房屋租赁系统:Spring Boot应用
1 绪论 1.1 研究背景 中国的科技的不断进步,计算机发展也慢慢的越来越成熟,人们对计算机也是越来越更加的依赖,科研、教育慢慢用于计算机进行管理。从第一台计算机的产生,到现在计算机已经发展到我们无法想象。给我们的生活改变很…...
学习单片机编程和硬件设计步骤
学习单片机编程和硬件设计可以分为几个步骤: 理解基本概念:首先需要了解单片机的基本概念、硬件结构和工作原理 。 选择开发平台:选择一个合适的单片机系列作为起点,如Arduino、ESP8266/ESP32或STM32系列 。 准备工具和环境&…...

.net Framework 4.6 WebAPI 使用Hangfire
C# 使用 Hangfire 第一章 .net Framework 4.6 WebAPI 使用Hangfire 文章目录 C# 使用 Hangfire前言一、hangfire是什么?二、hangfire的特点三、.net Framework 中hangfire的使用方法第一步:创建WebAPI控制器第二步:添加nuget包第三步 创建startup类新建项目startup类Startu…...

两个向量所在平面的法线,外积,叉积,行列式
偶尔在一个数学题里面看到求两向量所在平面的法线,常规方法可以通过法线与两向量垂直这一特点,列两个方程求解;另外一种方法可以通过求解两个向量的叉积,用矩阵行列式 (determinant) 的方式,之前还没见过,在…...

C++之 友元重载 以及最常用的几种友元函数
在之前的友元中就曾经讲过,我们为了去访问修改私有成员中的数据时,只能通过公有的办法去进行访问操作,非常的局限。所以C引用了友元函数,只要加上friend关键字,C的这个类,会自动把这个函数的权限拉到类内&a…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...