【图文并茂】c++介绍之队列

1.1队列的定义

队列(queue)简称队,它也是一种操作受限的线性表,其限制为仅允许在表的一端进行插入操作,而在表的另一端进行删除操作

一些基础概念:

  • 队尾(rear) :进行插入的一端
  • 队首(front):进行删除的一端
  • 入队(enqueue):插入新元素
  • 出队(dequeue):删除新元素

队列是一种先进先出表(FIFO),而前面介绍过的栈是一种先进后出表。

(一个队列)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传


1.2队列抽象数据类型

如图:

在这里插入图片描述


1.3队列的顺序存储结构及其基本运算

队列中数据元素的逻辑结构呈线性关系,所以队列可以像线性表一样采用顺序存储结构进行存储,即分配一块连续的存储空间来存放队列的元素,并用两个指针来反映队列中元素变化

顺序队:采用顺序存储结构的队列

(1)声明

typedef int ElemType;
#define MaxSiaze 50
typedef struct
{ElemType data[MaxSiaze];int front, rear;	//队头与队尾指针
}SqQueue;

图示:

在这里插入图片描述
Pe-1694079903125)

(2)初始化队列

//初始化队列
void InitQueue(SqQueue*& q)
{q = (SqQueue*)malloc(sizeof(SqQueue));q->front = q->rear = -1;
}

(3)销毁队列

//销毁队列
void DestroyQueue(SqQueue*& q)
{free(q);
}

(4)判断队列是否为空

//判断队列是否为空
bool QueueEmpty(SqQueue*&q)
{return(q->front == q->rear);
}

(5)入队

bool enQueue(SqQueue*& q, ElemType e)
{if (q->rear == MaxSiaze - 1)	//队满上溢出return false;q->rear++;q->data[q->rear] = e;return true;
}

(6)出队

bool deQueue(SqQueue*& q, ElemType& e)
{if (q->front == q->rear)//队空下溢出return false;q->front++;e = q->data[q->front];return true;
}

完整代码:

#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSiaze 50
typedef struct
{ElemType data[MaxSiaze];int front, rear;	//队头与队尾指针
}SqQueue;
//初始化队列
void InitQueue(SqQueue*& q)
{q = (SqQueue*)malloc(sizeof(SqQueue));q->front = q->rear = -1;
}
//销毁队列
void DestroyQueue(SqQueue*& q)
{free(q);
}
//判断队列是否为空
bool QueueEmpty(SqQueue*&q)
{return(q->front == q->rear);
}
bool enQueue(SqQueue*& q, ElemType e)
{if (q->rear == MaxSiaze - 1)	//队满上溢出return false;q->rear++;q->data[q->rear] = e;return true;
}
bool deQueue(SqQueue*& q, ElemType& e)
{if (q->front == q->rear)//队空下溢出return false;q->front++;e = q->data[q->front];return true;
}
int main() {return 0;
}

1.4队列的链式存储结构及其基本运算

链队:采用链式存储结构的队列

对于单链表实现的链队,在这种链队中只允许在单链表的表头进行删除操作和在表尾进行插入操作

链队的基本知识:

  • 队空的条件 q -->rear == NULL(也可以是q -->front == NULL)
  • 队满的条件:不考虑
  • 元素e的进队操作:新建一个结点存放元素e(由p指向它,将结点p插入作为尾结点)
  • 出队操作:取出队首结点的data值并将其删除

(1)声明

typedef int ElemType;
typedef struct qnode
{ElemType data;	//存放元素struct qnode* next;//下一个结点指针
}DataNode;
typedef struct
{DataNode* front; //指向队首结点DataNode* rear; //指向队首结点
}LinkQuNode;

(2)销毁队列

//销毁
void DestroyQueue(LinkQueue *&q)
{DataNode * pre = q->front,*p;	//pre指向队首结点 if(pre!=NULL){p = pre->next;				//p指向结点pre的后继结点 while(p!=NULL)				//p不空循环 {free(pre);				//释放pre结点 pre = p;				//同步后移 p = p->next;}free(pre);}free(q);
} 

(3)判断队列是否为空

bool QueueEmpty(LinkQueue *q)
{return (q-->rear == NULL)
}

(4)进队列

//进队列
void enQueue(LinkQuNode*& q,ElemType e)
{DataNode* p;p = (DataNode*)malloc(sizeof(DataNode));p->data = e;p->next = NULL;if (q->rear == NULL)//若链队为空,则新结点既是队首结点又是队尾结点q->front = q->rear = p;else{q->rear->next = p;	//将结点p链接到队尾,并将rear指向它q->rear = p;}
}

(5)出队列

//出队列
bool deQueue(LinkQuNode*& q, ElemType e)
{DataNode* t;if (q->rear == NULL)	//原来队列已经为空return false;t = q->front;			//指向首结点if (q->front == q->rear)	//原来队列中只有一个数据结点q->front = q->rear = NULL;elseq->front = q->front->next;e = t->data;free(t);return true;
}

