【数据结构】C语言实现共享栈

共享栈的C语言实现

  • 导言
  • 一、共享栈
    • 1.1 共享栈的初始化
    • 1.2 共享栈的判空
    • 1.3 共享栈的入栈
      • 1.3.1 空指针
      • 1.3.2 满栈
      • 1.3.3 入栈空间错误
      • 1.3.4 正常入栈
      • 1.3.5 小结
    • 1.4 共享栈的查找
    • 1.5 共享栈的出栈
    • 1.6 共享栈的销毁
  • 二、共享栈的实现演示
  • 结语

封面

导言

大家好,很高兴又和大家见面啦!!!
在上一篇内容中,我们介绍了如何通过C语言实现顺序栈,并且在介绍顺序栈的进栈操作时有提到过我们可以通过选择数组的首元素或者尾元素作为栈底,来进行栈的创建,以及栈的另一种形式——链栈。

根据前面的介绍,我们知道了顺序栈是通过静态数组进行实现的,既然是静态数组,那么它对应的空间大小就是不可被改变的。由于顺序栈的空间限制,当我们入栈的元素个数超过顺序栈的空间大小时,就会造成栈溢出的问题,我们为了避免出现栈溢出的情况,我们可以通过两种方式来进行栈的创建:

  1. 可以选择在申请空间时申请一个足够大的空间;
  2. 可以创建一个动态的链栈;

在今天的内容中我们将来详细介绍一下应该如何通过C语言来实现共享栈;

一、共享栈

为了解决栈溢出的问题,当我们选择通过申请一个足够大的空间时,势必就会造成内容空间的浪费,为了合理的解决这个问题,我们则可以根据栈在创建时的栈底选择不同,在同一个空间上创建两个栈,这个空间就被称为共享栈,如下图所示:
共享栈

从图中可以看到在共享栈中,一个栈的栈底选择的是数组的首元素,一个栈的栈底选择的是数组的尾元素,它们对应的下标一个是0,一个是MaxSize-1

1.1 共享栈的初始化

根据共享栈的结构,我们在初始化时,可以分别初始化为-1和MaxSize,也可以初始化为0和MaxSize-1,如下所示:

//共享栈的数据类型
#define MaxSize 10//定义空间存储的最大元素
typedef struct SqStack {int data[MaxSize];//存储数据的静态数组int top_a;//栈a的栈顶指针int top_b;//栈b的栈顶指针
}SqStack;
//初始化共享栈
void InitStack(SqStack* S) {assert(S);//通过断言来对指针进行判空S->top_a = -1;//将栈a的栈顶指针初始化为-1S->top_b = MaxSize;//将栈b的栈顶指针初始化为MaxSize
}

这里为了方便演示,我是定义的一个整型共享栈,站内能存储的是整型数据类型的数据元素。在初始化阶段,我这里是将其初始化为-1和MaxSize,当然也可以初始化为0和MaxSize-1,这里我就不演示了,大家可以自行下去尝试一下。

1.2 共享栈的判空

完成初始化后,我们要对其进行判空操作的话则是同时判断两个栈顶指针的值,如下所示:

//共享栈的判空
bool EmptyStack(SqStack S) {if (S.top_a == -1 && S.top_b == MaxSize)return true;return false;
}

在初始化阶段我们是通过assert来进行问题反馈,因此可以对函数的返回类型设置为void,在进行判空操作时,我们是通过函数的返回值来进行判断,所以这里通过分支语句来对不同的返回值做出对应的提示;

1.3 共享栈的入栈

当我要对共享栈进行入栈操作时,可以有多种实现方式:

  1. 对两个栈同时进行入栈操作;
  2. 对两个栈依次进行入栈操作;

这里我给大家演示一下对两个栈依次进行入栈操作应该如何实现,如下所示:

//共享栈的入栈操作
int Push(SqStack* S, int x, char flag) {if (!S)return 3;if(S->top_a + 1 == S->top_b)return 0;if (flag == 'a') {S->data[++S->top_a] = x;}else if (flag == 'b') {S->data[--S->top_b] = x;}elsereturn 2;return 1;
}

为了更加直观的收到函数的反馈,这里我们可以通过将函数的返回值以0,1,2,3这三个值来进行反馈,主函数中通过分支语句来判断返回值,以此给出不同的反馈,下面我们就来介绍一下这些返回值的作用;

1.3.1 空指针

