数据结构(顺序栈——c语言实现)

栈的基本概念:

       栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许进行操作的一端称为“栈顶”,另一固定端称为“栈底”,当栈中没有元素时称为“空栈”

       特点:先进后出(FILO)或后进先出(LIFO)

栈的优点

  1. 方便快捷:栈的操作非常明确,主要包括Push(压栈)和Pop(弹栈)两个操作,非常方便快捷。

  2. 逻辑清晰:栈的特性使得程序的逻辑非常清晰,因为它保证了操作的顺序和依赖关系。例如,在函数调用中,每进入一个函数,都会将临时变量作为栈帧入栈;当被调用函数执行完成返回后,将这个函数对应的栈帧出栈。这种顺序关系使得程序更易于理解和维护。

  3. 节省空间:栈是一种线性的数据结构,通常只需要在内存中分配一块连续的空间来存储元素,因此可以节省空间。此外,栈的插入和删除操作(即压栈和弹栈)通常只涉及栈顶元素,因此这些操作的时间复杂度较低,通常为O(1)。

  4. 支持递归:栈的特性使得它可以支持递归调用,这是一种非常便利的编程方式。递归调用本身就是一个不断压栈和弹栈的过程,栈能够很好地记录每一层递归的状态,从而确保递归调用的正确性和安全性。

栈的应用场景

  1. 函数调用:操作系统会给每个线程分配一块内存空间,这块内存被组织成栈结构。每进入一个函数,都会将临时变量作为栈帧入栈;当被调用函数执行完成返回后,将这个函数对应的栈帧出栈。这样,就可以保证函数调用的正确性和安全性。

  2. 表达式求值:编译器通过两个栈来实现表达式的求值。一个栈用来保存操作数,另一个栈用来保存运算符。从左到右遍历表达式,当遇到数字时,将其压入操作数栈;当遇到运算符时,将其与运算符栈栈顶元素进行比较,并根据优先级决定是压入栈还是进行运算。

  3. 括号匹配:在编写代码或处理文本时,经常需要检查括号是否匹配。可以使用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号进行匹配。这种方法可以高效地检查括号是否匹配。

  4. 浏览器的前进和后退功能:浏览器的前进和后退功能也可以看作是一个栈的应用。当用户浏览网页时,可以将每个网页的URL压入栈中;当用户点击后退按钮时,可以从栈中取出上一个网页的URL并跳转过去。同样地,当用户点击前进按钮时,可以从另一个栈(记录前进历史的栈)中取出下一个网页的URL并跳转过去。

 顺序栈:

       顺序栈是指采用地址连续的存储空间(如数组)来依次存储栈中的数据元素。在顺序栈中,栈底位置是固定不变的,通常设置在数组空间的起始处,而栈顶位置则随着入栈和出栈操作的进行而发生变化。因此,需要用一个整型变量(通常称为“栈顶指针”或“top”)来记录当前栈顶元素在数组中的位置。

#ifndef _SEQSTACK_H
#define _SEQSTACK_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//表尾为栈顶,表头为栈底
typedef int Type;
typedef struct{//Type data[size];Type *data;    //栈存储空间的首地址size_t size;      //保存栈空间的长度,无符号的长整形int top;       //栈顶元素的下标
}stack;            //顺序栈//创建栈
stack *create_stack(size_t size);
//判满
int full_stack(stack *s);
//判空 空为0非空为1
int empty_stack(stack *s);
//压栈
void push_stack(stack *s,Type data);
//弹栈
Type pop_stack(stack *s);
//获取栈顶元素
Type get_stack(stack *s);
//初始化
void init_stack(stack *s);
//回收
void free_stack(stack **s);#endif

       对于顺序栈,我这次采用跟之前不同的方法去创建,之前都是在一开始就规定了大小,但是这一次我们在功能函数中创建的时候再去定它的大小,所以在定义结构体的时候里面就有三个成员,一个为Type *类型的指针,用来接收数组的首地址,第二个用来保存栈空间的长度,第三个成员是用来保存栈顶元素下标的一个变量。

