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

栈详解

目录

    • 栈的概念及结构
    • 栈的实现
      • 数组栈的实现
      • 数组栈功能的实现
        • 栈的初始化void STInit(ST* pst)
          • 初始化情况一
          • 初始化情况二
        • 代码
        • 栈的插入void STPush(ST* pst, STDataType x)
          • 代码
        • 栈的删除void STPop(ST* pst)
          • 代码
        • 栈获取数据STDataType STTop(ST* pst)
          • 代码
        • 判断栈是否为空bool STEmpty(ST* pst)
        • 求栈的元素个数int STSize(ST* pst)
        • 栈的销毁void STDestory(ST* pst)
        • 栈的打印方式
        • 栈溢出问题

栈的概念及结构

栈:一种特殊的线性表(数据是挨着储存,是连续的),其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。
在这里插入图片描述
在这里插入图片描述

注意栈顶不能叫做头,栈底不能叫做尾

栈的实现

栈分为两种
数组栈:数组通常让首元素的空间为栈底,末尾为栈顶(因为栈的规则是后进先出,数组让末尾为栈顶的尾删效率更高)
在这里插入图片描述

链式栈:
双向链表实现的话栈顶可以是头节点或者尾借点,用头节点当栈顶就是头插或者头删,尾节点当栈顶就是尾插尾删
单链表实现的话通常用头节点当栈顶,尾节点当栈底(因为单链表头插头删的时间复杂度低,而尾插尾删需要遍历一遍链表,时间复杂度高)

在这里插入图片描述

数组栈和链式栈相比,数组栈相对来说更好一点,因为数组栈简单快捷,虽然数组栈有时需要扩容,但是这种情况相对来说比较少,因为一次扩容就是2倍左右(不是规定必须2倍,只是2倍相对来说更合理)
对于两个链式栈相比,单链表会更合适一点,因为双向链表实现起来更复杂一点

数组栈的实现

typedef struct stack
{int* a;int top;//栈顶int capacity;空间
}ST;

数组栈功能的实现

栈的初始化void STInit(ST* pst)

初始化的时对于指针a和capacity,我们很容易就会想到a=NULL,capacity=0

而对于top的初始化就需要注意

初始化情况一

如果top为数组的下标,当top初始化为0时就会出现歧义
当数组为空时,top=0
当数组中有一个元素时,top也为0
为了避免这种情况,我们将top初始化成-1

在这里插入图片描述

在这里插入图片描述

初始化情况二

我们也可以认为top代表数据个数,或者理解成指向栈顶元素的下一个位置
这样top就可以初始化成0

在这里插入图片描述

代码
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0//或者pst->top = -1;
}

后面的代码我们讨论top初始化为0的情况

栈的插入void STPush(ST* pst, STDataType x)

栈的插入和之前我写的顺序表还有链表方式都差不多,有疑惑的可以去看看我之前写的文章

代码
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
栈的删除void STPop(ST* pst)

栈的删除要注意不能让top=0,因为top=0后就代表栈没有元素可以删除,所以要断言

代码
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
栈获取数据STDataType STTop(ST* pst)

因为top初始化为0,所以top为栈顶元素的下一个的下标

代码
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
判断栈是否为空bool STEmpty(ST* pst)
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
求栈的元素个数int STSize(ST* pst)
int STSize(ST* pst)
{return pst->top;
}
栈的销毁void STDestory(ST* pst)
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
栈的打印方式

由于栈遵循后进先出,在访问栈的元素时,我们需要做到访问一个栈的元素就删除一个栈的元素,当栈访问完一遍后,栈的元素就全没了,也就是栈为空

int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}printf("\n");return 0;
}
栈溢出问题

栈有两种
数据结构的栈:存储数据

操作系统的栈:内存区域的划分(malloc,realloc…)

栈溢出中的栈是指操作系统的栈,发生的情况一般为递归出现返回条件错误,导致一直调用函数建立函数栈帧

相关文章:

栈详解