在进行编码时,对于空指针的问题我们一定要注意,在入栈操作中,我们是要对共享栈进行修改,所以此时的传参为传址传参,正常情况下,我们都是会将栈的起始地址传过去,但是为了避免出现问题,我们则需要对指针进行判空,如果此时的指针为空指针时,那说明我们并没有将需要修改的栈传给函数,此时就可以通过返回值来提醒使用者,如下所示:
空指针
可以看到,当我们传入的指针为空指针时,此时函数就会返回3,在switc语句中,3并不属于0,1,2这三者中的任意一种情况,因此,语句会执行default语句,此时我们就可以根据对应的提示来进行代码的检测,并对问题进行修改;

1.3.2 满栈

相比于单个的顺序栈,共享栈在进行入栈前对满栈的判断则是两个栈顶元素相邻,如下所示:
共享栈满栈
从图中可以看到,当共享栈的两个栈顶元素相邻时,它们对应的栈顶指针也相邻,因此指针之间的差值为1,也就是说当两个栈顶指针相差1时,此时我们是无法继续进行入栈操作的,这时我们可以通过返回0值来告诉使用者此时已经满栈了,并通过返回值结束入栈操作;

1.3.3 入栈空间错误

为了能更加精准的将元素存入对应的栈空间内,这里我们是通过一个标志变量来执行,当标志为’a’时,说明我们此时要存入的是栈a,当标志为’b’时,说明我们此时要存入的是栈b,但是当标志为其它内容时,我们需要给用户提示,说明输入空间有误,如下所示:
入栈空间错误
从测试结果中我们可以看到,当我们输入’c’时,此时的标志既不是’a’也不是’b’,所以函数返回值为2,回到主函数后,会执行返回值为2的对应语句,这时程序会提示我们入栈空间输入错误,请重新输入,通过提示,我们就能知道应该如何正确输入了;

1.3.4 正常入栈

当我们传参正确、栈未满且空间都正确时,此时函数返回值为1,这样我们可以一直进行输入,知道满栈为止,如下所示:
正常入栈
从测试结果中我们可以看到,正常情况下栈是只能存储10个元素的,也就是当栈a入栈4个元素后,栈b只能入栈6个元素,这里当我们对栈b已经入栈了6个元素后,还想入栈第7个元素时,此时程序就会提示,已经满栈,并退出循环;

1.3.5 小结

对于共享栈的入栈操作我们就介绍完了,通过这里演示的代码我们可以看到,此时咱们算法是有很强的健壮性的,可以根据不同的问题给出不同的反馈。
当然,在实际操作中肯定不会像我这样去进行编写代码,我们需要根据具体的情况来对代码进行相应的调整,这里我们只要保证操作的逻辑没有发生改变就行。

1.4 共享栈的查找

对于共享栈而言,我们要查找栈顶指针的话也是需要指明查找的对象,因此,我们可以依然可以通过标志变量进行指定,如下所示:

//共享栈的栈顶查找
int GetTop(SqStack S, char flag,int* x) {assert(x);if (flag == 'a') {if (S.top_a != -1)*x = S.data[S.top_a];return S.top_a;}else if (flag == 'b') {if (S.top_b != MaxSize)*x = S.data[S.top_b];return S.top_b;}elsereturn MaxSize + 1;
}

由于查找栈顶后,我们还需要将栈顶元素带回到主函数中,因此存储数据的变量我们选择的是通过传址的方式进行传参,并通过指针接收,这里我们可以直接通过assert断言来对指针x进行判空操作;

相比于正常的顺序栈而言,共享栈在进行栈顶查找时,我们通过标志变量来判断查找的对象,并通过判断查找对象的栈顶指针的位置来决定是否将该位置存储的值带回;

对应的主函数中,我们则可以根据函数对应的返回值来给出对应的反馈,如下所示:

	printf("请输入要查询的栈空间<a/b>:>");scanf("%c", &flag);int top = GetTop(S, flag, &x);switch (top) {case -1:printf("栈%c为空栈\n", flag);break;case MaxSize:printf("栈%c为空栈\n", flag);break;case MaxSize + 1:printf("共享栈中没有栈%c\n", flag);break;default:printf("栈%c的栈顶为%d,栈顶元素为%d\n", flag, top, x);break;}

在共享栈中栈a的栈顶指针的取值范围是-1~MaxSize-1,栈b的栈顶指针的取值范围是MaxSize~0,因此返回值为-1与返回值为MaxSize以及返回值为MaxSize+1这三种情况都是唯一的,所以我们在switch语句中只需要将这三者单独罗列出来即可,对其它的情况我们只需要正常打印就行;

1.5 共享栈的出栈

共享栈的出栈操作与入栈操作同理,都是需要根据指定出栈对象来完成出栈操作,因此,我们在出栈操作中同样需要增设一个标志变量来制定出栈的对象,如下所示:

