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

数据结构与算法基础-学习-09-线性表之栈的理解、初始化顺序栈、判断顺序栈空、获取顺序栈长度的实现

一、个人理解

栈是线性表的一种衍生,和之前的顺序表和链表在插入和删除元素上有较大差异,其他基本相同,栈是数据只能插入表的尾部(栈顶),删除数据时只能删除表的尾部(栈顶)数据,就是大家经常背的顺口溜:后入先出。后插入的数据先删除。

二、图解

这里把数组竖起来了,是方便理解,看得更清楚。

三、名词解释

1、出栈、弹栈

是一个意思,就是把数据从栈顶移除。

2、入栈、压栈

是一个意思,就是把数据从栈顶插入。

3、LIFO

LAST IN FIRST OUT的简写,也就是后进先出的意思。

4、顺序栈和链栈

实现方式上的不同,顺序栈是用数组实现,而链栈是用链表实现。

5、上溢

栈已满,但数据还需要继续入栈。上溢一般认为是一种错误,因为可能导致数据录入失败,或者导致数据录入延时。当是顺序栈时,对此情况有两种措施:

一是抛出错误。

二是重新申请新栈,把旧栈数据写入到新栈中,不推荐,比较耗时。

6、下溢

栈已空,但还是要出栈。下溢一般认为是一种结束标志,因为并不会有数据上的缺失。

四、函数实现

1、InitSqStack

(1)用途

初始化顺序栈。

(2)源码

Status InitSqStack(SqStack* S)
{printf("Init SqStack  : ");JudgeAllNullPointer(S);S->BasePointer    = (SqElemType*)MyMalloc(sizeof(SqElemType) * SQ_STACK_MAX_SIZE);S->TopPointer     = S->BasePointer;S->SqStackMaxSize = SQ_STACK_MAX_SIZE;printf("OK\n");PrintPretty();return SuccessFlag;   
}

(3)参数

参数名

说明

S

需要初始化的SqStack*类型顺序栈。

2、JudgeSqStackIsEmpty

(1)用途

判断顺序栈是否为空。

当栈顶指针和栈底指针相等时,表示栈为空,反之非空。

(2)源码

Status JudgeSqStackIsEmpty(SqStack* S)
{printf("Judge SqStack : ");JudgeAllNullPointer(S);if(S->BasePointer == S->TopPointer){printf("Empty\n");PrintPretty();return SuccessFlag;}printf("Not Empty\n");PrintPretty();return FailFlag;
}

(3)参数

参数名

说明

S

需要判断是否为空的SqStack*类型顺序栈。

3、GetSqStackLen

(1)用途

求顺序栈的长度。

栈顶指针减去栈底指针为顺序栈的长度,原理为相同类型的指针相减得到字节数,它会再除以一个栈类型(头文件中的结构体SqElemType)的字节长度,得到最终的顺序栈的长度。

(2)源码

SqStackMaxSizeType GetSqStackLen(SqStack* S)
{JudgeAllNullPointer(S);return S->TopPointer - S->BasePointer;
}

(3)参数

参数名

说明

S

需要求栈长度的SqStack*类型顺序栈。

五、测试代码

1、SqStack.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>
#include "SqStack.h"void PrintPretty()
{printf("*********************************\n");
}void PrintPretty_V1()
{printf("################\n");
}void *MyMalloc(size_t size)
{void *Result = (void *)malloc(size);if(Result == NULL){printf("malloc Function Exec Fail , Out Of Memory ,Exit!!!\n");exit(ExceptionExitFlag);}return Result;
}void JudgeAllNullPointer(void* P)
{if(!P){printf("Pointer Is Null ,Exit !\n");exit(ExceptionExitFlag);}
}Status InitSqStack(SqStack* S)
{printf("Init SqStack  : ");JudgeAllNullPointer(S);S->BasePointer    = (SqElemType*)MyMalloc(sizeof(SqElemType) * SQ_STACK_MAX_SIZE);S->TopPointer     = S->BasePointer;S->SqStackMaxSize = SQ_STACK_MAX_SIZE;printf("OK\n");PrintPretty();return SuccessFlag;   
}Status JudgeSqStackIsEmpty(SqStack* S)
{printf("Judge SqStack : ");JudgeAllNullPointer(S);if(S->BasePointer == S->TopPointer){printf("Empty\n");PrintPretty();return SuccessFlag;}printf("Not Empty\n");PrintPretty();return FailFlag;
}SqStackMaxSizeType GetSqStackLen(SqStack* S)
{JudgeAllNullPointer(S);return S->TopPointer - S->BasePointer;
}

