【数据结构】——栈
一、栈的概念和结构
栈其实就是一种特殊的顺序表,其只允许在一端进出,就是栈的数据的插入和删除只能在一端进行,进行数据的插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的元素遵循先进后出LIFO(Last InFirst Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入栈的位置也是在栈顶。
出栈:栈的删除操作叫做出栈。出栈也是在栈顶。
那么我们的栈是要如何进行实现呢?
我们实现栈的话有两种:链表和数组。
如果是使用链表的话,那么我们要是以头为栈顶,那么我们进行头插的话,就需要先考虑链表是否为空的情况,然后我们的头插的结构也是比较麻烦,每次都需要进行节点的申请。
还有就是进行出栈的时候也比较麻烦。
如果我们使用数组,直接使用数组的尾部为栈顶,那么我们的压栈和出栈都可以直接进行,时间复杂度为O(1)。
不过链表和数组都是可以实现的,不过如果使用链表进行实现的话,我们就推荐使用链表的头为栈顶,然后数组的话我们建议使用数组的尾部为栈顶。这样可以使得压栈和出栈的时间复杂度都为O(1)。
二、栈的实现
1、栈的定义
我们上面提到了,我们实现栈,我们底层使用数组来实现,那么其定义和我们前面学习的顺序表基本是一样的,但是就是我们的栈是有一个限制的,就是其只能在一端进行出入。
栈的定义如下:
其实 arr就是我们存储数据的数组,然后top表示当前我们的栈有多少个元素,capacity就表示我们当前的栈最大的容量。
我们定义好后,那么我们对这个栈进行一个初始化:
因为栈的销毁这里也不做多的解释了。
栈的销毁:
下面我们实现栈的压栈:
我们栈的特点就是其只有一端可以进行压栈和出栈的操作,我们前面说到,我们使用数组来实现的话,那么我们是在数组的尾部进行压栈和出栈,那么我们该如何进行压栈呢?
我们在定义栈的时候,我们有一个成员top其是记录当前我们的栈中的有效成员个数的,那么我们的数组是可以通过下标进行插入数据的,不过要注意的是,我们的栈如果此时为空,而且其表示栈的容量的成员也是空的时候,那么我们就需要进行空间申请的,还有就是栈如果满了,那么我们此时也需要进行空间的申请。不过我们发现我们的栈为空和栈满的时候有个共同点,就是我们的top和capacity是i相等的。所以我们再入栈操作的时候,一开始需要先进行判断当前栈的空间是否足够,不够的话我们要进行扩容,然后我们扩容一般是二倍增容。还有一个特殊情况就是刚开始的时候,我们的容量还是0,那么我们此时进行二倍增容是行不通的,所以我们也特殊处理一下。
代码如下:
上面我们实现了压栈,那么我们接下来就实现栈的另外一个功能:出栈
我们要出栈,那么我们的栈就要不为空才行,所以我们可以先写一个函数判断栈是否为空,然后通过这个函数我们就可以进行出栈,要注意的是我们的栈,出栈也是要在栈顶这一端,所以也是在数组的末尾端,那么我们的top进行--操作就可以了,那么就可以使得我们的栈的有效元素个数减-,而且是栈顶的第一个元素。
压栈:
我们栈有时候只是需要取栈顶的元素,并不需要出栈,那么我们也可以写一个函数来实现,我们的取栈顶元素是很简单的,就是访问数组一样,我们就访问下标为top-1的元素即可。
然后我们也可以获取当前栈的实际有效元素个数:
可以看到我们的栈的两个大的功能还是很好实现的,和我们前面的顺序表大致一样,就是其要控制的是,其入栈和出栈的端要一致。
相关文章:
【数据结构】——栈
一、栈的概念和结构 栈其实就是一种特殊的顺序表,其只允许在一端进出,就是栈的数据的插入和删除只能在一端进行,进行数据的插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的元素遵循先进后出LIFO(Last InFirst O…...
Octave 绘图快速入门指南
目录 1. 基本的 2D 绘图 2. 自定义图形样式 3. 绘制散点图 4. 绘制柱状图 5. 绘制直方图 6. 3D 绘图 6.6.1 3D 曲面图 6.6.2 3D 散点图 7. 绘制极坐标 8. 多子图绘制 总结 Octave 是一个类似于 MATLAB 的开源数学软件,广泛用于数值计算和数据分析。它提供…...
RabbitMQ深入学习
继续上一节的学习,上一节学习了RabbitMQ的基本内容,本节学习RabbitMQ的高级特性。 RocketMQ的高级特性学习见这篇博客 目录 1.消息可靠性1.1生产者消息确认1.2消息持久化1.3消费者消息确认1.4消费失败重试机制1.5消息可靠性保证总结 2.什么是死信交换机…...
数据结构中的栈与队列:原理、实现与应用
前言:栈和队列是计算机科学中两种最基础的线性数据结构,它们的独特操作规则和广泛的应用场景使其成为每一位开发者必须掌握的核心知识。本文将通过生活案例、代码实现和实际应用场景,带您深入理解这两种数据结构的精髓。 1.栈(Sta…...
Android 13 默认打开 使用屏幕键盘
原生设置里,系统-语言和输入法-实体键盘-使用屏幕键盘 选项, 关闭时,外接物理键盘,如USB键盘,输入时不会弹出软键盘。 打开时,外接物理键盘,如USB键盘,输入时会弹出软键盘。 这个选…...
C++GO语言微服务之图片、短信验证码生成及存储
目录 01 session的处理 02 获取网页图片验证码ID 03 测试图片验证码 04 图片验证码模块集成 05 图片验证码功能移植微服务 06 图片验证码功能对接微服务的web实现 07 对接微服务的web实现步骤小结 08 Redis数据库基本操作回顾 09 go语言操作Redis数据库API介绍 10 go语…...
视觉革命来袭!ComfyUI-LTXVideo 让视频创作更高效
探索LTX-Video 支持的ComfyUI 在数字化视频创作领域,视频制作效果的提升对创作者来说无疑是一项重要的突破。LTX-Video支持的ComfyUI便是这样一款提供自定义节点的工具集,它专为改善视频质量、提升生成速度而开发。接下来,我们将详细介绍其功…...
MySQL 索引(一)
文章目录 索引(重点)硬件理解磁盘盘片和扇区定位扇区磁盘的随机访问和连续访问 软件方面的理解建立共识索引的理解 索引(重点) 索引可以提高数据库的性能,它的价值,在于提高一个海量数据的检索速度。 案例…...
认识 Linux 内存构成:Linux 内存调优之内存分配机制和换页行为认知
写在前面 博文内容涉及 Linux 中内存分配和换页机制的基本认知理解不足小伙伴帮忙指正 😃,生活加油99%的焦虑都来自于虚度时间和没有好好做事,所以唯一的解决办法就是行动起来,认真做完事情,战胜焦虑,战胜那些心里空荡荡的时刻,而不是选择逃避。不要站在原地想象困难,行…...
uniapp-商城-50-后台 商家信息
本文介绍了如何在后台管理系统中添加和展示商家信息,包括商家logo、名称、电话、地址和介绍等内容,并支持后期上传营业许可等文件。通过使用uni-app的uni-forms组件,可以方便地实现表单的创建、校验和管理操作。文章详细说明了组件的引入、页…...
汇编语言的温度魔法:单总线温度采集与显示的奇幻之旅
在嵌入式系统的奇妙世界中,汇编语言与硬件的结合总是充满了无限可能。今天,我将带你走进一场充满乐趣的实验:如何用汇编语言在单片机上实现单总线温度采集与显示。这不仅是一次技术探索,更是一场点亮创意与灵感的奇幻之旅…...
2025盘古石初赛WP
来不及做,还有n道题待填坑 文章目录 手机取证 Mobile Forensics分析安卓手机检材,手机的IMSI是? [答案格式:660336842291717]养鱼诈骗投资1000,五天后收益是? [答案格式:123]分析苹果手机检材&a…...
巡检机器人数据处理技术的创新与实践
摘要 随着科技的飞速发展,巡检机器人在各行业中逐渐取代人工巡检,展现出高效、精准、安全等显著优势。当前,巡检机器人已从单纯的数据采集阶段迈向对采集数据进行深度分析的新阶段。本文探讨了巡检机器人替代人工巡检的现状及优势,…...
MySQL的Order by与Group by优化详解!
目录 前言核心思想:让索引帮你“排好序”或“分好组”Part 1: ORDER BY 优化详解1.1 什么是 Filesort?为什么它慢?1.2 如何避免 Filesort?—— 利用索引的有序性1.3 EXPLAIN 示例 (ORDER BY) Part 2: GROUP BY 优化详解2.1 什么是…...
使用小丸工具箱(视频压缩教学)压缩7倍
我们日常经常会遇见视频录制或者剪辑视频生成之后,视频文件非常占用存储空间,那么这款开源工具可以帮助我们压缩7倍,而且视频质量依然清晰。 软件下载 ①:可以通过我分享的CSDN资源下载:https://download.csdn.net/d…...
ui组件二次封装(vue)
组件二次封装的意义 保证一个系统中ui风格和功能的一致性便于维护 从属性、事件、插槽、ref这几方面考虑 属性和事件的处理:ui组件上绑定$attrs(v-model本质也是一个属性加一个事件,所以也在其列) 在自定义组件中打印$attrs&am…...
利用大型语言模型有效识别网络威胁情报报告中的攻击技术
摘要 本研究评估了网络威胁情报(CTI)提取方法在识别来自网络威胁报告中的攻击技术方面的性能,这些报告可从网络上获取,并使用了 MITRE ATT&CK 框架。我们分析了四种配置,这些配置利用了最先进的工具,包…...
笔试模拟 day4
观前提醒: 笔试所有系列文章均是记录本人的笔试题思路与代码,从中得到的启发和从别人题解的学习到的地方,所以关于题目的解答,只是以本人能读懂为目标,如果大家觉得看不懂,那是正常的。如果对本文的某些知…...
TCP的连接管理
三次握手 什么是三次握手? 1. 第一次握手(客户端 → 服务器) 客户端发送一个 SYN 报文,请求建立连接。 报文中包含一个初始序列号 SEQ x。 表示:我想和你建立连接,我的序列号是 x。 2. 第二次握手&a…...
ffmpeg 写入avpacket时候,即av_interleaved_write_frame方法是如何不需要 业务层释放avpacket的 逻辑分析
我们在通过 av_interleaved_write_frame方法 写入 avpacket的时候,通常不需要关心 avpacket的生命周期。 本文分析一下内部实现的部分。 ----> 代表一个内部实现。 A(){ B(); C(); } B(){ D(); } 表示为: A ---->B(); ---->D(); ---->C(); int…...
【MyBatis-7】深入理解MyBatis二级缓存:提升应用性能的利器
在现代应用开发中,数据库访问往往是性能瓶颈之一。作为Java生态中广泛使用的ORM框架,MyBatis提供了一级缓存和二级缓存机制来优化数据库访问性能。本文将深入探讨MyBatis二级缓存的工作原理、配置方式、使用场景以及最佳实践,帮助开发者充分利…...
扫雷革命:矩阵拓扑与安全扩散的数学之美
目录 扫雷革命:矩阵拓扑与安全扩散的数学之美引言第一章 雷区生成算法1.1 组合概率模型1.2 矩阵编码体系第二章 数字计算系统2.1 卷积核运算2.2 边缘处理第三章 安全扩散机制3.1 广度优先扩散3.2 记忆化加速第四章 玩家推理模型4.1 线性方程组构建4.2 概率决策模型第五章 高级…...
通俗的桥接模式
桥接模式(Bridge Pattern) 就像一座桥,把两个原本独立变化的东西连接起来,让它们可以各自自由变化,互不干扰。简单来说,就是 “把抽象和实现分开,用组合代替继承”。 一句话理解桥接模式 假设你…...
金丝猴食品:智能中枢AI-COP构建全链路数智化运营体系
“金丝猴奶糖”,这个曾藏在无数人童年口袋里的甜蜜符号,如今正经历一场数智焕新。当传统糖果遇上数字浪潮,这家承载着几代人味蕾记忆的企业,选择以数智化协同运营平台为“新配方”,将童年味道酿成智慧管理的醇香——让…...
基于定制开发开源AI智能名片S2B2C商城小程序的公私域流量融合运营策略研究
摘要:本文以定制开发开源AI智能名片S2B2C商城小程序为技术载体,系统探讨公域流量向私域流量沉淀的数字化路径。研究通过分析平台流量(公域流量)与私域流量的共生关系,提出"公域引流-私域沉淀-数据反哺"的闭环…...
一、数据仓库基石:核心理论、分层艺术与 ETL/ELT 之辨
随着企业数据的爆炸式增长,如何有效地存储、管理和分析这些数据,从中提炼价值,成为现代企业的核心竞争力之一。数据仓库 (Data Warehouse, DW) 正是为此而生的关键技术。理解其基础理论对于构建高效的数据驱动决策体系至关重要。 一、数据库…...
智慧能源大数据平台建设方案(PPT)
1、建设背景 2、建设思路 3、建设架构 4、应用场景 5、展望 软件开发全方位管理资料包清单概览: 任务部署指令书,可行性研究报告全集,项目启动审批文件,产品需求规格详尽说明书,需求调研策略规划,用户调研问…...
递归函数(斐波那契数列0,1,1,2,3,5,8,13,21,34,55...)
目录 一、斐波那契数列(兔子问题) 二、迭代法(用while循环推下一项 ) 三、递归函数 (函数的定义中调用函数自身的一种函数定义方式) 四、递归函数的底层逻辑推理 (二叉树推倒最左下节点回退法) 一、斐波那契数列(兔子问题&…...
Python 从 SQLite 数据库中批量提取图像数据
Python 从 SQLite 数据库中批量提取图像数据 flyfish 实现了一个可扩展的 SQLite 图像导出工具,能够自动检测图像格式、处理数据前缀,并将数据库中的二进制图像数据导出为文件系统中的标准图像文件 import os import sqlite3 from typing import Dict…...
rust-candle学习笔记12-实现因果注意力
参考:about-pytorch 定义结构体: struct CausalAttention {w_qkv: Linear,dropout: Dropout, d_model: Tensor,mask: Tensor,device: Device, } 定义new方法: impl CausalAttention {fn new(vb: VarBuilder, embedding_dim: usize, ou…...
vue3使用tailwindcss报错问题
npm create vitelatestnpm install -D tailwindcss postcss autoprefixernpx tailwindcss init 4. 不过执行 npx tailwindcss init 的时候控制台就报错了PS E:\vite-demo> npx tailwindcss init npm ERR! cb.apply is not a function npm ERR! A complete log of this run c…...
MySQL COUNT(*) 查询优化详解!
目录 前言1. COUNT(*) 为什么慢?—— InnoDB 的“计数烦恼” 🤔2. MySQL 执行 COUNT(*) 的方式 (InnoDB)3. COUNT(*) 优化策略:快!准!狠!策略一:利用索引优化带 WHERE 子句的 COUNT(*) (最常见且…...
5.Redission
5.1 前文锁问题 基于 setnx 实现的分布式锁存在下面的问题: 重入问题:重入问题是指 获得锁的线程可以再次进入到相同的锁的代码块中,可重入锁的意义在于防止死锁,比如 HashTable 这样的代码中,他的方法都是使用 sync…...
RAG 赋能客服机器人:多轮对话与精准回复
一、引言 在人工智能技术飞速发展的今天,客服机器人已成为企业提升服务效率的重要工具。然而,传统客服系统在多轮对话连贯性和精准回复能力上存在明显短板。检索增强生成(Retrieval-Augmented Generation, RAG)技术通过结合大语言…...
rust-candle学习笔记13-实现多头注意力
参考:about-pytorch 定义结构体: use core::f32;use candle_core::{DType, Device, Result, Tensor}; use candle_nn::{embedding, linear_no_bias, linear, ops, Dropout, Linear, Module, VarBuilder, VarMap};struct MultiHeadAttention {w_qkv: Li…...
PyTorch API 5 - 全分片数据并行、流水线并行、概率分布
文章目录 全分片数据并行 (FullyShardedDataParallel)torch.distributed.fsdp.fully_shardPyTorch FSDP2 (fully_shard) Tensor Parallelism - torch.distributed.tensor.parallel分布式优化器流水线并行为什么需要流水线并行?什么是 torch.distributed.pipelining&…...
STL-list
一、 list的介绍 std::list 是 C 标准模板库(STL)中的一种双向链表容器。每个元素包含指向前后节点的指针,支持高效插入和删除操作,但随机访问性能较差。 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#x…...
WPF中如何自定义控件
WPF自定义控件简化版:账户菜单按钮(AccountButton) 我们以**“账户菜单按钮”为例,用更清晰的架构实现一个支持标题显示、渐变背景、选中状态高亮**的自定义控件。以下是分步拆解: 一、控件核心功能 我们要做一个类似…...
华为云Git使用与GitCode操作指南
案例介绍 本文档带领开发者学习如何在云主机上基于GitCode来使用Git来管理自己的项目代码,并使用一些常用的Git命令来进行Git环境的设置。 案例内容 1 概述 1.1 背景介绍 Git 是一个快速、可扩展的分布式版本控制系统,它拥有异常丰富的命令集,可以提供高级操作和对内部…...
UniRepLknet助力YOLOv8:高效特征提取与目标检测性能优化
文章目录 一、引言二、UniRepLknet 的框架原理(一)架构概述(二)架构优势 三、UniRepLknet 在 YOLOv8 中的集成(一)集成方法(二)代码实例 四、实验与对比(一)对…...
【软件工程】基于频谱的缺陷定位
基于频谱的缺陷定位(Spectrum-Based Fault Localization, SBFL)是一种通过分析程序执行覆盖信息(频谱数据)来定位代码中缺陷的方法。其核心思想是:通过测试用例的执行结果(成功/失败)和代码覆盖…...
stm32之IIC
目录 1.I2C1.1 简介1.2 硬件电路1.3 时序基本单元1.4 时序实例1.4.1 指定地址写1.4.2 当前地址读1.4.3 指定地址读 2.MPU60502.1 简介2.2 参数2.3 硬件电路2.4 框图2.5 文档 3.软件操作MPU60504.I2C通信外设4.1 简介4.2 I2C框图4.3 基本结构4.4 主机发送/接收4.5 软件/硬件波形…...
阿里云购买ECS 安装redis mysql nginx jdk 部署jar 部署web
阿里云服务维护 1.安装JDK 查询要安装jdk的版本,命令:yum -y list java* 命令:yum install -y java-1.8.0-openjdk.x86_64 yum install -y java-17-openjdk.x86_64 2.安装nginx 启用 EPEL 仓库 sudo yum install epel-release 安装 Nginx sudo yum …...
记录 ubuntu 安装中文语言出现 software database is broken
搜索出来的结果是 sudo apt-get install language-pack-zh-han* 然而,无效,最后手动安装如下 apt install language-pack-zh-hans apt install language-pack-zh-hans-base apt install language-pack-gnome-zh-hans apt install fonts-arphic-uming apt install libreoffic…...
质数和约数
一、知识和经验 把质数和约数放在一起就是因为他们有非常多的联系,为了验证这个观点我们可以先学习唯一分解定理:一个大于 1 的自然数一定能被唯一分解为有限个质数的乘积。 而且一个数不仅能被质数分解,原本也应该被自己的约数分解…...
OSPF的四种特殊区域(Stub、Totally Stub、NSSA、Totally NSSA)详解
OSPF的四种特殊区域(Stub、Totally Stub、NSSA、Totally NSSA)通过限制LSA的传播来优化网络性能,减少路由表规模。以下是它们的核心区别: 1. Stub 区域(末梢区域) 允许的LSA类型:Type 1-3&#…...
Docker中运行的Chrome崩溃问题解决
问题 各位看官是否在 Docker 容器中的 Linux 桌面环境(如Xfce)上启动Chrome ,遇到了令人沮丧的频繁崩溃问题?尤其是在打开包含图片、视频的网页,或者进行一些稍复杂的操作时,窗口突然消失?如果…...
【从零实现JsonRpc框架#3】线程模型与性能优化
1.Muduo 的线程模型 Muduo 基于 Reactor 模式 ,采用 单线程 Reactor 和 多线程 Reactor 相结合的方式,通过事件驱动和线程池实现高并发。 1. 单线程模型 核心思想 :所有 I/O 操作(accept、read、write)和业务逻辑均…...
Kubernetes资源管理之Request与Limit配置黄金法则
一、从"酒店订房"看K8s资源管理 想象你经营一家云上酒店(K8s集群),每个房间(Node节点)都有固定数量的床位(CPU)和储物柜(内存)。当客人(Pod&#…...
Windows 上使用 WSL 2 后端的 Docker Desktop
执行命令 docker pull hello-world 执行命令 docker run hello-world 执行命令 wsl -d Ubuntu...