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

                                      🌹个人主页🌹:喜欢草莓熊的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);

总结

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

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

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

相关文章

react 项目中预防xss攻击的插件 dompurify

一、安装 $ yarn add dompurify $ yarn add --dev types/dompurify 二、使用 import DOMPurify from dompurify;// 1、处理&#xff1a; DOMPurify.sanitize(htmlContent)// 2、之后放进 dangerouslySetInnerHTML dangerouslySetInnerHTML{{ __html: cleanHTML }} 如&#…

Android Studio Run窗口中文乱码解决办法

Android Studio Run窗口中文乱码解决办法 问题描述&#xff1a; AndroidStudio 编译项目时Run窗口中文乱码&#xff0c;如图&#xff1a; 解决方法&#xff1a; 依次打开菜单&#xff1a;Help--Edit Custom VM Options&#xff0c;打开studio64.exe.vmoptions编辑框&#xf…

c/c++ 程序运行的过程分析

c/c编译基础知识 GNU GNU&#xff08;GNU’s Not Unix!&#xff09;是一个由理查德斯托曼&#xff08;Richard Stallman&#xff09;在1983年发起的自由软件项目&#xff0c;旨在创建一个完全自由的操作系统&#xff0c;包括操作系统的内核、编译器、工具、库、文本编辑器、邮…

ROS——坐标系管理、监听与广播、常用可视化工具

坐标系管理 TF功能包 小海龟追踪实验 ros版本(20.04)的tf安装命令: sudo apt-get install ros-noetic-turtle-tf 解决因python版本出现的无法生成跟随海龟&#xff1a; sudo ln -s /usr/bin/python3 /usr/bin/python ( -s 软链接,符号链接) ln命令&#xff08;英文全拼&#…

7 动态规划

下面的例子不错&#xff1a; 对于动态规划&#xff0c;能学到不少东西&#xff1b; 你要清楚每一步都在做什么&#xff0c;划分细致就能够拆解清楚&#xff01; xk. - 力扣&#xff08;LeetCode&#xff09; labuladong的算法笔记-动态规划-CSDN博客 动态规划是一种强大的算法…

JDK都出到20多了,你还不会使用JDK8的Stream流写代码吗?

目录 前言 Stream流 是什么&#xff1f; 为什么要用Steam流 常见stream流使用案例 映射 map() & 集合 collect() 单字段映射 多字段映射 映射为其他的对象 映射为 Map 去重 distinct() 过滤 filter() Stream流的其他方法 使用Stream流的弊端 前言 当你某天看…

【图解大数据技术】Hive、HBase

【图解大数据技术】Hive、HBase Hive数据仓库Hive的执行流程Hive架构数据导入Hive HBaseHBase简介HBase架构HBase的列式存储HBase建表流程HBase数据写入流程HBase数据读取流程 Hive Hive是基于Hadoop的一个数据仓库工具&#xff0c;Hive的数据存储在HDFS上&#xff0c;底层基于…

价格预言机的使用总结(一):Chainlink篇

文章首发于公众号&#xff1a;Keegan小钢 前言 价格预言机已经成为了 DeFi 中不可获取的基础设施&#xff0c;很多 DeFi 应用都需要从价格预言机来获取稳定可信的价格数据&#xff0c;包括借贷协议 Compound、AAVE、Liquity &#xff0c;也包括衍生品交易所 dYdX、PERP 等等。…

Linux 防火墙配置指南:firewalld 端口管理应用案例(二十个实列)

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f427;Linux基础知识(初学)&#xff1a;点击&#xff01; &#x1f427;&#x1f427;Linux高级管理专栏&#xff1a;点击&#xff01; &#x1f510;Linux中firewalld防火墙&#xff1a;点击&#xff01; ⏰️…

adb不插usb线通过wifi调试

说起做手机开发也有好多年了&#xff0c;说来惭愧&#xff0c;我最近才知道安卓手机是可以不插数据线进行开发调试的。起因是公司近期采购了一批安卓一卡通设备&#xff0c;需要对其进行定制开发APP,但是由于我插USB调试发现没有反应。通过询问厂家才知道可以通过WIFI进行调试。…