完整代码:

#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct qnode
{ElemType data;	//存放元素struct qnode* next;//下一个结点指针
}DataNode;
typedef struct
{DataNode* front; //指向队首结点DataNode* rear; //指向队首结点
}LinkQuNode;//初始化
void InitQueue(LinkQuNode*& q)
{q = (LinkQuNode*)malloc(sizeof(LinkQuNode));q->front = q->rear = NULL;
}
//销毁
void DestroyQueue(LinkQueue *&q)
{DataNode * pre = q->front,*p;	//pre指向队首结点 if(pre!=NULL){p = pre->next;				//p指向结点pre的后继结点 while(p!=NULL)				//p不空循环 {free(pre);				//释放pre结点 pre = p;				//同步后移 p = p->next;}free(pre);}free(q);
} 
//进队列
void enQueue(LinkQuNode*& q,ElemType e)
{DataNode* p;p = (DataNode*)malloc(sizeof(DataNode));p->data = e;p->next = NULL;if (q->rear == NULL)//若链队为空,则新结点既是队首结点又是队尾结点q->front = q->rear = p;else{q->rear->next = p;	//将结点p链接到队尾,并将rear指向它q->rear = p;}
}
//出队列
bool deQueue(LinkQuNode*& q, ElemType e)
{DataNode* t;if (q->rear == NULL)	//原来队列已经为空return false;t = q->front;			//指向首结点if (q->front == q->rear)	//原来队列中只有一个数据结点q->front = q->rear = NULL;elseq->front = q->front->next;e = t->data;free(t);return true;
}
int main()
{return 0;
}

当然了,队列的形式多种多样,比如双端队列,循环队列等等。希望本文对你有所帮助
在这里插入图片描述

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

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

相关文章

CloudQuery X PolarDB:让数据库管理更简单

前言&#xff1a;8 月 15 日&#xff0c;CloudQuery 数据操作管控平台与阿里云 PolarDB 数据库管理软件&#xff0c;完成产品集成认证测试。也在以下功能上完善了用户使用 PolarDB 的体验&#xff0c;使数据库的管理更加安全高效。 支持在 CloudQuery 中创建连接&#xff0c;便…

数据接口工程对接BI可视化大屏(一)

文章目录 第1章 案例概述1.1 案例目标1.2 BI最终效果1.2.1 PC端显示效果1.2.2 移动端显示效果 后记 第1章 案例概述 1.1 案例目标 此项目以常见的手机零售BI场景为例&#xff0c;介绍如何编写数据接口工程对接BI可视化大屏。 如何从当前常见的主流大数据场景中为后台程序推送…

数据结构入门-13-图

文章目录 一、图的概述1.1 图论的作用1.2 图的分类1.2.1 无向图1.2.2 有向图1.2.3 无权图1.2.4 有劝图 1.3 图的基本概念 二、树的基本表示2.1 邻接矩阵2.1.1 邻接矩阵 表示图2.1.2 邻接矩阵的复杂度 2.2 邻接表2.2.1 邻接表的复杂度2.2.2 邻接表By哈希表 三、图的深度优先遍历…

sentinel加密狗使用及规则配置

Sentinel加密狗是一种硬件加密设备&#xff0c;用于保护软件应用程序免受未经授权的访问和复制。它可以提供软件许可管理、访问控制和数据保护等功能。下面是Sentinel加密狗的使用及规则配置的相关介绍。 Sentinel加密狗的使用 插入加密狗&#xff1a;将Sentinel加密狗插入计算…

C51智能小车(循迹、跟随、避障、测速、蓝牙、wifie、4g、语音识别)总结

目录 1.电机模块开发 1.1 让小车动起来 1.2 串口控制小车方向 1.3 如何进行小车PWM调速 1.4 PWM方式实现小车转向 2.循迹小车 2.1 循迹模块使用 2.2 循迹小车原理 2.3 循迹小车核心代码 3.跟随/避障小车 3.1 红外壁障模块分析​编辑 3.2 跟随小车的原理 3.3 跟随小…

Leetcode.174 地下城游戏

题目链接 Leetcode.174 地下城游戏 hard 题目描述 恶魔们抓住了公主并将她关在了地下城 d u n g e o n dungeon dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里&#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公…

【高阶产品策略】设计有效的AB测试

文章目录 1、A/B测试概述2、A/B测试实施过程3、A/B测试中需要注意的地方4、从一个案例中看A/B测试 1、A/B测试概述 2、A/B测试实施过程 3、A/B测试中需要注意的地方 4、从一个案例中看A/B测试

编写中间件以用于 Express 应用程序

概述 中间件函数能够访问请求对象 (req)、响应对象 (res) 以及应用程序的请求/响应循环中的下一个中间件函数。下一个中间件函数通常由名为 next 的变量来表示。 中间件函数可以执行以下任务&#xff1a; 执行任何代码。对请求和响应对象进行更改。结束请求/响应循环。调用堆…

