【数据结构和算法初阶(C语言)】队列实操(概念实现+oj题目栈和队列的双向实现,超级经典!!!)

news/2024/5/26 20:36:58/文章来源:https://blog.csdn.net/m0_71503225/article/details/136651799

1. 队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,

队列具有先进先出 FIFO(First In First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

2.队列结构存在的意义

①公平排队

比如医院或者银行的排号

②BFSL广度优先

3.队列实现的结构选择

数组和链表都可以实现队列,但是链表的头插尾插,头删尾删要方便些,所以首选链表

 单向还是双向:选择单向,双向的优势是方便找前一个1节点,没有这个需求。(找尾不是因为双向,双向循环方便找尾)

是否需要带哨兵位的链表:哨兵位是为了解决二级指针(可以将头尾指针封装为结构体进行传参,这样就可以改变真实的指针了,所以哨兵位可要可不要),尾插少一次判断。

选择单向不循环链表即可实现。

4.队列实现

typedef  int QdataType;typedef struct QListNode
{struct QListNode* next;QdataType data;
}QNode;//将头尾指针封装为一个结构体,解决传递二级指针的问题typedef struct Queue
{QNode* head;QNode* tail;int size;//保存链表的大小
}Queue;

5.队列对数据的处理

5.1队列初始化

void QUeueInit(Queue* pq)//初始化队列
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

5.2队尾入数据

void QueuePush(Queue* pq, QdataType x)//队列增加数据
{assert(pq);//首先传入的这个结构体要存在//申请到节点来创建QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");}//新节点初始化newnode->data = x;newnode->next = NULL;//准备插入,看一下是不是第一次插入if (pq->tail == NULL){pq->head = pq->tail = newnode;pq->size++;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;pq->size++;}
}

5.3队头出数据

void QueuepPop(Queue* pq, QdataType x)//队列删除元素
{assert(pq);assert(pq->size != 0);if (pq->head->next == NULL)//因为不是带哨兵位的,删除到最后一个位置防止尾指针成为野指针,单独处理{free(pq->head);pq->head = pq->tail = NULL;pq->size--;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;pq->size--;}}

5.4获取队列尾部元素

QdataType QueueBack(Queue* pq)//获取队列前后面元素
{assert(pq);assert(!QueueEmpty);return pq->tail->data;
}

5.5获取队列头部元素

QdataType QueueFront(Queue* pq)//获取队列前面元素
{assert(pq);assert(!QueueEmpty);return pq->head->data;
}

5.6获取队列中元素个数

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

5.7检测队列是否为空

bool QueueEmpty(Queue* pq)//检测队列是否为空
{assert(pq);return pq->head == NULL;
}

5.8销毁队列

void QueueDestory(Queue* pq)//销毁队列
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = cur->next;}pq->head = pq->tail = NULL;pq->size = 0;
}

6.循环队列补充

 

7.使用队列实现栈

链接跳转题目:

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/implement-stack-using-queues/

分析:栈的结构特点是数据先进后出

           队列的结构特点是先进先出

 

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

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

相关文章

ChatGPT提问技巧——对抗性提示

ChatGPT提问技巧——对抗性提示 对抗性提示是一种允许模型生成能够抵御某些类型的攻击或偏差的文本的技术。这种技术可用于训练更健壮、更能抵御某些类型的攻击或偏差的模型。 要在 ChatGPT 中使用对抗性提示,应为模型提供一个提示,该提示的设计应使模…

OS-Copilot:实现具有自我完善能力的通用计算机智能体

🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ AI 缩小了人类间的知识和技术差距 论文标题:OS-Copilot: Towards Generalist Computer Agents with Self-Improvement 论文链接:https://arxiv.org/abs/2402.07456 项目主页&a…

Java NIO浅析

NIO(Non-blocking I/O,在Java领域,也称为New I/O),是一种同步非阻塞的I/O模型,也是I/O多路复用的基础,已经被越来越多地应用到大型应用服务器,成为解决高并发与大量连接、I/O处理问题…

从金蝶云星空到钉钉通过接口配置打通数据

从金蝶云星空到钉钉通过接口配置打通数据 对接系统金蝶云星空 金蝶K/3Cloud(金蝶云星空)是移动互联网时代的新型ERP,是基于WEB2.0与云技术的新时代企业管理服务平台。金蝶K/3Cloud围绕着“生态、人人、体验”,旨在帮助企业打造面…

IDEA中配置Tomcat

文章目录 一、创建Web项目二、配置tomcat三、启动Tomcat 一、创建Web项目 1.首先我们要用IDEA创建一个普通的java项目。 2.我创建的项目名称为myTomcat,想要开发web程序,我们还要做一下操作。 首先我们先给项目添加框架支持...,我的 idea 版…

Android Button点击事件

