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

《数据结构之美--栈和队列》

news 来源：原创 2025/7/1 17:01:47

一：引言：

上次我们学习了双向链表的实现，这次我们来学习两个新的数据结构，因为比较简单，就放在一块学习。

二：栈的实现

1. 栈的结构与性质

只凭文字来描述的话不够生动，下面我们就以图画的形式来直观感受一下栈。

在这里插入图片描述

2. 思考：

既然我们已经知道了栈的结构和性质，那么就是来实现栈。我们用什么来实现栈呢？
先来考虑拿刚学的链表来实现栈：
在这里插入图片描述

接着再来考虑用顺序表来实现栈：
在这里插入图片描述
可以看到用顺序表和链表实现栈的时间复杂度都为o(1)，那么只好再从空间角度来比较，若用链表来实现的话，需要不停地申请新节点，并且链表的存储结构还不一定连续，容易造成空间的碎片化，而顺序表的话存储结构是一个接一个的连续着的，空间利用率会更好，并且顺序表采用动态数组，也能做到动态扩容，因此，结合以上几点分析，还是用顺序表来实现栈更好一点。

3. 定义栈

在这里插入图片描述
因为进栈和出栈都是在栈顶进行，因此这里需要定义栈顶位置，除了动态数组，还需要知道栈的空间大小，因此再定义一个容器大小。

4. 初始化

声明：

注意这里因为要改变结构体中的成员，因此传入的是结构体指针（结构体的地址）
在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述

5. 入栈

声明：

在这里插入图片描述

逻辑分析：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述
可以看到测试正常

6. 出栈

声明：

在这里插入图片描述

逻辑分析：

栈的出栈其实就是顺序表的删除逻辑，只需让top--即可，这时top位置的元素就是无效元素了。
注：但进行出栈操作之前还要判断栈是否为空，也就是top是否为0。

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述
可以看到测试没问题

7. 取出栈顶元素

声明：

在这里插入图片描述

逻辑实现：

因为在每次入栈之后top会往后走一格，因此栈顶位置即为top - 1
在这里插入图片描述

8. 栈中有效元素个数

声明：

在这里插入图片描述

逻辑实现：

由于我们是从下标为0的位置开始使用，因此top的值即为栈中有效元素的个数
在这里插入图片描述

9.销毁

声明：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述

三：队列的实现

1. 队列的结构和性质

队列：一种具有先进先出性质的连续存储的数据结构。
下面通过图画来辅助理解：
在这里插入图片描述

2.思考：

在知道了队列的性质和结构之后，就是来实现队列，下面我们还是从顺序表和链表的角度来考虑。
先来看顺序表：
在这里插入图片描述
接下来再看链表：

通过上述分析可以看到无论是顺序表还是链表，时间复杂度都不能做到入队和出队的时间复杂度同时为o(1)
因此就需要想办法来优化一下：我们可以发现：队列的出队和入队，一个是针对队头，一个是针对队尾，队列的中间部分我们不关心，并且队列是由一个个节点组成的，因此可以分为两个结构，定义一个队列结构，定义一个节点结构，这样就可以实现队列的出队和入队时间复杂度都为o(1)

3. 定义队列

在这里插入图片描述

这里我们先定义了每个节点的结构，然后定义了队列结构，其中维护了指向队头和指向队尾的两个结构体指针。

4. 初始化

声明：

这里还是老样子，由于需要修改结构体的成员，要改变实参，因此传入的是结构体指针（结构体的地址）
在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述
可以看到初始化正常、

5.入队

声明：

在这里插入图片描述

逻辑分析：

在这里插入图片描述

逻辑实现：

在这里插入图片描述
进队分为了两种情况：空队列与非空队列

6. 判空

声明：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

7.出队

声明：

在这里插入图片描述

逻辑分析：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

8. 取出队头元素

声明：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述
这里我们让1 2 依次入队，之后我们又执行了一次出队，因此队头就成了2

9. 取出队尾元素

声明：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述

10.队列中有效元素个数

声明：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述

11.销毁

声明：

在这里插入图片描述

逻辑实现：