//共享栈的出栈
int Pop(SqStack* S, char flag, int* x) {assert(S && x);if (flag == 'a') {if (S->top_a != -1)*x = S->data[S->top_a--];return S->top_a;}else if (flag == 'b') {if (S->top_b != MaxSize)*x = S->data[S->top_b++];return S->top_b;}elsereturn MaxSize + 1;
}

这里我是通过仿照查找栈顶指针的操作编写的代码,根据函数的返回值,我们在主函数中就可以编写以下代码:

	printf("请输入需要出栈的栈空间<a/b>:>");scanf("%c", &flag);top = Pop(&S, flag, &x);switch (top) {case -1:printf("栈%c为空栈\n", flag);break;case MaxSize:printf("栈%c为空栈\n", flag);break;case MaxSize + 1:printf("共享栈中没有栈%c\n", flag);break;default:printf("栈%c的已完成栈顶元素%d的出栈,此时的栈顶为%d\n", flag, x, top);break;}

可以看到,此时我们只是对代码进行了一些小改动,反馈逻辑与栈顶指针的查找的反馈逻辑是一致的;

1.6 共享栈的销毁

共享栈的销毁我们则是通过在出栈的基础上加上一个循环,将所有的元素全部进行出栈即可,对应的代码如下所示:

	int des = 2;while (des) {printf("请输入需要出栈的栈空间<a/b>:>");scanf("%c", &flag);top = Pop(&S, flag, &x);switch (top) {case -1:printf("栈%c为空栈\n", flag);des--;break;case MaxSize:printf("栈%c为空栈\n", flag);des--;break;case MaxSize + 1:printf("共享栈中没有栈%c\n", flag);break;default:printf("栈%c的已完成栈顶元素%d的出栈,此时的栈顶为%d\n", flag, x, top);break;}getchar();}printf("共享栈S已完成销毁\n");

我这里的代码执行的销毁是手动进行元素的出栈,有兴趣的朋友也可以将其改为自动进行销毁操作。

从循环的判断条件我们可以看到,此时除非两个栈都为空栈时,循环才会停止否则就会一直运行;在完成所有的元素弹出后,栈的空间回收我们只需要等待程序运行结束后自动回收即可。

二、共享栈的实现演示

为了节约时间,这里我将最大的元素个数修改为4,下面我们在来看一下具体的操作演示:
共享栈操作演示
可以看到,此时我们已经成功实现了共享栈的所有操作,共享栈对应操作的代码如下所示,有需要的朋友自取:

//共享栈的数据类型
#define MaxSize 4//定义空间存储的最大元素
typedef struct SqStack {int data[MaxSize];//存储数据的静态数组int top_a;//栈a的栈顶指针int top_b;//栈b的栈顶指针
}SqStack;
//初始化共享栈
void InitStack(SqStack* S) {assert(S);//通过断言来对指针进行判空S->top_a = -1;//将栈a的栈顶指针初始化为-1S->top_b = MaxSize;//将栈b的栈顶指针初始化为MaxSize
}
//共享栈的判空
bool EmptyStack(SqStack S) {if (S.top_a == -1 && S.top_b == MaxSize)return true;return false;
}
//共享栈的入栈操作
int Push(SqStack* S, int x, char flag) {if (!S)return 3;if(S->top_a + 1 == S->top_b)return 0;if (flag == 'a') {S->data[++S->top_a] = x;}else if (flag == 'b') {S->data[--S->top_b] = x;}elsereturn 2;return 1;
}
//共享栈的栈顶查找
int GetTop(SqStack S, char flag,int* x) {assert(x);if (flag == 'a') {if (S.top_a != -1)*x = S.data[S.top_a];return S.top_a;}else if (flag == 'b') {if (S.top_b != MaxSize)*x = S.data[S.top_b];return S.top_b;}elsereturn MaxSize + 1;
}
//共享栈的出栈
int Pop(SqStack* S, char flag, int* x) {assert(S && x);if (flag == 'a') {if (S->top_a != -1)*x = S->data[S->top_a--];return S->top_a;}else if (flag == 'b') {if (S->top_b != MaxSize)*x = S->data[S->top_b++];return S->top_b;}elsereturn MaxSize + 1;
}
int main() {SqStack S;InitStack(&S);//初始化共享栈if (EmptyStack(S))printf("共享栈为空栈\n");elseprintf("共享栈内有存入元素\n");char flag = 0;int x = 0;int ret = 1;while (ret == 1 || ret == 2) {printf("请输入进行入栈的空间:>");scanf("%c", &flag);printf("请输入进行入栈的数据:>");scanf("%d", &x);ret = Push(&S, x, flag);switch (ret){case 0:printf("共享栈已满栈\n");break;case 1:break;case 2:printf("入栈的空间输入错误,请重新输入<a/b>\n");break;default:printf("指针S为空指针\n");break;}getchar();//读取输入缓冲区的\n避免对后面的输入造成干扰}printf("请输入要查询的栈空间<a/b>:>");scanf("%c", &flag);int top = GetTop(S, flag, &x);switch (top) {case -1:printf("栈%c为空栈\n", flag);break;case MaxSize:printf("栈%c为空栈\n", flag);break;case MaxSize + 1:printf("共享栈中没有栈%c\n", flag);break;default:printf("栈%c的栈顶为%d,栈顶元素为%d\n", flag, top, x);break;}getchar();int des = 2;while (des) {printf("请输入需要出栈的栈空间<a/b>:>");scanf("%c", &flag);top = Pop(&S, flag, &x);switch (top) {case -1:printf("栈%c为空栈\n", flag);des--;break;case MaxSize:printf("栈%c为空栈\n", flag);des--;break;case MaxSize + 1:printf("共享栈中没有栈%c\n", flag);break;default:printf("栈%c的已完成栈顶元素%d的出栈,此时的栈顶为%d\n", flag, x, top);break;}getchar();}printf("共享栈S已完成销毁\n");return 0;
}

