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

embedded/2024/10/4 13:14:27/

前言

介绍

🍃数据结构专区：数据结构

参考

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


http://www.ppmy.cn/embedded/121891.html

相关文章

订阅ROS2中相机的相关话题并保存RGB、深度和点云图

订阅ROS2中相机的相关话题并保存RGB、深度和点云图

系统&#xff1a;Ubuntu22.04 ROS2版本&#xff1a;ROS2 humble 1.订阅ROS2中相机的相关话题并保存RGB图、深度图和点云图 ros2 topic list/stellar_1/rgb/image_raw /camera/depth/image_raw /stellar_1/points2CMakeLists.txt cmake_minimum_required(VERSION 3.15) projec…
阅读更多...
linux部署redis，整合ansible和redis

linux部署redis，整合ansible和redis

准备服务器192.168.45.133&#xff0c;192.168.45.135 在135上执行命令yum install -y redis安装redis yum install -y redis 源码安装方法 wget http://download.redis.io/releases/redis-2.8.13.tar.gz tar zxf redis-2.8.13.tar.gz cd redis-2.8.13 make PREFIX/usr/loca…
阅读更多...
自闭症儿童寄宿学校：打造良好的学习和生活环境

自闭症儿童寄宿学校：打造良好的学习和生活环境

在探讨自闭症儿童的教育与康复之路时&#xff0c;星贝育园无疑是一个值得深入了解的典范。这所全国知名的广泛性发育障碍全托寄宿制儿童康复训练机构&#xff0c;不仅以其独特的CBM干预法引领着行业前沿&#xff0c;更以其对每一个孩子的深切关怀与承诺&#xff0c;构建了一个充…
阅读更多...
记HttpURLConnection下载图片

记HttpURLConnection下载图片

目录 一、示例代码1 二、示例代码2 一、示例代码1 import java.io.*; import java.net.HttpURLConnection; import java.net.URL;public class Test {/*** 下载图片*/public void getNetImg() {InputStream inStream null;FileOutputStream fOutStream null;try {// URL 统…
阅读更多...
各省-城镇化率（2001-2022年）

各省-城镇化率（2001-2022年）

数据收集各省-城镇化率&#xff08;2001-2022年&#xff09;.zip资源-CSDN文库https://download.csdn.net/download/2401_84585615/89465885 相关指标&#xff1a; 包括省份、年份、年末总人口数(万人)、年末城镇人口数(万人)、城镇化率等。 数据集构建&#xff1a; 数据集通…
阅读更多...
车辆重识别（2020NIPS去噪扩散概率模型）论文阅读2024/9/27

车辆重识别（2020NIPS去噪扩散概率模型）论文阅读2024/9/27

[2] Denoising Diffusion Probabilistic Models 作者&#xff1a;Jonathan Ho Ajay Jain Pieter Abbeel 单位&#xff1a;加州大学伯克利分校 摘要&#xff1a; 我们提出了高质量的图像合成结果使用扩散概率模型&#xff0c;一类潜变量模型从非平衡热力学的考虑启发。我们的最…
阅读更多...
STM32精确控制步进电机

STM32精确控制步进电机

目的&#xff1a;学习使用STM32电机驱动器步进电机&#xff0c;进行电机运动精确控制。 测试环境&#xff1a; MCU主控芯片STM32F103RCT6 &#xff1b;A4988步进电机驱动器模块&#xff1b; 微型2相4线步…
阅读更多...
开发微信小程序 基础03

开发微信小程序 基础03

WXSS(类似CSS) 定义&#xff1a; WXSS (WeiXin Style Sheets)是一套样式语言&#xff0c;用于描述 WXML的组件样式&#xff0c;类似于网页开发中的 CSS。 分类&#xff1a; 全局样式&#xff1a;定义在 app.wxss 中的样式为全局样式&#xff0c;作用于每一个页面 局部样式&…
阅读更多...
最新文章

Copyright @ 2022~2023