在这里插入图片描述

测试：

在这里插入图片描述

总结：

在这篇博客中，我们实现了具有先进后出性质的栈和具有先进先出性质的队列。
下篇博客我们将练习几道关于栈和队列的oj题。

相关文章：

《数据结构之美--栈和队列》

一：引言： 上次我们学习了双向链表的实现，这次我们来学习两个新的数据结构，因为比较简单，就放在一块学习。二：栈的实现 1. 栈的结构与性质只凭文字来描述的话不够生动，下面我们就以图画的形…...

编程日记 2025/7/1 17:01:47

如何彻底卸载Android Studio？

要彻底卸载 Android Studio，需要分别在不同操作系统上进行不同的操作，以下为你详细介绍： Windows 系统卸载主程序通过 “开始” 菜单，打开 “设置”，选择 “应用”。在应用列表中找到 “Android Studio”&#xff…...

编程日记 2025/7/1 16:53:02

乐聚机器人与地瓜机器人达成战略合作，联合发布Aelos Embodied具身智能

要闻 4月19日，在CCF人形机器人与人工智能技术巡回研讨会（武汉站）上，乐聚机器人与地瓜机器人达成战略合作，双方将基于RDK X5、RDK S100以及更高性能的国产大算力平台，就夸父（KUAVO）、…...

编程日记 2025/6/29 9:18:00

[MERN 项目实战] MERN Multi-Vendor 电商平台开发笔记（v2.0 从 bug 到结构优化的工程记录）

[MERN 项目实战] MERN Multi-Vendor 电商平台开发笔记（v2.0 从 bug 到结构优化的工程记录） 其实之前没想着这么快就能把 2.0 的笔记写出来的，之前的预期是，下一个阶段会一直维持到将 MERN 项目写完，毕竟后期很多东西都…...

编程日记 2025/6/29 12:18:06

KS卡片铃铛知多少，春花秋月何时了

废话不多说，直接上干活卡片随意跳转技术可以私信卡片，也可以群发卡片，丝毫不影响使用铃铛跳转实例需要一定要找我哦：qmfy01...

编程日记 2025/6/29 9:17:57

SQL 语法

