数据结构—栈和队列

目录

1.栈底层结构的选择

2.栈的实现

3.栈

3.1入栈

3.2出栈

3.3栈顶删除

4.队列

4.1队列介绍

4.2队列初始化

4.3入队列

4.4队头删除



1.栈底层结构的选择

栈是一种数据结构

具有“后进先出的”的特点

现在面临的两种选择,一种是顺序表,另一种是链表。选择顺序表应该是优于链表的,链表的出栈和入栈时过于复杂,可以选用顺序表,仅需改变数组的下标即可实现。

2.栈的实现

栈首先要有栈顶,容量,和数据。

存入栈的数据只能出栈顶的数据,不能修改栈底的数据以及其他的数据,栈顶我们用top来表示,顺序表是arr,capacity来表示栈的容量大小。

typedef struct Stack
{STDataType*arr;int top;int capacity;
};

这样栈的结构实现好了,接着实现栈的功能。

3.栈

3.1入栈

入栈之前我们要确保栈还有多余的空间可以留给新的数据,所以要对栈进行检查容量大小。

if (ps->top == ps->capacity)
{int tmp = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* p = (STDataType*)realloc(ps->arr, sizeof(STDataType) * tmp);if (p == NULL){perror("realloc Fail");exit(1);}else{ps->arr = p;ps->capacity = tmp;}
}

如果top和capacity相等的话,就要进行扩容。

3.2出栈

STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

 值得注意的是出栈之情要检查是否为空指针,是否为空栈。

3.3栈顶删除

栈顶删除就是将top减一即可,这里不做过多解释。

void STPop(ST* ps)
{assert(!StackEmpty(ps));assert(ps);ps->top--;}

4.队列

4.1队列介绍

队列是使用链表实现的,包含队头队尾,队列节点等。

4.2队列初始化

void QueueInit(Queue* pq)
{pq->phead = pq->ptail = NULL;pq->size = 0;
}

4.3入队列

void QueuePush(Queue* pq, QDataType x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc faild");exit(1);}else{newnode->data = x;newnode->next = NULL;}assert(pq);if (pq->phead ==NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

入队列需要先创建一个队列节点,然后将需要插入的数据x赋给新节点。

值得注意的是要先确定pq和pq是非空的。

4.4队头删除

void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}pq->size--;}

如果对头和队尾相等,此时是只有一个节点,直接将头节点释放就行,然后将头尾节点置为空指针。

如果头尾不相等,那先创建一个临时指针保存phead,然后释放头节点,最后将头节点置为tmp即可,最后要将size--,这样一个删除的接口就实现好了。

队列主要的难实现的函数就是这些,其他的简单的这里就不解释了。

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

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

相关文章

安装paddle

网址:飞桨PaddlePaddle-源于产业实践的开源深度学习平台 或者找对应python和cuda版本的paddle下载后安装: https://www.paddlepaddle.org.cn/whl/linux/mkl/avx/stable.html 你想要安装paddlepaddle - gpu2.6.1.post112版本。在你提供的文件列表中&am…

【解决】Layout 下创建槽位后,执行 Image 同步槽位位置后表现错误的问题。

开发平台:Unity 6.0 编程语言:CSharp 编程平台:Visual Studio 2022   一、问题背景 | 开发库存系统 图1 位置同步失败问题 图2 位置正常同步效果表现 黑框 作用于 UnityEngine.UI.GridLayoutGruop,形成 4x6 布局,如…

电商系统开发:Spring Boot框架实战

3 系统分析 当用户确定开发一款程序时,是需要遵循下面的顺序进行工作,概括为:系统分析–>系统设计–>系统开发–>系统测试,无论这个过程是否有变更或者迭代,都是按照这样的顺序开展工作的。系统分析就是分析系…

深度神经网络DNN反向传播BP算法公式推导

深度神经网络DNN反向传播BP算法推导、δ法则 文章目录 前言一、单个神经元的内部结构二、前向传播三、反向传播总结 前言 \;\;\;\;\; 本文详细推导深度神经网络DNN反向传播BP算法中对权重w和偏置b的更新公式。通过图片和一步步的数学公式推导深刻理解反向传播BP算法&#xff0c…

借助Excel实现Word表格快速排序