2、SqStack.h

#ifndef SqStack_H
#define SqStack_H#define InsertDataArrayLen 8
#define SQ_STACK_MAX_SIZE  6#define ExceptionExitFlag -1
#define SuccessFlag        1
#define FailFlag           0
#define StudentNumLen      8
#define StudentNameLen     8typedef int Status;
typedef long long int SqStackMaxSizeType;typedef struct SqElemType
{char StudentNum[StudentNumLen];char StudentName[StudentNameLen];int  StudentScore;
}SqElemType;typedef struct 
{SqElemType*        BasePointer;SqElemType*        TopPointer;SqStackMaxSizeType SqStackMaxSize;
}SqStack;void *MyMalloc(size_t size);
void JudgeAllNullPointer(void* P);
void PrintPretty();
void PrintPretty_V1();Status InitSqStack(SqStack* S);
Status JudgeSqStackIsEmpty(SqStack* S);
SqStackMaxSizeType GetSqStackLen(SqStack* S);#endif

3、main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "SqStack.h"int main()
{//测试数据生成SqElemType *InsertSqElemArray = (SqElemType *)MyMalloc(sizeof(SqElemType) * InsertDataArrayLen);int i;for(i=0; i<InsertDataArrayLen; i++){strcpy(InsertSqElemArray[i].StudentNum ,"X666");strcpy(InsertSqElemArray[i].StudentName,"Sun");InsertSqElemArray[i].StudentScore = i + 100;}//测试顺序栈SqStack* S = (SqStack*)MyMalloc(sizeof(SqStack));InitSqStack(S);JudgeSqStackIsEmpty(S);printf("SqStack Len   : %lld\n",GetSqStackLen(S));PrintPretty();//释放内存free(InsertSqElemArray);InsertSqElemArray = NULL;return SuccessFlag;
}

4、makefile

CC = gcc
CFLAG_EXEC = -Wall -O3
CFLAG_ALIAS = -o
RM_COMM = rm -rfall : mainmain : $(CC) $(CFLAG_EXEC) SqStack.c main.c $(CFLAG_ALIAS) TestSqStackclean : $(RM_COMM) TestSqStack

六、测试结果

[gbase@czg2 LinearTable_Stack]$ make clean
rm -rf TestSqStack[gbase@czg2 LinearTable_Stack]$ make
gcc -Wall -O3 SqStack.c main.c -o TestSqStack[gbase@czg2 LinearTable_Stack]$ ./TestSqStack 
Init SqStack  : OK
*********************************
Judge SqStack : Empty
*********************************
SqStack Len   : 0
*********************************

七、顺序栈的应用

大家可以参考一下之前写的文章《leecode-C语言实现-20. 有效的括号》,里面用到了顺序栈的知识。

相关文章:

数据结构与算法基础-学习-09-线性表之栈的理解、初始化顺序栈、判断顺序栈空、获取顺序栈长度的实现

一、个人理解栈是线性表的一种衍生&#xff0c;和之前的顺序表和链表在插入和删除元素上有较大差异&#xff0c;其他基本相同&#xff0c;栈是数据只能插入表的尾部&#xff08;栈顶&#xff09;&#xff0c;删除数据时只能删除表的尾部&#xff08;栈顶&#xff09;数据&#…...

