当前位置: 首页 > 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;&…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...