去除gif动图背景的工具网站

选择视频或GIF - 取消屏幕 (unscreen.com)https://www.unscreen.com/upload

Upload-Labs靶场闯关

文章目录 Pass-01Pass-02Pass-03Pass-04Pass-05Pass-06Pass-07Pass-08Pass-09Pass-10Pass-11Pass-12Pass-13Pass-14Pass-15Pass-16Pass-17Pass-18Pass-19Pass-20 以下是文件上传绕过的各种思路&#xff0c;不过是鄙人做题记下来的一些思路笔记罢了。 GitHub靶场环境下载&#x…

进程控制-fork函数

一个进程&#xff0c;包括代码、数据和分配给进程的资源。 fork &#xff08;&#xff09;函数通过系统调用创建一个与原来进程几乎完全相同的进程&#xff0c;也就是两个进程可以做完全相同的事&#xff0c;但如果初始参数或者传入的变量不同&#xff0c;两个进程也可以做不同…

通过卷防水上限,解锁手机的新玩法?IP68之间亦有不同

当手机的日常防水已经成了基本功&#xff0c;防水能力的上限便成了新的赛道。 毕竟再谨慎的人&#xff0c;也可能会有手滑的时候。这个时候&#xff0c;一台有着IP68级防水的手机&#xff0c;就能给你提供一份安心。 【IP68是标准上限&#xff0c;不是手机防水上限】 IP68是…

使用LoFTR模型进行图像配准、重叠区提取

LoFTR模型源自2021年CVPR提出的一篇论文LoFTR: Detector-Free Local Feature Matching with Transformers&#xff0c;其基于pytorch实现图像配准&#xff0c;与基于superpointsuperglue的方法不同&#xff0c; 是一个端到端的图像配准方法。与LoFTR官方库相关的有loftr2onnx库…

【MYSQL】InnoDB引擎为什么选可重复读作为默认隔离级别

InnoDB引擎为什么选可重复读作为默认隔离级别 一般的DBMS系统&#xff0c;默认都会使用读提交&#xff08;Read-Comitted&#xff0c;RC&#xff09;作为默认隔离级别&#xff0c;如Oracle、SQL Server等&#xff0c;而MySQL却使用可重复读&#xff08;Read-Repeatable&#x…

基于GWO灰狼优化的多目标优化算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1灰狼优化算法原理 4.2 多目标优化问题(MOP)的帕累托最优解 4.3 基于GWO的多目标优化算法 5.完整程序 1.程序功能描述 基于GWO灰狼优化的多目标优化算法matlab仿真&#xff0c;目标函数…

浏览器打不开网页、但是电脑有网络,解决办法(win11)

2023.07.06测试有效 华为电脑拿去免费拆机保养后&#xff0c;发现浏览器连接不上网了&#xff0c;但是&#xff01;微信又能登录得上&#xff0c;也就是说电脑还是有网的。 原文链接 一、问题截图 二、解决方法 1.右键打开“网络和Internet设置” 2.打开“代理” 3.将该选项设…

[数据结构] 基于交换的排序 冒泡排序快速排序

标题&#xff1a;[数据结构] 基于交换的排序 冒泡排序&&快速排序 水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 &#xff08;一&#xff09;冒泡排序 优化后实现&#xff1a; &#xff08;二&#xff09;快速排序 I、实现方法&#xff1a; &#…

24-7-6-读书笔记(八)-《蒙田随笔集》[法]蒙田 [译]潘丽珍

文章目录 《蒙田随笔集》阅读笔记记录总结 《蒙田随笔集》 《蒙田随笔集》蒙田&#xff08;1533-1592&#xff09;&#xff0c;是个大神人&#xff0c;这本书就是250页的样子&#xff0c;但是却看了好长好长时间&#xff0c;体会还是挺深的&#xff0c;但看的也是不大仔细&…