#include "seqstack.h"//创建栈
stack *create_stack(size_t size)
{stack *s = (stack *)malloc(sizeof(stack));if(NULL == s){perror("create stack malloc");return NULL;}s->size = size;s->top = -1;s->data = (Type *)malloc(sizeof(Type)*size);if(NULL == s->data){perror("create array  malloc");free(s);return NULL;}return s;
}
//判满 满为0,不满为1
int full_stack(stack *s)
{if(NULL == s){puts("stack is NULL");return -1;}return s->top == s->size-1?0:1;
}
//判空 空为0非空为1
int empty_stack(stack *s)
{if(NULL == s){puts("stack is NULL");return -1;}return s->top == -1?0:1; 
}
//压栈
void push_stack(stack *s,Type data)
{if(!full_stack(s)){puts("栈已满");return;}elses->data[++s->top] = data;
}
//弹栈
Type pop_stack(stack *s)
{if(0 == empty_stack(s)){puts("栈为空,无法操作");}elsereturn s->data[s->top--];
}
//获取栈顶元素
Type get_stack(stack *s)
{if(NULL == s){puts("stack is NULL");}if(0 == empty_stack(s)){puts("空栈,无法获取栈顶元素");}elsereturn s->data[s->top];
}
//初始化
void init_stack(stack *s)
{if(NULL == s){puts("stack is NULL");return;}s->top = -1;
}
//回收
void free_stack(stack **s)
{if(NULL == *s){puts("stack is NULL");return;}free((*s)->data);free(*s);*s = NULL;
}

创建:stack *create_stack(size_t size)

       在这里创建函数跟之前的有所区别,这里的创建我们需要传参,传入所需要创建顺序栈空间的大小;首先创建这个结构体,然后给结构体里的size赋值;因为一开始栈为空栈,没有元素,所以栈顶元素的下标为-1,然后就是顺序栈的空间大小,这个也需要我们开辟,将开辟的空间的首地址赋值给结构体里面的data,之后就通过操作结构体里的data来操作栈;因为这里开辟了两次空间,所以要进行两次判断,来判断开辟空间是否成功。

判满:int full_stack(stack *s)

       顺序栈的判满其实就是看栈顶元素的下标是否与栈长度减去一相等,如果相等证明放满,不等则没有放满;满返回0,不满返回1。

判空:int empty_stack(stack *s)

       判空和判满类似,判空就是看栈顶元素下标top与-1是否相等,如果相等证明栈为空,不相等则栈非空,空返回0,非空返回1。

压栈:void push_stack(stack *s,Type data)

        因为顺序栈是有大小的,所以在压栈之前我们需要判断栈是否放满,如果放满就不能再进行压栈操作,直接return结束即可;如果没有放满那就可以进行压栈,压栈先让栈顶元素下标top++,然后再赋值;顺序栈压栈操作其实就相当于数组的赋值,每次赋值都先让top往后移再赋值,这样top保存的就是最后一个元素的下标。

弹栈:Type pop_stack(stack *s)

       弹栈首先需要判断栈是否为空,如果是空的就无法进行弹栈操作;因为是顺序栈,因此弹栈操作也只需要将弹出的元素作为函数返回值,然后栈顶元素下标往前移动一位即可,下次压栈到这个位置会将原来的值覆盖,因此并不会对压栈造成影响。

获取栈顶元素:Type get_stack(stack *s)

       获取栈顶元素就是直接将top下标对应的元素当做函数返回值返回即可,当然在获取栈顶元素之前需要判断栈是否为空,如果为空就无法获取栈顶元素,就打印一个提示,告诉用户空栈无法获取栈顶元素。

初始化:void init_stack(stack *s)

       顺序栈的初始化和之前顺序表的初始化是一样的,在顺序栈这里只需让栈顶元素的下标top为-1即可,这样在下次压栈的时候就算里面有值也会被覆盖,所以不会对后续操作产生影响。

回收:void free_stack(stack **s)

       回收需要注意的点就是我们在创建的时候不仅创建了结构体,还给顺序栈开辟了空间,因此在回收的时候需要先将存放元素的空间释放,然后再释放存放结构体的空间;当然传参需要传二级指针,我们需要得到的是指针的地址,将存放元素的空间和存放结构体的空间都释放之后再让指针指向NULL就完成了回收。