结语

咱们今天的内容到这里就全部介绍完了,希望今天的内容能够帮助大家更好的理解共享栈以及对应的操作如何通过C语言来实现,在下一个篇章中,我将继续给大家介绍链栈的相关内容,大家记得关注哦!!!
最后感谢大家的翻阅,咱们下一篇再见!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238838.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

领域驱动设计——DDD领域驱动设计进阶

摘要 进阶篇主要讲解领域事件、DDD 分层架构、几种常见的微服务架构模型以及中台设计思想等内容。如何通过领域事件实现微服务解耦&#xff1f;、怎样进行微服务分层设计&#xff1f;、如何实现层与层之间的服务协作&#xff1f;、通过几种微服务架构模型的对比分析&#xff0…

基于Java (spring-boot)的社团管理系统

一、项目介绍 系统管理员的功能概述&#xff1a; ①用户管理 a.注册用户账户 当一个新用户注册时&#xff0c;用户填写基本信息并上传。用户基本信息包括账号、 姓名、密码、手机、地址等信息。 b.用户信息管理 管理员可以查看系统所有用户的基本信息&#xff0c;并修改和…

【征服redis2】redis的事务与lua

1.redis事务介绍 在前面我们介绍了redis的几种典型数据结构和应用&#xff0c;本文我们来看一下redis的事务问题。事务也是数据库的重要主题&#xff0c;熟悉关系型数据库的读者应该对事务比较了解&#xff0c;简单地说&#xff0c;事务表示一组动作&#xff0c;要么全部执行&…