pytorch学习——循环神经网络RNN讲解及其实现

参考书籍&#xff1a;8.6. 循环神经网络的简洁实现 — 动手学深度学习 2.0.0 documentation 参考视频&#xff1a;54 循环神经网络 RNN【动手学深度学习v2】_哔哩哔哩_bilibili 一.介绍 循环神经网络RNN&#xff08;Recurrent Neural Network &#xff09;是一类广泛应用于序列…

stm32之30.DMA

DMA&#xff08;硬件加速方法&#xff09;一般用于帮运比较大的数据&#xff08;如&#xff1a;摄像头数据图像传输&#xff09;&#xff0c;寄存器-》DMA-》RAM 或者 RAM-》DMA-》寄存器提高CPU的工作效率 源码-- #include "myhead.h" #include "adc.h"#…

javaee之黑马乐优商城2

简单分析一下商品分类表的结构 先来说一下分类表与品牌表之间的关系 再来说一下分类表和品牌表与商品表之间的关系 面我们要开始就要创建sql语句了嘛&#xff0c;这里我们分析一下字段 用到的数据库是heima->tb_category这个表 现在去数据库里面创建好这张表 下面我们再去编…

有向图和无向图的表示方式(邻接矩阵,邻接表)

目录 一.邻接矩阵 1.无向图​编辑 2.有向图 补充&#xff1a;网&#xff08;有权图&#xff09;的邻接矩阵表示法 二.邻接表 1.无向图 2.有向图 三.邻接矩阵与邻接表的关系 一.邻接矩阵 1.无向图 &#xff08;1&#xff09;对角线上是每一个顶点与自身之间的关系&…

线性空间和线性变化

目录 考点一、线性空间的基与维数 1、线性空间 2、基底 3、子空间&#xff08;线性子空间&#xff09; ​编辑4、生成子空间 &#xff08;1&#xff09;、v1 n v2 &#xff08;2&#xff09;、v1 v2 5、求和子空间的方法 6、维数定理 7、例题 &#xff08;1&#xf…

HCIA自学笔记01-冲突域

共享式网络&#xff08;用同一根同轴电缆通信&#xff09;中可能会出现信号冲突现象。 如图是一个10BASE5以太网&#xff0c;每个主机都是用同一根同轴电缆来与其它主机进行通信&#xff0c;因此&#xff0c;这里的同轴电缆又被称为共享介质&#xff0c;相应的网络被称为共享介…

MyBatis-Plus学习笔记总结

一、查询 构造器分为QueryWrapper和LambdaQueryWrapper 创建实体类User package com.system.mybatisplus.model;import com.baomidou.mybatisplus.annotation.IdType; import com.baomidou.mybatisplus.annotation.TableField; import com.baomidou.mybatisplus.annotation.…

JDK8的 ConcurrentHashMap 源码分析

目录 1. 导读 2. ConcurrentHashMap 成员变量解读 3. ConcurrentHashMap 初始化 3.1 ConcurrentHashMap 无参构造源码解读 3.2 ConcurrentHashMap 带参构造源码解读 3.3 tableSizeFor 方法作用解读 3.4 ConcurrenthashMap初始化总结 4. ConcurrentHashMap 添加元素方法…

springboot之一:配置文件(内外部配置优先顺序+properties、xml、yaml基础语法+profile动态切换配置、激活方式)

配置的概念&#xff1a; Spring Boot是基于约定的&#xff0c;所以很多配置都有默认值&#xff0c;但如果想使用自己的配置替换默认配置的话&#xff0c;就可以使用application.properties或者application.yml(application.yaml)进行配置。 注意配置文件的命名必须是applicat…

大数据课程K18——Spark的ALS算法与显式矩阵分解

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的ALS算法与显式矩阵分解; ⚪ 掌握Spark的ALS算法原理; 一、ALS算法与显式矩阵分解 1. 概述 我们在实现推荐系统时,当要处理的那些数据是由用户所提供的自身的偏好数据,这些…

设计模式系列-原型模式

一、上篇回顾 上篇创建者模式中&#xff0c;我们主要讲述了创建者的几类实现方案&#xff0c;和创建者模式的应用的场景和特点&#xff0c;创建者模式适合创建复杂的对象&#xff0c;并且这些对象的每 个组成部分的详细创建步骤可以是动态的变化的&#xff0c;但是每个对象的组…

数据可视化、BI和数字孪生软件:用途和特点对比

在现代企业和科技领域&#xff0c;数据起着至关重要的作用。为了更好地管理和理解数据&#xff0c;不同类型的软件工具应运而生&#xff0c;其中包括数据可视化软件、BI&#xff08;Business Intelligence&#xff09;软件和数字孪生软件。虽然它们都涉及数据&#xff0c;但在功…