好的，下面是对 SQL 语法的简洁总结，涵盖了常见的 SQL 操作和基本语法结构。创建一个表 (CREATE TABLE) 首先，我们需要创建一个表 users，如果还没有的话： CREATE TABLE users ( id INT PRIMARY KEY, name VARCHAR(100)…...

编程日记 2025/6/29 9:18:10

《ATPL地面培训教材13：飞行原理》——第1章：概述与定义

翻译：刘远贺；辅助工具：Cluade 3.7 第1章：概述与定义目录概述一般定义术语表符号列表希腊符号其他自我评估问题答案概述飞机的基本要求如下： 机翼产生升力； 机身容纳载荷； 尾部表面增加…...

编程日记 2025/7/1 8:23:20

https nginx 负载均衡配置

我的系统是OpenEuler。安装nginx yum install -y nginx 启动&开机启动 systemctl start nginx systemctl enable nginx 自定义conf配置文件 cat <<EOF >> /etc/nginx/conf.d/load_balancer.conf upstream backend {ip_hash; # 防止验证码验证失败server…...

编程日记 2025/7/1 16:50:07

初始https附带c/c++源码使用curl库调用

使用C与CURL开发HTTPS客户端的深度指南目录准备工作基础HTTPS请求实现核心功能扩展进阶配置与优化安全注意事项调试与问题排查跨平台适配要点一、准备工作 1.1 cURL库简介 cURL（Client URL Request Library）是一个支持多种网络协议的开源库&…...

编程日记 2025/6/29 9:18:24

NI Multisim官网下载: 电路设计自动化EDA仿真软件

NI Multisim是一款由美国国家仪器公司（National Instruments，简称 NI）推出的电路设计与仿真软件，广泛应用于工程教育、电子电路开发和科研领域。它结合了图形化的电路绘图界面与强大的 SPICE 仿真引擎，让用户可以在虚拟…...

编程日记 2025/6/29 12:01:39

通过阿里云Milvus与通义千问VL大模型，快速实现多模态搜索

本文主要演示了如何使用阿里云向量检索服务Milvus版与通义千问VL大模型，提取图片特征，并使用多模态Embedding模型，快速实现多模态搜索。基于灵积（Dashscope）模型服务上的通义千问 API以及Embedding API来接入图片、文…...

编程日记 2025/6/29 9:18:15

React 与 Vue：两大前端框架的深度对比

在前端开发领域，React 和 Vue 无疑是当下最受欢迎的两大框架。它们各自拥有独特的优势和特点，吸引了大量开发者。无论是初学者还是经验丰富的工程师，选择 React 还是 Vue 都是一个常见的问题。本文将从多个角度对 React 和 Vue 进行对比&…...

编程日记 2025/6/29 9:18:03

OpenFeign和Gateway

OpenFeign和Gateway 一.OpenFeign介绍二.快速上手1.引入依赖2.开启openfeign的功能3.编写客户端4.修改远程调用代码5.测试三.OpenFeign参数传递1.传递单个参数2.多个参数、传递对象和传递JSON字符串3.最佳方式写代码继承的方式抽取的方式四.部署OpenFeign五.统一服务入口-Gat…...

编程日记 2025/7/1 16:53:44

openwrt作旁路由时的几个常见问题 openwrt作为旁路由配置zerotier 图文讲解

1 先看openwrt时间，一定要保证时间和浏览器和服务器是一致的，不然无法更新 2 openwrt设置旁路由前先测试下，路由器能否ping通主路由，是否能够连接外网，好多旁路由设置完了，发现还不能远程好多就是旁路由本…...

编程日记 2025/7/1 16:57:05

ai如何赋能艺术教育

在数字化浪潮席卷全球的今天，人工智能（AI）作为第四次工业革命的核心驱动力，正以前所未有的速度重塑教育生态。艺术教育领域作为培养创造力、批判性思维与跨文化理解力的关键阵地，正经历着AI技术带来的深刻变革。本文将从技术赋能、教育范式革新、全球化协作三个维度，探讨…...

编程日记 2025/6/29 11:47:42

NocoBase 本周更新汇总：联动规则条件左侧支持变量

原文链接：https://www.nocobase.com/cn/blog/weekly-updates-20250424。汇总一周产品更新日志，最新发布可以前往我们的博客查看。 NocoBase 目前更新包括的版本更新包括三个分支：main ，next和 develop。 main ：截止…...

编程日记 2025/6/29 9:18:04

协作开发攻略：Git全面使用指南 — 第二部分高级技巧与最佳实践

协作开发攻略：Git全面使用指南 — 第二部分高级技巧与最佳实践 Git 是一种分布式版本控制系统，用于跟踪文件和目录的变更。它能帮助开发者有效管理代码版本，支持多人协作开发，方便代码合并与冲突解决，广泛应用于软件开…...

编程日记 2025/6/29 10:42:52

sass 变量

基本使用如果分配给变量的值后面添加了 !default 标志 ，这意味着该变量如果已经赋值，那么它不会被重新赋值，但是，如果它尚未赋值，那么它会被赋予新的给定值。如果在此之前变量已经赋值，那就不使用默认值…...

编程日记 2025/7/1 16:54:27

多级缓存架构深度解析：从设计原理到生产实践

多级缓存架构深度解析：从设计原理到生产实践一、多级缓存架构核心定位与设计原则 1. 架构分层与角色定位多级缓存通过分层存储、流量削峰、数据分级实现性能与成本的平衡，典型三层架构如下： 层级代表组件存储介质数据特征命中目标成本级…...

编程日记 2025/6/29 10:47:04

（51单片机）LCD展示动画（延时函数）（LLCD1602教程）

前言： 前面我们说过，之前LCD1602模块有点难，但是现在，我们通过几遍博客的学习，今天来讲一下LCD1602的原理演示视频： LCD1602流动源代码： main.c #include <STC89C5xRC.H> #include &q…...

编程日记 2025/6/28 15:27:44

12N60-ASEMI无人机专用功率器件12N60

编辑：LL 12N60-ASEMI无人机专用功率器件12N60 型号：12N60 品牌：ASEMI 封装：TO-220F 最大漏源电流：12A 漏源击穿电压：600V 批号：最新 RDS（ON）Max：0.68…...

编程日记 2025/6/29 9:18:11

[Redis] Redis最佳实践

🌸个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 🏵️热门专栏: 🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 🍕 Collection与…...

编程日记 2025/6/29 9:18:14

arm64适配系列文章-第九章-arm64环境上sentinel的部署

ARM64适配系列文章第一章 arm64环境上kubesphere和k8s的部署第二章 arm64环境上nfs-subdir-external-provisioner的部署第三章 arm64环境上mariadb的部署第四章 arm64环境上nacos的部署第五章 arm64环境上redis的部署第六章 arm64环境上rabbitmq-management的部署第七章…...

编程日记 2025/6/29 9:18:12

3dmax模型怎么处理3dtiles，制作制作B3DM格式文件

1咱们先打3dmax，或su或者其他软件建模型 2记住面一定一定要少，面一定不能多，也不要是VR材质，可以用插件一键处理 3导出fbx 4使用cesium把fbx转换 5这里可以坐标，因为要对地图位置 6转换出来了，3dtiles格式…...

编程日记 2025/6/29 9:18:02

雪花算法生成int64，在前端js的精度问题

1.问题背景后端对视频生成唯一性id，在发送评论阶段，由于后端接收的json数据格式，设置videoId为int64。前端于是使用js的Number函数，进行字符串转换为数字，由于不清楚js的精度范围，产生了携带的videoId变化…...

编程日记 2025/6/29 9:18:08

软件测试报告包括哪些内容?可出专业软件测试方案的测评机构推荐

随着信息技术的快速发展，软件质量已经成为决定企业竞争力的重要因素之一。软件测试作为保障软件质量的关键环节，其成果汇总形成的“软件测试报告”在项目生命周期中扮演着重要角色。软件测试报告就是用来反映测试工作全貌的报告。从测试准备、过程、结…...

编程日记 2025/6/29 9:18:30

dockercompose文件仓库

mysql version: 3 # 使用docker-compose的版本，根据需要可以调整# 创建数据目录 # mkdir -p /home/docker/mysql/mysql_data # mkdir -p /home/docker/mysql/mysql_logs # 给予适当的权限（确保MySQL容器可以读写这些目录） # chmod 777 /ho…...

编程日记 2025/6/29 11:38:35

Docker 的基本概念和优势以及在应用程序开发中的实际应用

Docker 是一种开源的容器化平台，可以让开发者将应用程序及其所有依赖项打包成一个独立的容器，从而实现应用程序的快速部署和运行。下面是 Docker 的基本概念和优势：基本概念：容器：一个轻量级、独立的运行环境，包含应用程序及其所有依赖项。镜像：一个只读的模板，用于创…...

编程日记 2025/6/29 11:49:02

JavaWeb：HtmlCss

快速入门 <html><head><title>HTML快速入门</title><head><body><h1>Hello HTML</h1><img src"1.png"></img></body> </html>开发工具vscode 常见便签&样式（新闻&#xff0…...

编程日记 2025/6/29 11:29:26

linux centOS7.9 No package docker-ce available

docker pull apache/apisix:3.2.2-centos Error response from daemon: missing signature key 处理方式如下： 问题：在纯净机里安装docker时报错No package docker-ce available。解决办法： 1、更新yum，使用yum -y upgrade&#…...

编程日记 2025/6/29 10:39:10

机器学习（8）——主成分分析

文章目录 1. 主成分分析介绍2. 核心思想3. 数学基础4. 算法步骤4.1. 数据标准化：4.2. 计算协方差矩阵：4.3. 特征分解：4.4. 选择主成分：4.5 降维： 5. 关键参数6. 优缺点7. 改进变种8. 应用场景9. Python示例10. 数学推导…...

编程日记 2025/6/29 12:18:20

使用深度 Q 学习解决Lunar lander问题

使用深度 Q 学习解决Lunar lander问题 0. 前言1. 使用深度 Q 网络解决 Atari 游戏2. 定义环境3. 解决 Lunar lander 问题相关链接 0. 前言深度 Q 学习模型只需观察状态作为输入就能够解决经典 Atari 游戏，这是一个重大突破，从那时起，深度强…...

编程日记 2025/6/29 9:29:38

centos7使用yum快速安装最新版本Jenkins-2.462.3

Jenkins支持多种安装方式：yum安装、war包安装、Docker安装等。官方下载地址：https://www.jenkins.io/zh/download 本次实验使用yum方式安装Jenkins LTS长期支持版，版本为 2.462.3。一、Jenkins基础环境的安装与配置 1.1：基本…...

编程日记 2025/6/29 11:45:18

Bean的生命周期

1.实例化Bean（通过BeanDefinition反射调用无参构造创建对象，如果没有无参构造，需要指定唯一构造方法） 2.给Bean的属性set()赋值 3.检查Bean是否实现了Aware相关接口，实现的话则执行方法 Aware接口：空接口&…...

编程日记 2025/6/29 12:01:32

【缓存与数据库结合方案】伪从技术 vs 直接同步/MQ方案的深度对比

伪从技术 vs 直接同步/MQ方案的深度对比直接同步修改或通过MQ消息队列也能实现类似同步功能，但伪从技术（通过消费binlog实现数据同步）在某些场景下具有独特优势。下面我将从多个维度进行详细对比分析： 一、核心差异对比表方案…...

编程日记 2025/6/29 10:24:48

【前端】【业务场景】【面试】在前端开发中，如何实现文件的上传与下载功能，并且处理可能出现的错误情况？

前端文件上传与下载攻略本文目标：帮你快速掌握文件上传 & 下载的核心实现方式，并在常见出错场景下保持“优雅不崩溃”。一、文件上传 1. 基础结构 <input type"file" id"fileInput" /> <button id"uploadBtn&…...

编程日记 2025/6/29 11:45:07

【axios取消请求】如何在token过期后取消未响应的请求

功能背景： 我们在实际项目中通常会遇到登录过期后会跳登录页的情况，回跳过程会根据接口请求的状态码判断是否登陆状态过期，并给出用户提示，如果此时存在多个请求接口同时调用，就会同时报出多个登录过期的提示&#xf…...

编程日记 2025/6/29 11:41:46

【高频考点精讲】JavaScript中的组合模式：从树形结构到组件嵌套实战

📚 目录 📦 什么是组合模式？🌲 基础版：用组合模式构建一个简单的树形结构💡 举个更真实的场景：菜单组件🧠 为什么组合模式在前端特别重要？🔨 实战案例：组件嵌套组合 + 权限控制🧩 组合模式的延伸用法：搭建 UI DSL 引擎🧪 面试题时间（欢迎评论区作答）组…...

编程日记 2025/6/29 9:18:31

《仙剑奇侠传二》游戏秘籍

无限冥纸：在丰都城，点击特定的小猫，它会给你五张冥纸，再次点击还会再给五张，可循环获取。无限使用虎煞技能：学会 “虎啸风声” 技能后，将虎煞之力值设置为 16，在战斗中持续使用该技能…...

编程日记 2025/6/29 12:13:42

AWS 中国区 CloudFront SSL 证书到期更换实战指南

适用场景: AWS 中国区（宁夏区域 cn-northwest-1 或北京区域 cn-north-1）CloudFront 分配的 SSL 证书到期后无缝替换，域名主体为 domain.cn。背景与痛点当 CloudFront 使用的 SSL 证书即将到期时，需手动替换新证书以避免服务中断。由于 AWS 中国区不支持 ACM 证书，必须…...

编程日记 2025/6/29 9:19:06

【2025A卷】华为OD机试九日集训第3期 - 按算法分类，由易到难，提升编程能力和解题技巧，从而提高机试通过率（Python/JS/C/C++）

目录一、适合人群二、本期训练时间三、如何参加四、数据结构与算法大纲五、华为OD九日集训第3期第1天、逻辑分析第2天、逻辑分析第3天、双指针第4天、双指针第5天、数据结构map第6天、栈第7天、二叉树第8天、贪心算法第9天、二分查找六、集训总结国内直接使用最新o3、o4-mini…...

编程日记 2025/6/29 10:01:32

MacOS上如何运行内网穿透详细教程

本文以市面常见、好用的内网穿透为例，一款为开源内网穿透工具Frp;另一款为国产新锐软件ZeroNews。一、Frp（开源工作、使用自由） 1. 下载 FRP 访问 FRP 的 GitHub 发布页： https://github.com/fatedier/frp/releases 选择适合 …...

编程日记 2025/6/29 12:16:57

第55讲：农业人工智能的跨学科融合与社会影响——构建更加可持续、包容的农业社会

目录一、农业人工智能的多维融合：科技与社会的桥梁 1. 技术与社会：解决现代农业中的不平等 2. AI与伦理：塑造道德规范与社会责任 3. AI与政策：推动农业政策的科学决策与智能执行二、AI与农业未来社会的构建：更绿色、更智能、更包容 1. 推动农业可持续发展：绿色农…...

编程日记 2025/6/29 10:28:36

JVM性能优化之老年代参数设置

一、引言咱们书接上回，上篇文章主要讲解了年轻代参数设置，如果对这一部分还不清楚的建议先去看一下（年轻代参数设置），本文主要为大家介绍老年代参数的设置，掌握好jvm参数的设置是一个高级开发人人员必备的…...

编程日记 2025/6/29 9:54:14

在 Ubuntu 环境为 Elasticsearch 引入 `icu_tokenizer

1. 为什么需要 ICU 分析插件 Elasticsearch 默认的 standard tokenizer 遵循 UAX #29 规则，但在 CJK（中、日、韩）等亚洲语言上仅能按字符切分，无法识别词边界；对包含重音符号、大小写或多脚本混排的文本也缺乏统一归一…...

编程日记 2025/6/29 9:41:20

JMeter 安装及使用 [软件测试工具]

目录 JMeter 1. JMeter 安装 1.1 点击官网下载: JMeter官网下载 1.2 下载后解压即可 1.3 打开 JMeter 1.3.1 方式一: 点击对应程序打开 1.3.2 方式二: 命令行启动 1.4 关闭 JMeter 2. JMeter 基础配置 2.1 修改字体为简体中文 2.2 添加拓展插件 2.2.1 下载其他监听器…...

编程日记 2025/6/29 9:18:09

Unity 资源合理性检测

一：表格过度配置，表格资源是否在工程中存在，并输出不存在的资源 import pandas as pd import glob import osassets [] count 0# 遍历configs文件夹下所有xlsx文件 for file_path in glob.glob(configs/*.xlsx):count 1try:sheets pd.re…...

编程日记 2025/6/29 11:09:47

vue-study（1）

黑马智数项目黑马智数是一个数字化园区管理项目，该项目后台可以在线管理园区内的楼宇、企业、车辆和一体杆等资源，可视化大屏通过园区3D模型实时展示园区概况。通过该项目能学到如何用qiankun搭建微前端架构、用Echarts进行数据可视化、以及前沿的3D模…...

编程日记 2025/6/29 12:12:49

XS5032：高性能3DNR+HDR ISP-TX 2K芯片

爱芯元智 XS5032：高性能3DNRHDR ISP-TX 2K芯片视频输入支持MIPI接口，4lane，Max.1.5Gbps/lane 支持Sensor并口（DVP） 视频分辨率支持多种同轴高清制式和标清制式，包括： 960H25/30fps&…...

编程日记 2025/6/29 12:11:38

[原创](现代Delphi 12指南):[macOS 64bit App开发]：如何使用NSString类型字符串?

[作者] 常用网名: 猪头三出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站编程生涯: 2001年~至今[共24年] 职业生涯: 22年开发语言: C/C++、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、开发工具: Visual Studio、Delphi、XCode、…...

编程日记 2025/6/29 12:04:56