基于Springboot的善筹网(众筹网-有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的善筹网(众筹网-有报告)。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring S…

2024年全网最全春招时间线

2024年全网最全春招时间线 春招&#xff0c;许多同学可能会误以为这是春天才会进行。 你可能会想&#xff0c;期末刚考完试&#xff0c;先享受下寒假&#xff0c;再欢度春节&#xff0c;收些红包&#xff0c;甚至还能抽空去理个发型。等到春日明媚时&#xff0c;再参加春招活…

【数据结构】归并排序的非递归写法和计数排序

前言 &#x1f493;作者简介&#xff1a; 加油&#xff0c;旭杏&#xff0c;目前大二&#xff0c;正在学习C&#xff0c;数据结构等&#x1f440; &#x1f493;作者主页&#xff1a;加油&#xff0c;旭杏的主页&#x1f440; ⏩本文收录在&#xff1a;再识C进阶的专栏&#x1…

表单验证 ---- 在Vue2中使用ElementUI进行表单验证

目录 前言 给表单绑定对应属性 在data中定义数据对象和表单的定义规则 与数据对象双向绑定 对整个表单进行验证 前言 在做项目时&#xff0c;对于表单进行验证是我们必不可少的 例如 搭建一个基本的登录界面 <div class"form"><h1>登录</h1>&…

电商物流查询:未来的发展方向

在电商日益繁荣的时代&#xff0c;物流信息查询不仅关乎消费者体验&#xff0c;更影响着电商运营的效率。快速、准确地追踪物流信息至关重要。本文将简述物流信息快速追踪的价值&#xff0c;并重点介绍固乔快递查询助手这一高效查询工具及其批量查询功能。 一、物流信息快速追踪…

一、docker的安装与踩坑

目录 一、安装docker&#xff08;centos7安装docker&#xff09;1.安装环境前期准备2.参考官网安装前准备3.参考官网安装步骤开始安装docker4.运行首个容器 二、安装一些软件的踩坑1.启动docker踩坑2.安装mysql踩坑3.罕见问题 三、关于我的虚拟机 一、安装docker&#xff08;ce…

鸿蒙开发(三)理解UIAbility

前文提到过&#xff0c;在使用DevEco创建鸿蒙项目的时候&#xff0c;会选择Empty Ability&#xff0c;那么这个Ability是什么呢&#xff1f;其实对比Android Studio创建Android羡慕时选择的Empty Activity&#xff0c;感觉Harmony的Ability更像是Android的Activity&#xff0c;…

持久双向通信网络协议-WebSocket-入门案例实现demo

1 介绍 WebSocket 是基于 TCP 的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c; 并进行双向数据传输。 HTTP协议和WebSocket协议对比&#xff1a; HTTP是短连接&#xff0…

利用人工智能和机器人技术实现复杂的自动化任务!

这篇mylangrobot项目由neka-nat创建&#xff0c;本文已获得作者Shirokuma授权进行编辑和转载。 https://twitter.com/neka_nat GitHub-mylangrobot &#xff1a;GitHub - neka-nat/mylangrobot: Language instructions to mycobot using GPT-4V 引言 本项目创建了一个使用GPT-4…

【K8S 云原生】Kurbernets集群的调度策略

目录 一、Kubernetes的list-watch机制 1、List-watch 2、创建pod的过程&#xff1a; 二、scheduler调度的过程和策略&#xff1a; 1、简介 2、预算策略&#xff1a;predicate 3、优先策略&#xff1a; 3.1、leastrequestedpriority&#xff1a; 3.2、balanceresourceal…

爬虫利器一览

前言 爬虫&#xff08;英文&#xff1a;spider&#xff09;&#xff0c;可以理解为简单的机器人&#xff0c;如此一个“不为名利而活&#xff0c;只为数据而生&#xff0c;目标单纯&#xff0c;能量充沛&#xff0c;不怕日晒雨淋&#xff0c;不惧寒冬酷暑”的家伙&#xff0c;…

含PEMFC的热电联供系统能量管理策略Simulink仿真

1.光伏发电系统 在直流微电网中&#xff0c;光伏电池系统经过升压DC/DC变换器接入直流微电网提供功率。在不同的系统运行条件下&#xff0c;光伏电池系统有三种工作模式&#xff1a;MPPT 模式、下垂模式和空闲模式。由于光伏阵列的输出特性随着环境条件影响&#xff0c;光伏电池…

【科技素养题】少儿编程 蓝桥杯青少组科技素养题真题及解析第22套

少儿编程 蓝桥杯青少组科技素养题真题及解析第22套 1、植物的叶子多为绿色,这主要是因为它们含有 A、绿色色素 B、叶绿素 C、花青素 D、细胞 答案:B 考点分析:主要考查小朋友们生物知识的储备;叶绿素是植物叶子中的一种色素,它可以吸收太阳光中的能量并转化为植物所…

数据库多表查询练习题

二、多表查询 1. 创建 student 和 score 表 CREATE TABLE student ( id INT ( 10 ) NOT NULL UNIQUE PRIMARY KEY , name VARCHAR ( 20 ) NOT NULL , sex VARCHAR ( 4 ) , birth YEAR , department VARCHAR ( 20 ) , address VARCHAR ( 50 ) ); 创建 s…

嵌入式软件工程师面试题——2025校招社招通用(十八)

说明&#xff1a; 面试群&#xff0c;群号&#xff1a; 228447240面试题来源于网络书籍&#xff0c;公司题目以及博主原创或修改&#xff08;题目大部分来源于各种公司&#xff09;&#xff1b;文中很多题目&#xff0c;或许大家直接编译器写完&#xff0c;1分钟就出结果了。但…

Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4)

Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图的圆切图&#xff0c;Kotlin&#xff08;4&#xff09; 这篇 Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图像圆图&#xff0c;Kotlin&am…

电阻表示方法和电路应用

电阻 电阻的表示方法 直标法 直标法是将电阻器的类别及主要技术参数的数值直接标注在电阻器表面上 通常用3位阿拉伯数字来标注片状电阻的阻值&#xff0c;其中第1位数代表阻值的第1位有效数&#xff1b;第2位数代表阻值的第二位有效数字&#xff1b;第3位数代表阻值倍率&…