实例需求:Word中的表格如下图所示,为了强化记忆,希望能够将表格内容随机排序,表格第一列仍然按照顺序编号,即编号不跟随表格行内容调整。 乱序之后的效果如下图所示(每次运行代码的结果都不一定相同&#x…

HarmonyOS 开发环境搭建

HarmonyOS(鸿蒙操作系统)作为一种面向全场景多设备的智能操作系统,正逐渐在市场上崭露头角。为了进入HarmonyOS生态,开发者需要搭建一个高效的开发环境。本文将详细介绍如何搭建HarmonyOS开发环境,特别是如何安装和配置…

Fish Agent V0.13B:Fish Audio的语音处理新突破,AI语音助手的未来已来!

近日,Fish Audio公司发布了一款全新的语音处理模型——Fish Agent V0.13B,这款模型以其高效、精确的语音生成和处理能力,尤其是在模拟或克隆不同声音方面的表现,引起了广泛关注。这不仅意味着我们在拥有一个声音自然、反应迅速的A…

Shell基础2

声明! 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下,如涉及侵权马上删除文章,笔记只是方便各位师傅的学习和探讨,文章所提到的网站以及内容,只做学习交流,其他均与本人以及泷羽sec团…

系统架构师考试18天极限备考复盘(2024年11月)

前言 写下这篇复盘笔记的时候还没有出成绩。泽崽目前是在读研究生,在经过 大概2周多个全日 的极限备考之后,于11月10日参加了软考的系统架构师考试(高级)。目前12月下旬才会出成绩,对于“基础知识-案例分析-论文”的估…

Tessy学习笔记—requirement(需求)的管理

1:什么是需求 Tessy中的requirement(需求)是,我们还是跟着Tessy官方的文档,继续学习,打开官方自带的工程Is Value In Range Requirement.project。 按照官方自带的操作手册,导入txt类型的需求…

web——sqliabs靶场——第六关——报错注入和布尔盲注

这一关还是使用报错注入和布尔盲注 一. 判断是否有sql注入 二. 判断注入的类型 是双引号的注入类型。 3.报错注入的检测 可以使用sql报错注入 4.查看库名 5. 查看表名 6.查看字段名 7. 查具体字段的内容 结束 布尔盲注 结束

Day44 | 动态规划 :状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III

Day44 | 动态规划 :状态机DP 买卖股票的最佳时机IV&&买卖股票的最佳时机III&&309.买卖股票的最佳时机含冷冻期 动态规划应该如何学习?-CSDN博客 本次题解参考自灵神的做法,大家也多多支持灵神的题解 买卖股票的最佳时机【…

FlinkSql读取kafka数据流的方法(scala)

我的scala版本为2.12 <scala.binary.version>2.12</scala.binary.version> 我的Flink版本为1.13.6 <flink.version>1.13.6</flink.version> FlinkSql读取kafka数据流需要如下依赖&#xff1a; <dependency><groupId>org.apache.flink&…

RabbitMQ实战启程:从原理到部署的全方位探索(上)

文章目录 一、RabbitMQ简介1.1、概述1.2、特性 二、RabbitMQ原理架构三、RabbitMQ应用场景3.1 简单模式3.2 工作模式3.3 发布订阅3.4 路由模式3.5 主题订阅模式 四、同类中间件对比五、RabbitMQ部署5.1 单机部署5.1.1 安装erlang5.1.2 安装rabbitmq 5.2 集群部署&#xff08;镜…

动态内存管理(c语言)

我们通常开辟空间的方式 int val 20; //大小为4个字节 char arr[10] {0} //开辟出一块连续的空间且大小为10 但是上面开辟空间方式的特点 1.空间开辟大小是固定的 2.数组在声明得时候&#xff0c;必须指定数组得长度&#xff0c;它所需要得内存在编译时分配 但是以上的方式不能…

【从零开始的LeetCode-算法】3270. 求出数字答案

给你三个 正 整数 num1 &#xff0c;num2 和 num3 。 数字 num1 &#xff0c;num2 和 num3 的数字答案 key 是一个四位数&#xff0c;定义如下&#xff1a; 一开始&#xff0c;如果有数字 少于 四位数&#xff0c;给它补 前导 0 。答案 key 的第 i 个数位&#xff08;1 < …

STM32+AI语音识别智能家居系统

基于 STM32 和 AI 语音识别的智能家居系统的详细硬件和软件设计&#xff0c;包括各个模块的详细描述和代码示例。 一、硬件设计 1. 微控制器&#xff08;STM32&#xff09;&#xff1a; 选择 STM32F7 系列或更高性能的芯片&#xff0c;如 STM32F767ZIT6&#xff0c;以满足处理…

信息收集—JS框架识别泄露提取API接口泄露FUZZ爬虫插件项目

前言 免杀结束了&#xff0c;我们开个新的篇章——信息收集。为什么我一开始先写信息收集的文章呢&#xff0c;是因为现在我才发现我的信息收集能力其实有点弱的&#xff0c;所以呢开始知不足&#xff0c;而后进。 什么是JS JS就是JavaScript的简称&#xff0c;它和Java是没…

智能化护士排班系统的设计与实现(文末附源码)

自动排班-护士(分白班|夜班) 当服务器启动时检测需要自动排班,自动开始排班的算法执行 获得本周的所有日期,例如2023-01-29.....2023-02-04依次对每个科室&#xff0c;从第一天开始,逐天进行排班&#xff0c;分别设置两个二个数组&#xff0c;day[7];night[7]分别记忆一周内每…