一.Button点击事件 <!-- activity_main.xml --> <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android" xmlns:tools"http://schemas.android.com/tools"…

【Flutter学习笔记】9.6 动画切换组件(AnimatedSwitcher)

参考资料&#xff1a;《Flutter实战第二版》9.6 动画切换组件&#xff08;AnimatedSwitcher&#xff09; 9.6.1 AnimatedSwitcher AnimatedSwitcher 可以同时对其新、旧子元素添加显示、隐藏动画&#xff0c;在需要切换新旧元素的场景广泛使用。也就是说在AnimatedSwitcher的子…

面试题:a.equals(1) a.equals(2) a.equals(3)为true,为什么

1.背景 public static void main(String[] args) throws Exception {Class cache Integer.class.getDeclaredClasses()[0];Field c cache.getDeclaredField("cache");c.setAccessible(true);Integer[] array (Integer[]) c.get(cache);array[130] 1;array[131] …

Xcode 15.3 Archive失败

Xcode 15.3 Archive失败 背景 升级 Xcode 到 15.3&#xff0c;真机运行正常。打包的时候发现 Archive 失败。 提示&#xff1a; Call parameter type does not match function signature! 仔细看报错里是和HandyJSON相关的提示。 解决 起初以为和 Pod 库有关系&#xff0c;…

UE4.27_ParticleSystem(没写完的材料)

UE4.27_ParticleSystem&#xff08;没写完的材料&#xff09; 参考实例&#xff1a; UE4[蓝图]下雪效果及雪的材质的实现

【Java常用API】正则表达式的基础使用

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

牛牛的凑数游戏 --- 题解

目录 牛牛的凑数游戏&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 代码实现&#xff1a; 牛牛的凑数游戏&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 我们可以很容易一个区间是否会存在1&#xff0c;那么我们想如果存在1&#xff0c;且有3个1&…

【分布式websocket】群聊中的各种难点以及解决推拉结合【第16期】

前言 群聊中未读消息如何设计&#xff0c;以及是推消息还是拉去消息如何选择是需要讨论的。推送消息是推送全量消息还是推送信号消息让客户端再去拉取。其中方案如何选型会比较纠结。 首先基本的推拉结合思路是在线用户推送消息。用户离线的话上线去拉取消息。这是简单的推拉结…

接上一篇:分布式调用链追踪系统设计

所以必须得记录父子关系&#xff1a; A---->B 是 B---->C 的父调用 A---->D 是 D---->E 的父调用 A---->D 还是 D---->F 的父调用 如何记录呢&#xff1f;需要给每个调用分配一个ID (称为 SpanID)&#xff0c;并且把这个 ID 传递给子调用&#xff0c; 子…

react native常用插件

react-native-async-storage/async-storage 说明&#xff1a;AsyncStorage 是一个在 react-native 中轻量存储的库&#xff1b;跟 localStorage 类似&#xff0c;API 也几乎一样&#xff1b;存储的时候需要将存储内容转成字符串存储。 react-navigation/material-bottom-tabs …

FRM模型十六:期权策略(期权组合)

文章目录 备兑看涨期权&#xff08;Covered Call&#xff09;保护看跌期权&#xff08;protective put&#xff09;牛市价差套利熊市价差套利写在后面 本文所有代码基于windAPI&#xff0c;复现前先下载客户端并注册账号 备兑看涨期权&#xff08;Covered Call&#xff09; 构…

第 7 场 小白入门赛

第5题 &#xff1a;兽之泪【算法赛】 AC_Code:C #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include<stack> #include<cmath> #include <unordered_set> #include &…

Jmeter扩展---自定义取样器

简介 Jmeter已经内置了各种协议的取样器&#xff0c;已经能满足常用的性能压测需求。且在前面一章Jmeter扩展开发--自定义java取样器-CSDN博客中也有关于Java取样器的扩展开发&#xff0c;不过有时候我们期望能定制自己的取样器和界面。为此&#xff0c;需要对Jmeter做扩展&am…

【方法封装】时间格式化输出,获取请求设备和IP

目录 时间类 1.1 获取当前时间&#xff0c;以特定格式化形式输出 1.2 自定义时间&#xff0c;以特定格式化输出 1.3 获取当前时间&#xff0c;自定义格式化 1.4 自定义时间&#xff0c;自定义格式化 设备类 根据请求头信息&#xff0c;获取用户发起请求的设备 请求IP类 …

Spring状态机简单实现

一、什么是状态机 状态机&#xff0c;又称有限状态自动机&#xff0c;是表示有限个状态以及在这些状态之间的转移和动作等行为的计算模型。状态机的概念其实可以应用的各种领域&#xff0c;包括电子工程、语言学、哲学、生物学、数学和逻辑学等&#xff0c;例如日常生活中的电…