测试(主函数)

#include "seqstack.h"
int main(int agrc,char *agrv[])
{stack *s = create_stack(5);puts("压栈,将1,2,3,依次压入栈中");push_stack(s,1);push_stack(s,2);push_stack(s,3);puts("弹栈,将栈顶元素弹出");printf("%d\n",pop_stack(s));puts("获取栈顶元素");printf("%d\n",get_stack(s));puts("回收");free_stack(&s);printf("s=%p\n",s);return 0;
}

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

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

相关文章

【智谱清言-注册_登录安全分析报告】

前言 由于网站注册入口容易被机器执行自动化程序攻击&#xff0c;存在如下风险&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露&#xff0c;不符合国家等级保护的要求。短信盗刷带来的拒绝服务风险 &#xff0c;造成用户无法登陆、注册&#xff0c;大量收到垃圾短信的…

[Realtek sdk-3.4.14b] RTL8197FH-VG新增jffs2分区操作说明

sdk说明 ** Gateway/AP firmware v3.4.14b – Aug 26, 2019**  Wireless LAN driver changes as:  Refine WiFi Stability and Performance  Add 8812F MU-MIMO  Add 97G/8812F multiple mac-clone  Add 97G 2T3R antenna diversity  Fix 97G/8812F/8814B MP issu…

Cesium 加载B3DM模型

一、引入Cesium&#xff0c;可以使用该链接下载cesium 链接: https://pan.baidu.com/s/1BRQyaFCkxO2xQQT5RzFUCw?pwdkcv9 提取码: kcv9 在index.html文件中引入cesium <script type"text/javascript" src"/Cesium/Cesium.js"></script> …

掌握移动端性能测试利器:深入JMeter手机录制功能

引言 在当今移动互联网时代&#xff0c;应用程序的性能和用户体验至关重要。为了确保应用程序在不同设备和网络环境下都能稳定运行&#xff0c;性能测试成为了不可或缺的一环。Apache JMeter作为一款强大的开源性能测试工具&#xff0c;不仅支持传统的PC端性能测试&#xff0c…

友思特新闻 | 友思特荣获广州科技创新创业大赛智能装备行业赛初创组优胜企业!

2024年11月19日&#xff0c;第十三届中国创新创业大赛&#xff08;广东广州赛区&#xff09;暨2024年广州科技创新创业大赛智能装备行业赛颁奖典礼隆重举行。 赛事奖项介绍&#xff1a;广州科技创新创业大赛智能装备行业赛 第十三届“中国创新创业大赛&#xff08;广东广州赛区…

Docker3:docker基础1

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…

MySQL - 数据库基础 | 数据库操作 | 表操作

文章目录 1、数据库基础1.1为什么要有数据库1.2主流的数据库1.3连接MySQL1.4服务器、数据库、表的关系1.5 MySQL框架1.6 SQL分类1.7储存引擎 2.数据库操作2.1创建数据库2.2字符集和校验规则2.3删除数据库2.4修改数据库2.5备份与恢复2.6查看连接情况 3.表的操作3.1创建表3.2查看…

通过vite+vue3+pinia从0到1搭建一个uniapp应用

最近项目上要做一个app&#xff0c;选择了用uniapp作为开发框架&#xff1b;我大概看了一下uniapp的文档&#xff0c;根据文档从0到1搭了一个uniapp应用供大家参考。 因为本人习惯使用了WebStorm编译器&#xff0c;但是uniapp官方推荐使用HBuilder搭建&#xff0c;如果和我一样…

学习路之phpstudy--安装mysql5.7后在my.ini文件中无法修改sql_mode

windows环境下使用phpstudy安装mysql5.7后需要修改mysql中的sql_mode配置&#xff0c;但是在phpstudy中打开mysql配置文件my.ini后&#xff0c; 通过查找找不到sql_mode或sql-mode&#xff0c; 此时无法在my.ini文件中直接进行修改&#xff0c;可以使用mysql命令进行修改&#…

IDEA:2023版远程服务器debug

很简单&#xff0c;但是很多文档没有写清楚&#xff0c;wocao 一、首先新建一个远程jvm 二、配置 三、把上面的参数复制出来 -agentlib:jdwptransportdt_socket,servery,suspendn,address5005 四、然后把这串代码放到服务器中&#xff08;这里的0.0.0.0意思是所有IP都能访问&a…