深入Kafka核心设计与实践原理读书笔记第二章

1 生产者 生产逻辑 配置生产者客户端参数及创建相应的生产者实例。构建待发送的消息。发送消息关闭实列 参数说明 bootstrap.servers &#xff1a;用来指定生产者客户端链接Kafka集群搜需要的broker地址清单&#xff0c;具体格式 host1:port1,host2:port2,可以设置一个或多…...

知乎kol投放怎么做?知乎kol资源从哪里找?

每个领域都有一些比较专业且具有话语权的大V博主&#xff0c;他们推荐某个产品或是品牌就能对粉丝产生很深的影响力&#xff0c;影响用户消费决策。 互联网时代&#xff0c;每个热门的内容平台上都活跃着一大批kol博主&#xff0c;做kol投放具有很高的商业价值。 知乎内容社区…...

python设计模式-享元设计模式,抽象工厂设计模式,面向对象设计模式

享元设计模式 享元(flyweight)设计模式属于结构设计模式类别。 它提供了一种减少对象数的方法。 它包含各种有助于改进应用程序结构的功能。享元对象最重要的特性是不可变的。 这意味着一旦构建就不能修改它们。 该模式使用HashMap来存储引用对象 如何实现享元(flyweight)设计…...

10条终身受益的Salesforce职业发展建议!

Salesforce这个千亿美金巨兽&#xff0c;在全球范围内有42,000多名员工。作为一家发展迅速的科技公司&#xff0c;一直在招聘各种角色&#xff0c;包括销售、营销、工程师和管理人员等。 据IDC估计&#xff0c;从2016年到2020年&#xff0c;该生态系统创造了190万个工作岗位。…...

电子科技大学人工智能期末复习笔记(四):概率与贝叶斯网络

目录 前言 概率 概率公式 贝叶斯公式 链式条件概率 例题 1. 求联合概率分布/边缘概率分布/条件概率分布 2. 灵活运用贝叶斯公式 概率总结 贝叶斯网络 判断独立性 两个事件独立的判断 条件独立性的判断 假设条件独立的链式法则 ⚠Active / Inactive Paths 判断独…...

码上掘金实现电子木鱼

前言 前几天在朋友圈看到“敲电子木鱼”的视频&#xff0c;敲一下木鱼就提示“功德 1”&#xff0c;还带有敲击声和念经的声音&#xff0c;感觉挺有意思的。 心血来潮&#xff0c;捣鼓了一晚上&#xff0c;借助码上掘金实现了这个功能。 展示效果 素材 准备素材如下&#…...

深度学习_L2正则化

文章目录参考博客正则化介绍正则化的实现参考博客 深入理解L1、L2正则化 PyTorch 实现L2正则化以及Dropout的操作 正则化介绍 正则化&#xff08;Regularization&#xff09;是机器学习中一种常用的技术&#xff0c;其主要目的是控制模型复杂度&#xff0c;减小过拟合。最基…...

第一章 认识Python

本章目录 一、初识Python 二、Python环境安装 三、Python代码的执行 四、Python集成开发环境 五、Python2.x与Python3.x的区别 六、本章小结 Python代码的编辑和运行方式主要分为两种&#xff1a;交互模式和脚本模式。 在交互模式下&#xff0c; 用户输入Python代码并按…...

复习0206

目录 一、访问修饰符 一、权限范围 二、注意事项 二、封装&#xff08;面向对象的三大特征之一&#xff09; 一、封装的好处 二、封装的实现步骤 三、和构造器结合 四、练习题中的细节 一、访问修饰符 一、权限范围 访问修饰符用于控制方法和属性&#xff08;成员变量…...

小红书如何查看笔记

