当前位置: 首页 > news >正文

数据结构——栈的基本操作

前言

介绍

🍃数据结构专区:数据结构

参考

该部分知识参考于《数据结构(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写为一种结构体类型,让我们在学习顺序表时写起来就有些困难,在前面学会之后看到这里就游刃有余了!

相关文章:

数据结构——栈的基本操作

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

Chainlit集成LlamaIndex实现知识库高级检索(组合对象检索)

检索原理 对象组合索引的原理 是利用IndexNode索引节点&#xff0c;将两个不同类型的检索器作为节点对象&#xff0c;使用 SummaryIndex &#xff08;它可以用来构建一个包含多个索引节点的索引结构。这种索引通常用于从多个不同的数据源或索引方法中汇总信息&#xff0c;并能…...

万界星空科技铜拉丝行业MES系统,实现智能化转型

一、铜拉丝行业生产管理的难点主要体现在以下几个方面&#xff1a; 1、标准严格&#xff1a;铜线产品对质量的要求极高&#xff0c;特别是在电气性能、导电性、耐腐蚀性等方面&#xff0c;任何微小的瑕疵都可能影响产品的使用效果和安全性。 2、过程监控&#xff1a;生产过程…...

ECCV 2024 现场:参会者付高价、跨万里,却无法入场?

ECCV&#xff08;European Conference on Computer Vision&#xff0c;欧洲计算机视觉国际会议&#xff09;是计算机视觉领域的重要国际会议之一&#xff0c;与CVPR和ICCV并称为计算机视觉的三大顶级会议。 ECCV2024是该系列会议的第18届会议&#xff0c;2024年9月29日至10月4…...

使用rsync+jenkins实现服务自动部署全流程

项目背景&#xff1a;城市政务云服务器没有上k8s&#xff0c;所有后端服务都是原始方式部署启动 &#xff08;java -jar xxx.jar&#xff09;&#xff0c;那么有没有方式简化部署难度&#xff0c;实现自动部署&#xff1f;当然是有的&#xff0c;下面详细介绍&#xff08;以Cen…...

python 实现decision tree决策树算法

decision tree决策树算法介绍 决策树算法&#xff08;Decision Tree Algorithm&#xff09;是一种基于输入特征对实例进行分类的树结构模型&#xff0c;主要用于分类和回归任务。其基本原理是根据训练数据的特征属性和类别标签之间的关系&#xff0c;生成一个能够对新样本进行…...

前端大模型入门:实战篇之Vue3+Antdv+transformers+本地模型实现增强搜索

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

《向量数据库指南》——Fivetran 的 Partner SDK:构建自定义连接器和目标

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

微信小程序的 button 标签的边框如何去除?

目录 问题描述&#xff1a; 问题原因&#xff1a; 解决办法&#xff1a; 方案一 方案二 问题描述&#xff1a; 实际开发中会发现这个 button 自带有样式&#xff0c;当背景颜色设置为白色的时候还有一个黑色的边框&#xff0c;刚开始那个边框怎么都去不掉 无法去除的边框…...

20240926 关于Goland处理wsl-GOROOT原理猜测

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

Anki 学习日记 - 卡片模版 - 单选ABCD(纯操作)

摘要&#xff1a;在不懂前端语言的情况下自定义卡片模版&#xff0c;卡片模版的字段 安装&#xff08;官网&#xff09;&#xff1a;Anki - powerful, intelligent flashcards (ankiweb.net) 一、在哪能修改卡片模版 管理笔记模板 - > 添加 -> 问答题 -> 设置名称 二…...

钉钉x昇腾:用AI一体机撬动企业数字资产智能化

“走红”近两年后&#xff0c;大模型正在加速走进千行万业。 由于大模型的主要模态是文字和图片&#xff0c;恰好是数字化办公最基础的内容要素&#xff0c;办公于是成了离AI最近的场景。 公文写作、表格生成、提炼大纲、文本翻译、代码润色、数据统计、智能问答……越来越多…...

【C/C++】 秋招常考面试题最全总结(让你有一种相见恨晚的感觉)

目录 1.C程序编译链接过程 2.浅拷贝和move有区别吗 3.深拷贝和浅拷贝的区别 4.空类的大小 5.类的继承有几种方式&#xff0c;区别是什么&#xff1f; 六、extern 关键字的作用 七、static关键字的作用 八、指针和引用的区别 九、C内存分配方式 十、结构体对齐…...

CSS面试真题 part1

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

针对考研的C语言学习(定制化快速掌握重点5)

顺序表 特点&#xff1a; 写代码主要就是增删改查&#xff01;&#xff01;&#xff01; 写代码的边界性非常重要以及考研插入和删除的位置都是从1开始&#xff0c;而数组下标是从0开始 【注】下标和位置的关系 线性表最重要的是插入和删除会涉及边界问题以及判断是否合法 …...

构建高效房屋租赁系统:Spring Boot应用

1 绪论 1.1 研究背景 中国的科技的不断进步&#xff0c;计算机发展也慢慢的越来越成熟&#xff0c;人们对计算机也是越来越更加的依赖&#xff0c;科研、教育慢慢用于计算机进行管理。从第一台计算机的产生&#xff0c;到现在计算机已经发展到我们无法想象。给我们的生活改变很…...

学习单片机编程和硬件设计步骤

学习单片机编程和硬件设计可以分为几个步骤&#xff1a; 理解基本概念&#xff1a;首先需要了解单片机的基本概念、硬件结构和工作原理 。 选择开发平台&#xff1a;选择一个合适的单片机系列作为起点&#xff0c;如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…...

两个向量所在平面的法线,外积,叉积,行列式

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

C++之 友元重载 以及最常用的几种友元函数

在之前的友元中就曾经讲过&#xff0c;我们为了去访问修改私有成员中的数据时&#xff0c;只能通过公有的办法去进行访问操作&#xff0c;非常的局限。所以C引用了友元函数&#xff0c;只要加上friend关键字&#xff0c;C的这个类&#xff0c;会自动把这个函数的权限拉到类内&a…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...