目录 栈栈的概念及结构栈的实现数组栈的实现数组栈功能的实现栈的初始化void STInit(ST* pst)初始化情况一初始化情况二 代码栈的插入void STPush(ST* pst, STDataType x)代码 栈的删除void STPop(ST* pst)代码 栈获取数据STDataType STTop(ST* pst)代码 判断栈是否为空bool ST…...

硬盘 <-> CPU, CPU <-> GPU 数据传输速度

1. 硬盘 <-> CPU 数据传输速度 import time import os# 定义文件大小和测试文件路径 file_size 1 * 1024 * 1024 * 100 # 100 MB 的文件大小 file_path "test_file.bin"# 创建一个测试文件并测量写入速度 def test_write_speed():data os.urandom(file_si…...

数据编排与ETL有什么关系?

数据编排作为近期比较有热度的一个话题&#xff0c;讨论度比较高&#xff0c;同时数据编排的出现也暗示着数字化进程的自动化发展。在谈及数据编排时&#xff0c;通常也会谈到ETL&#xff0c;这两个东西有相似点也有不同点。 数据编排和ETL&#xff08;提取、转换、加载&#x…...

来了解一下!!!——React

React 是一个用于构建用户界面的 JavaScript 库&#xff0c;特别适合用于创建单页面应用程序&#xff08;SPA&#xff09;。它由 Facebook 维护&#xff0c;并且拥有一个活跃的社区&#xff0c;这使得 React 成为了目前最流行的前端框架之一。以下是关于 React 的一些重要信息和…...

用vite创建项目

一. vite vue2 1. 全局安装 create-vite npm install -g create-vite 2. 创建项目 进入你想要创建项目的文件夹下 打开 CMD 用 JavaScript create-vite my-vue2-project --template vue 若用 TypeScript 则 create-vite my-vue2-project --template vue-ts 这里的 …...

json-server的使用(根据json数据一键生成接口)

一.使用目的 在前端开发初期&#xff0c;后端 API 可能还未完成&#xff0c;json-server 可以快速创建模拟的 RESTful API&#xff0c;帮助前端开发者进行开发和测试。 二.安装 npm install json-server //局部安装npm i json-server -g //全局安装 三.使用教程 1.准备一…...

半波正弦信号的FFT变换

目录 Hello&#xff0c; 大家好&#xff0c;这一期我们谈谈半波正弦信号的FFT变化长什么样子。本文硬件使用GFARM02硬件模块[1]&#xff0c;文章最后有其淘宝链接。核心器件为STM32F103RCT6&#xff0c;为Cortex-M3核&#xff0c;采用的CMSIS版本为CMSIS_5-5.6.0。 如图1所示&…...

Python数据分析NumPy和pandas(二十三、数据清洗与预处理之五:pandas的分类类型数据)

pandas的分类类型数据&#xff08;Categorical Data&#xff09; 这次学习使用Categorical Data&#xff0c;在某些 pandas 操作中使用分类类型能实现更好的性能和减少内存使用。另外还学习一些工具&#xff0c;这些工具有助于在统计和机器学习应用程序中使用分类数据。 一.背…...

redis源码系列--(二)--multi/exec/eval命令执行流程

本文主要记录multi/exec、eval、redis执行lua脚本的源码流程 redis在exec之前&#xff0c;所有queued的命令是没有执行的&#xff0c;&#xff01;&#xff01;&#xff01;在执行时会通过检测client是否被打上CLIENT_DIRTY_CAS标记来判断[watch后,exec时]时间段内是否有key被…...

【力扣打卡系列】移动零(双指针)

坚持按题型打卡&刷&梳理力扣算法题系列&#xff0c;语言为go&#xff0c;Day19 移动零&#xff08;双指针&#xff09; 题目描述 解题思路 p和q同时从起点移动&#xff0c;p每次都&#xff0c;q仅在交换时&#xff0c;p遇到非零数时与p值交换&#xff01;&#xff01;…...

无源元器件-电容选型参数总结