小红书如何查看笔记 在小红书上找关键词的 6 大方法进阶版想要查找品类词、行业词、产品词、长尾词的小伙伴看过来&#xff0c;这一次我们就来给大家升级了 6 种找关键词的方法&#xff0c;也是我们的进阶版。 第一种&#xff0c;下拉框查找。我们只需要在小红书 AP 输入主要的…...

linux001之linux系统部署安装

注意&#xff1a;本次安装讲解以乌班图(Ubuntu) 虚拟机来说明讲解&#xff0c;既然学习linux&#xff0c;就无需用图形界面了&#xff0c;直接用服务器版本 1. 下载乌班图 网址&#xff1a;https://www.ubuntu.org.cn/download/server 然后就可以看到右下角有下载提示&#xff…...

服务异步通信 RabbitMQ-高级篇

服务异步通信RabbitMQ-高级篇服务异步通信RabbitMQ-高级篇1.消息可靠性1.1.生产者消息确认1.1.1.修改配置1.1.2.定义Return回调1.1.3.定义ConfirmCallback1.2.消息持久化1.2.1.交换机持久化1.2.2.队列持久化1.2.3.消息持久化1.3.消费者消息确认1.3.1.演示none模式1.3.2.演示aut…...

【PR】零基础快速入门教程

【PR】零基础快速入门教程PR&#xff08;Premiere&#xff09;能做什么&#xff1f;PR欢迎界面及新建项目工作区及窗口说明导入文件建立序列视频剪辑添加字幕导出视频使用软件&#xff1a;Premiere2020新年卷起来&#xff0c;写文章已近不能满足与我了&#xff0c;我要向着更前…...

Matlab 点云迭代加权最小二乘法拟合平面(抑制噪声)

不要虚掷你的黄金时代,不要去倾听枯燥乏味的东西,不要设法挽留无望的失败,不要把你的生命献给无知、平庸和低俗。这些都是我们时代病态的目标,虚假的理想。 ----王尔德 文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 受到之前博客的启发(Matlab 点云最小二乘…...

2023 软件测试行业内卷动荡,红利期过去后,何去何从?

前段时间席卷全互联网行业的内卷现象&#xff0c;想必有不少人都深陷其中。其实刚开始测试行业人才往往供不应求&#xff0c;而在发展了十几年后&#xff0c;很多人涌入这个行业开始面对存量竞争。红利期过去了&#xff0c;只剩内部争夺。 即便如此&#xff0c;测试行业仍有许…...

【王道数据结构】第六章(下) | 图的应用

目录 一、最小生成树 二、最短路径 三、有向⽆环图描述表达式 四、拓扑排序 五、关键路径 一、最小生成树 1、最小生成树的概念 对于一个带权连通无向图G &#xff08;V,E)&#xff0c;生成树不&#xff0c;每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所…...

Leetcode:518. 零钱兑换 II(C++)

目录 518. 零钱兑换 II 问题描述&#xff1a; 实现代码与解析&#xff1a; 动态规划&#xff08;完全背包&#xff09;&#xff1a; 原理思路&#xff1a; 377. 组合总和 Ⅳ 问题描述&#xff1a; 实现代码与解析&#xff1a; 动态规划&#xff08;完全背包&#xff0…...

Java中类是什么

类(class)是构造对象的模板或蓝图。 我们可以将类想象成制作小甜饼的模具&#xff0c;将对象想象为小甜饼。由类构造(construct)对象的过程称为创建类的实例(instance)。 正如前面所看到的&#xff0c;用Java 编写的所有代码都位于某个类里面。 标准 Java 库提供了几千个类&a…...

C进阶:预处理

&#x1f916;本篇文章主要讲解预处理的知识&#xff0c;即使你是小白也可以看的懂&#xff0c;若你对预处理有所不解&#xff0c;确定不来看看吗&#xff1f;&#x1f63f; 目录 一.代码运行是的两种环境 二.翻译环境 三.预定义符号 四.#define 1.define 定义宏 2.带有…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...