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

🕗 发布于 2024-10-04 13:35 数据结构

前言

介绍

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

参考

该部分知识参考于《数据结构（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的最大容量为MAXSIZE
return 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) //如果栈顶和栈底指向同一个位置则证明栈为NULL
return OK;
else
return 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;
}
else
return 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的最大容量为MAXSIZE
return 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) //如果栈顶和栈底指向同一个位置则证明栈为NULL
return OK;
else
return 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;
}
else
return 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)
{
//在栈顶位置插入元素e
StackNode* p = new StackNode;
p->data = e;
p->next = S;  //将新结点插入栈顶
S = p;        //修改栈顶指针为p
return 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)
{
//在栈顶位置插入元素e
StackNode* p = new StackNode;
p->data = e;
p->next = S;  //将新结点插入栈顶
S = p;        //修改栈顶指针为p
return 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写为一种结构体类型，让我们在学习顺序表时写起来就有些困难，在前面学会之后看到这里就游刃有余了！

原文地址：https://blog.csdn.net/2301_80492355/article/details/142487429

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Github 2024-09-28Rust开源项目日报Top10
下一篇：9.30学习记录(补)

云RDS MySQL迁移至本地MySQL
云RDS MySQL迁移至本地MySQL
阅读更多2024-10-05
Gralloc图形缓冲的分配过程
Gralloc 图形缓冲是一段保存图形数据的内存，这是一段共享的内存，Fence机制释放也是大多数都是通过memcpXXX等c++函数完成，也就是把指针重新指向一个地址，在Android系统中，Gra
阅读更多2024-10-05
使用PyTorch实现自然语言处理：从基础到实践
本文详细介绍了如何使用PyTorch实现一个简单的自然语言处理任务——文本分类。从数据准备、模型构建到训练与评估，提供了完整的代码示例。希望通过本文，读者能够掌握使用PyTorch进行自然语言处理的基
阅读更多2024-10-05
计算机毕业设计Python+Spark知识图谱微博舆情预测微博推荐系统微博可视化微博数据分析微博大数据微博爬虫 Hadoop 大数据毕业设计
计算机毕业设计Python+Spark知识图谱微博舆情预测微博推荐系统微博可视化微博数据分析微博大数据微博爬虫 Hadoop 大数据毕业设计
阅读更多2024-10-05
Springboot结合RabbitMQ
配置文件，也可以使用@PostConstruct。
阅读更多2024-10-05
PyTorch 模型保存与加载的三种常用方式
训练一个神经网络可能需要数小时甚至数天的时间，你需要认知到一点：时间是非常宝贵的，目前3090云服务器租赁一天的价格为 37.92 元。如果你的代码没有保存模型的模块，那就先不要开始，因为不保存基本等
阅读更多2024-10-05
【优选算法】（第二十二篇）
如果我们使⽤荷兰国旗问题的思想，将数组划分为左中右三部分：左边是⽐基准元素⼩的数据，中间是与基准元素相同的数据，右边是⽐基准元素⼤的数据。right - 1 与 cur 位置的元素，并且让 right
阅读更多2024-10-05
深度学习常见术语介绍
深度学习常见术语介绍
阅读更多2024-10-05
TCP BIC 的拟合函数分析
但要记住本质，不管是 bic 还是 cubic，不应过分关注数学表达本身，它们只是处理上的技巧，数学是工具，本质上要达到的目标是，尽量快速逼近 Wmax，谨慎适当 probe 新带宽，数学上拟合的曲线
阅读更多2024-10-05
profile-spec-ref元素
元素允许 SBB 关联到特定的 Profile，进而获取与用户相关的配置信息。它定义了 SBB 如何访问用户的个性化设置。元素在 JAIN SLEE 中扮演着重要角色，它允许 SBB 动态访问用户配置
阅读更多2024-10-05