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

数据结构之“栈”(全方位认识)

                                      🌹个人主页🌹:喜欢草莓熊的bear

                                       🌹专栏🌹:数据结构


前言

栈是一种数据结构,具有" 后进先出 "的特点 或者也可见说是 ” 先进后出 “。大家一起加油吧冲冲冲!!

目录

前言

一、栈

1.1栈的概念和结构

1.2栈的实现

 1.2.1栈的结构体定义

1.2.2初始化和销毁

1.2.3入栈

1.2.4出栈

1.2.5获取栈顶元素

1.2.6获取栈中的有效个数

1.2.7判空

1.3 代码测试

1.4 头文件

总结


一、栈

1.1栈的概念和结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。 栈中的数据元素遵守后进先出 LIFO Last In First Out )的原则。

 这个栈的数据结构在我们生活中很像羽毛球桶

压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
出栈:栈的删除操作叫做出栈。 出数据也在栈顶
除了"  先进后出 "这个特点还有" 入数据和出数据都在栈顶 "
下面是我画的简易图帮助大家理解栈是一个怎么样的数据结构。

1.2栈的实现

栈的实现一般可以使用 数组或者链表实现 ,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

 我们这里实现的是动态栈的结构,因为静态栈实际中一般运用不到。

先给大家看一下栈的结构体定义和一些功能。

//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;typedef int STDataType;
//动态栈
typedef struct Stack
{STDataType* a;int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。int capacity;
}ST;//栈的实现是通过数组所以只需要传一级指针。//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);//获取栈数据
STDataType STTop(ST* pst);//栈的判空
bool STEmpty(ST* pst);//栈的数据个数
int STSize(ST* pst);

 1.2.1栈的结构体定义

因为我们这次实现的栈是基于数组实现的,我们就可以参考顺序表的结构体定义来改进。

 我们了解的栈的定义发现,栈顶元素一直有被提及。我们要定义栈顶,其次我们定义数组,但是为什么我们这边是用指针呢?其实这里数组等价于指针的,在学习指针的时候我们学习过 a[i] == *(p+i)所以我们就像理解指针那一样的思路就可以了。还有就是结构体里面定义指针动态内存管理、高效的内存管理、还方便栈的各种操作。这边提到了内存,也要定义一个数来计算是否满了。

 结构体定义如下:一个指针 STDataType *a、一个栈顶元素下标的下一个元素(这里的top和顺序表的size相似的都是指有效元素的下一个数据,当作顺序表的size来理解这样更容易想通。)、一个计入内存大小的 capacity。

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。int capacity;
}ST;

1.2.2初始化和销毁

初始化:最前面就还是需要判断指针是否为空,有指针所以我们要置为NULL,其他的都给赋值为0。如果我们把top定义成栈顶元素的下标,那么我们就要把top赋值为-1了。这样赋值就会显得很奇怪。

销毁:最前面就还是需要判断指针是否为空,我们申请了动态空间当然要释放,所以free必不可少,其他的都给赋值为0。

//栈的初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;
}
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity;
}

1.2.3入栈

数组没有满时:很简单就是把当前栈顶元素往后移动一位在赋值就可以了。

数组满时:我们就要重新申请空间了,什么时候是数组满了呢?就那下面这个图理解,top是5,刚好capacity也是5。这时就满了,所以就要扩容了。就和之前顺序表一样写就可以了。

void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int Newcapacity = pst->capacity == 0 ? 4 :pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, Newcapacity * sizeof(STDataType));if (tmp == NULL){perror("ralloc fail");return;}pst->a = tmp;pst->capacity = Newcapacity;}pst->a[pst->top++] = x;
}

1.2.4出栈

出栈就更简单了,把栈顶指针向前移动一位就可以了。但是除了判别为空指针,还要判别数组里面还有数据吗!assert(pst->top > 0);

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

1.2.5获取栈顶元素

这个功能实现也是非常简单,要牢记top是指向栈顶元素的下一个元素。所以我们要top-1。

//获取栈数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}

1.2.6获取栈中的有效个数

我们定义的top为0还有计数的作用,所以直接返回top就行了。

int STSize(ST* pst)
{assert(pst);return pst->top;
}

1.2.7判空

我们直接使用具有计数作用的top判断是否等于0就可以知道是否为空栈了。

//栈的判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