ts: 定义一个对象接收后端返回对象数据,但是报错了有红色的红线为什么

问&#xff1a; const backendProgressData ref<object>&#xff08;{}&#xff09; 这是我的代码&#xff0c;但是当我进行使用的时候&#xff1a; backendProgressData.value xxxx接口返回数据progressData:{percentage:123,text:"文字"} 在template中{{…

解决Docker环境变量的配置的通用方法

我们部署的很多服务都是以Docker容器的形式存在的。 在运行Docker容器前&#xff0c;除了设置网络、数据卷之外&#xff0c;还需要设置各种各样的环境变量。 有时候&#xff0c;由于容器版本的问题&#xff0c;一些文档没有及时更新&#xff0c;可能同时存在多个新旧版本的环…

【腾讯云产品最佳实践】腾讯云CVM入门技术与实践:通过腾讯云快速构建云上应用

目录 前言 什么是腾讯云CVM&#xff1f; 腾讯云CVM的技术优势 基于最佳技术实践&#xff0c;使用腾讯云CVM搭建应用 1. 开通CVM实例 2. 连接CVM实例 3. 配置Web环境 4. 部署PHP应用 腾讯云CVM行业应用案例&#xff1a;电商平台的双十一攻略 1. 弹性伸缩解决高并发问题…

51c嵌入式~IO合集2

我自己的原文哦~ https://blog.51cto.com/whaosoft/11697814 一、STM32串口通信基本原理 通信接口背景知识 设备之间通信的方式 一般情况下&#xff0c;设备之间的通信方式可以分成并行通信和串行通信两种。并行与串行通信的区别如下表所示。 串行通信的分类 1、按照数据传…

七、电机三环控制

电机三环控制指的是&#xff0c;直流有刷电机三环&#xff08;电流环速度环位置环&#xff09;PID 控制。 1、三环PID控制原理 三环 PID 控制就是将三个 PID 控制系统&#xff08;例如&#xff1a;电流环、速度环以及位置环&#xff09;串联起来&#xff0c;然后对前一个系统…

NLP论文速读(多伦多大学)|利用人类偏好校准来调整机器翻译的元指标

论文速读|MetaMetrics-MT: Tuning Meta-Metrics for Machine Translation via Human Preference Calibration 论文信息&#xff1a; 简介&#xff1a; 本文的背景是机器翻译&#xff08;MT&#xff09;任务的评估。在机器翻译领域&#xff0c;由于不同场景和语言对的需求差异&a…

【Vue】Vue指令

目录 概念 作用 分类 内容渲染指令 属性绑定指令 事件绑定指令 条件渲染指令 v-if/v-else-if/v-else多分支渲染 v-show和v-if的区别 列表渲染指令 v-for中的key属性 双向绑定指令 示例&#xff1a;图片切换 示例&#xff1a;可折叠面板 示例&#xff1a;书架…

C++:类和对象(三)

1.深入了解构造函数 1.1初始化列表 引入&#xff1a;我们首先要知道&#xff0c;在类中我们是声明变量&#xff0c;在实例化的时候才是开空间&#xff0c;在调用构造函数的时候又分两段&#xff0c;一段是定义&#xff08;所有的成员变量进行定义&#xff09;&#xff0c;一段…

北京申请中级职称流程(2024年)

想找个完整详细点的申请流程资料真不容易&#xff0c;做个分享送给需要的人吧。 不清楚为什么说文章过度宣传&#xff0c;把链接和页面去掉了&#xff0c;网上自己找一下。 最好用windows自带的EDGE浏览器打开申请网站&#xff0c;只有在开始申请的时间内才可以进行网上申报&…

好用的js组件库

lodash https://www.lodashjs.com/https://www.lodashjs.com/ uuid 用于生成随机数&#xff0c;常用于生成id标识 GitHub - uuidjs/uuid: Generate RFC-compliant UUIDs in JavaScripthttps://github.com/uuidjs/uuid dayjs 常用于时间的处理 安装 | Day.js中文网 (fenxi…