🏡《总目录》 目录 1,概述2,电容选型参数2.1,电容值(Capacitance)2.2,额定电压(Rated Voltage )2.3,外观(Appearance)2.4,尺寸(Dimension)2.5,耐压(Voltage Proof)2.6,绝缘电阻(Insulation Resistance)2.7,耗散因子或耗散系数(IQ or Dissipation Facto…...

Linux下的socket编程

概述 下面是一个通用的server端程序源码&#xff0c;用于实现两个client之间的通信。 功能 1、接收user的命令cmd消息&#xff0c;并将cmd消息发送到dev&#xff1b; 2、接收dev的应答ack消息&#xff0c;并将ack消息发送到user&#xff1b; 架构实现 通过6个线程实现。 …...

【算法】Floyd多源最短路径算法

目录 一、概念 二、思路 三、代码 一、概念 在前面的学习中&#xff0c;我们已经接触了Dijkstra、Bellman-Ford等单源最短路径算法。但首先我们要知道何为单源最短路径&#xff0c;何为多源最短路径 单源最短路径&#xff1a;从图中选取一点&#xff0c;求这个点到图中其他…...

iOS SmartCodable 替换 HandyJSON 适配记录

前言 HandyJSON群里说建议不要再使用HandyJSON&#xff0c;我最终选择了SmartCodable 来替换&#xff0c;原因如下&#xff1a; 首先按照 SmartCodable 官方教程替换 大概要替换的内容如图&#xff1a; 详细的替换教程请前往&#xff1a;使用SmartCodable 平替 HandyJSON …...

使用 axios 拦截器实现请求和响应的统一处理(附常见面试题)

在现代前端开发中&#xff0c;我们经常需要向服务器发送 HTTP 请求&#xff0c;并根据响应内容做不同的处理。axios 是一个流行的 HTTP 库&#xff0c;提供了 拦截器 功能&#xff0c;可以在请求和响应阶段插入自定义逻辑&#xff0c;这使得我们在处理认证、错误提示等场景时更…...

阿里 Sentinel

1、什么是sentinel&#xff1f; sentinel顾名思义&#xff1a;卫兵&#xff1b;在Redis中叫做哨兵&#xff0c;用于监控主从切换&#xff0c;但是在微服务中叫做流量防卫兵。 Sentinel 以流量为切入点&#xff0c;从流量控制、熔断降级、系统负载保护等多个维度保护服务的稳定…...

【点云网络】 pointnet 和 pointnet++

这两个网络都是斯坦福大学的一个团队提出的 我先先看一下pointnet的网络架构,这个网络比较经典&#xff0c;是2016年提出的&#xff1a; PointNet 是一个专门用于点云数据处理的神经网络。它的设计目的是直接操作不规则的点云数据&#xff0c;而无需将点云数据转换为规则网格或…...

.net core mvc 控制器中页面跳转

方式一&#xff1a; 在控制器的方法内部结尾使用 return View(); 来打开与方法同名的页面&#xff0c;如&#xff1a; public ActionResult Login() { return View(); } 该写法打开 Login 页面。 方式二&#xff1a; 可以添加参数来显式地指定要跳转的页面&#xff0…...

大学适合学C语言还是Python?

在大学学习编程时&#xff0c;选择C语言还是Python&#xff0c;这主要取决于你的学习目标、专业需求以及个人兴趣。以下是对两种语言的详细比较&#xff0c;帮助你做出更明智的选择&#xff1a; C语言 优点&#xff1a; 底层编程&#xff1a;C语言是一种底层编程语言&#x…...

跳表原理课堂笔记

课程地址 跳表是一种基于随机化的有序数据结构&#xff0c;它提出是为了赋予有序单链表以 O(logn) 的快速查找和插入的能力 创建 首先在头部创建一个 sentinel 节点&#xff0c;然后在 L1 层采用“抛硬币”的方式来决定 L0 层的指针是否增长到 L1 层 例如上图中&#xff0c;L…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...