1.3 代码测试

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
int main()
{ST sa;STInit(&sa);STPush(&sa, 1);STPush(&sa, 3);STPush(&sa, 5);while (!STEmpty(&sa)){printf("%d ", STTop(&sa));STPop(&sa);}STDestory(&sa);
}

 实现了栈先进后出的特点。

1.4 头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//bool 类型的头文件
#include<assert.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。int capacity;
}ST;//栈的实现是通过数组所以只需要传一级指针。//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);//获取栈数据
STDataType STTop(ST* pst);//栈的判空
bool STEmpty(ST* pst);//栈的数据个数
int STSize(ST* pst);

总结

好了给大家介绍完了,”栈“。下回介绍队列!!

相关文章:

数据结构之“栈”(全方位认识)

&#x1f339;个人主页&#x1f339;&#xff1a;喜欢草莓熊的bear &#x1f339;专栏&#x1f339;&#xff1a;数据结构 前言 栈是一种数据结构&#xff0c;具有" 后进先出 "的特点 或者也可见说是 ” 先进后出 “。大家一起加油吧冲冲冲&#xff01;&#xff01; …...

vue项目打包部署后 浏览器自动清除缓存问题(解决方法)

vue打包部署后 浏览器缓存问题&#xff0c;导致控制台报错ChunkLoadError: Loading chunk failed的解决方案 一、报错如下&#xff1a; 每次build打包部署到服务器上时&#xff0c;偶尔会出现前端资源文件不能及时更新到最新&#xff0c;浏览器存在缓存问题&#xff0c;这时在…...

解决vscode配置C++编译带有中文名称报错问题

在新电脑上安装vscode运行带有中文路径和中文名称的C代码时遇到报错 根据别人的教程将laugh.json文件中"program": "${fileDirname}\\${fileBasenameNoExtension}.exe",改成了"program": "${fileDirname}\\output\\test.exe",&#x…...

A61 STM32_HAL库函数 之 TIM扩展驱动 -- C -- 所有函数的介绍及使用

A61 STM32_HAL库函数 之 TIM扩展驱动 -- C -- 所有函数的介绍及使用 1 该驱动函数预览1.24 HAL_TIMEx_OnePulseN_Stop1.25 HAL_TIMEx_OnePulseN_Start_IT1.26 HAL_TIMEx_OnePulseN_Stop_IT1.27 HAL_TIMEx_ConfigCommutationEvent1.28 HAL_TIMEx_ConfigCommutationEvent_IT1.29 …...

使用瀚高数据库开发管理工具进行数据的备份与恢复---国产瀚高数据库工作笔记008

使用瀚高数据库,备份 恢复数据 然后找到对应的目录 其实就是hgdbdeveloper,瀚高的数据库开发管理工具 对应的包中有个dbclient 这个目录,选中这个目录以后,就可以了,然后 在对应的数据库,比如 data_middle 中,选中 某个模式,比如bigdata_huiju 然后右键进行,点击 恢复,然…...

css 选择器汇总

目录 所有选择器伪类选择器 所有选择器 选择器用法id选择器#myid类选择器.myclassname标签选择器div,h1,p相邻选择器h1p子选择器ul > li后代选择器li a通配符选择器*属性选择器a[rel“external”]伪类选择器a:hover, li:nth-child 伪类选择器 在CSS3中新增了一个结构伪类选…...

My Greedy Algorithm(贪心算法)之路(一)

引子&#xff1a;我们之前&#xff0c;其实也遇到过贪心算法&#xff0c;0,1背包就是一个典型的贪心算法问题&#xff0c;那今天我就来开始my-Greedy Algorithm的道路。 什么是贪心算法&#xff1f; 我愿称贪心算法为贪婪鼠目寸光&#xff0c;贪心算法&#xff08;Greedy Alg…...

Win11 Python3.10 安装pytorch3d

0&#xff0c;背景 Python3.10、cuda 11.7、pytorch 2.0.1 阅读【深度学习】【三维重建】windows10环境配置PyTorch3d详细教程-CSDN博客 1&#xff0c;解决方法 本来想尝试&#xff0c;结果发现CUB安装配置对照表里没有cuda 11.7对应的版本&#xff0c;不敢轻举妄动&#x…...

kotlin 中 string array 怎么表示

在 Kotlin 中&#xff0c;字符串数组可以使用 Array<String> 类型表示。你可以通过多种方式来创建和初始化字符串数组。以下是几种常见的方法&#xff1a; 使用 arrayOf 函数&#xff1a; val stringArray arrayOf("Hello", "World", "Kotli…...

ffmpeg使用bmp编码器把bgr24编码为bmp图像

version #define LIBAVCODEC_VERSION_MAJOR 60 #define LIBAVCODEC_VERSION_MINOR 15 #define LIBAVCODEC_VERSION_MICRO 100 note 不使用AVOutputFormat code void CFfmpegOps::EncodeBGR24ToBMP(const char* infile, const char* width_str, const char* height_str…...

基于YOLOv10+YOLOP+PYQT的可视化系统,实现多类别目标检测+可行驶区域分割+车道线分割【附代码】

文章目录 前言视频效果必要环境一、代码结构1、 训练参数解析2、 核心代码解析1.初始化Detector类2. torch.no_grad()3. 复制输入图像并初始化计数器4. 调用YOLOv10模型进行目标检测5. 提取检测结果信息6. 遍历检测结果并在图像上绘制边界框和标签7. 准备输入图像以适应End-to-…...

计算机网络之令牌总线

上文内容&#xff1a;什么是以太网 1.令牌总线工作原理 在总线的基础上&#xff0c;通过在网络结点之间有序地传递令牌来分配各结点对共享型总线的访问权利&#xff0c;形成闭合的逻辑环路。 完全采用半双工的操作方式&#xff0c;只有获得令牌的结点才能发送信息&#xff…...

策略模式的应用

前言 系统有一个需求就是采购员审批注册供应商的信息时&#xff0c;会生成一个供应商的账号&#xff0c;此时需要发送供应商的账号信息&#xff08;账号、密码&#xff09;到注册填写的邮箱中&#xff0c;通知供应商账号信息&#xff0c;当时很快就写好了一个工具类&#xff0…...

如何使用uer做多分类任务

如何使用uer做多分类任务 语料集下载 找到这里点击即可 里面是这有json文件的 因此我们对此要做一些处理&#xff0c;将其转为tsv格式 # -*- coding: utf-8 -*- import json import csv import chardet# 检测文件编码 def detect_encoding(file_path):with open(file_path,…...

【HICE】转发服务器实验

1.在本地主机上操作 2.在客户端操作设置主机的IP地址为dns 3.测试,客户机是否能ping通...

MATLAB-分类CPO-RF-Adaboost冠豪猪优化器(CPO)优化RF随机森林结合Adaboost分类预测(二分类及多分类)

MATLAB-分类CPO-RF-Adaboost冠豪猪优化器&#xff08;CPO&#xff09;优化RF随机森林结合Adaboost分类预测&#xff08;二分类及多分类&#xff09; 分类CPO-RF-Adaboost冠豪猪优化器&#xff08;CPO&#xff09;优化RF随机森林结合Adaboost分类预测&#xff08;二分类及多分类…...

绝区贰--及时优化降低 LLM 成本和延迟

前言 大型语言模型 (LLM) 为各行各业带来了变革性功能&#xff0c;让用户能够利用尖端的自然语言处理技术处理各种应用。然而&#xff0c;这些强大的 AI 系统的便利性是有代价的 — 确实如此。随着 LLM 变得越来越普及&#xff0c;其计算成本和延迟可能会迅速增加&#xff0c;…...

JDBC【封装工具类、SQL注入问题】

day54 JDBC 封装工具类01 创建配置文件 DBConfig.properties driverNamecom.mysql.cj.jdbc.Driver urljdbc:mysql://localhost:3306/qnz01?characterEncodingutf8&serverTimezoneUTC usernameroot passwordroot新建配置文件&#xff0c;不用写后缀名 创建工具类 将变…...

Windows打开redis以及Springboot整合redis

目录 前言Windows系统打开redisSpringboot整合redis依赖实体类yml配置文件config配置各个数据存储类型分别说明记录string数据写入redis&#xff0c;并查询通过命令行查询 list插入数据到redis中从redis中读取命令读取数据 hash向redis中逐个添加map键值对获取key对应的map中所…...

MySQL使用LIKE索引是否失效的验证

1、简单的示例展示 在MySQL中&#xff0c;LIKE查询可以通过一些方法来使得LIKE查询能够使用索引。以下是一些可以使用的方法&#xff1a; 使用前导通配符&#xff08;%&#xff09;&#xff0c;但确保它紧跟着一个固定的字符。 避免使用后置通配符&#xff08;%&#xff09;&…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...