当前位置: 首页 > article >正文

数据结构的概念大合集04(队列)

概念大合集04

  • 1、队列
    • 1.1 队列的定义
    • 1.2队列的顺序存储
      • 1.2.1 顺序队
      • 1.2.2 顺序队的基本运算的基本思想
      • 1.2.3 顺序队的4要素的基本思想
    • 1.3 环形队列
      • 1.3.1 环形队列的定义
      • 1.3.1 环形队列的实现
    • 1.4 队列的链式存储
      • 1.4.1 链队
      • 1.4.2 链队的实现方式
      • 1.4.3 链队的4要素的基本思想
    • 1.5 双端队列

1、队列

1.1 队列的定义

  • 队列限制为仅允许在表的一旦进行插入操作,而在表的另一端进行删除操作。
  • 将进行插入的一端称为队尾,进行删除的一端称为队头或对首。
  • 将插入新元素称为入队或进对。
  • 将删除元素称为出队或离队。

队列的特点是:先进队的先出队,即先进先出表(first in first out,FIFO)

1.2队列的顺序存储

1.2.1 顺序队

采用顺序存储的列表称为顺序队
请添加图片描述

1.2.2 顺序队的基本运算的基本思想

函数名函数作用
InitQueue(&q)初识化队列,构造一个空队列
DestroyQueue(&q)销毁队列,释放为队列q分配的内存空间
QueueEmpty(q)判断队列是否为空表,若L为空队列,则返回true,否则返回false
enQueue(&q,e)进队列,将元素e插入作为对尾元素。
deQueue(&q,e)出队列,从队列q中出队一个元素,并将其赋值给e

1.2.3 顺序队的4要素的基本思想

请添加图片描述

  • 空队:q -> front == q -> rear;
  • 队满:q -> rear == MaxSize - 1;
  • 进队:先将rear增1,然后将元素e放在data数组的rear位置。即data[++rear] = e;
  • 出队:先将front增1,然后取出data数组中front位置的元素。即e = data[++front];

1.3 环形队列

1.3.1 环形队列的定义

       环形队是顺序队的衍生。

       衍生原因,由上面的基本思想可知,队满的情况是q -> rear == MaxSize - 1,而队列的出队,是从队头出队,当出队两次后,队列空出两个元素,但是这时候,仍旧是q -> rear == MaxSize - 1,所以会出现假队队满的情况。为避免这种情况,于是就衍生出环形队列,这种特殊的队列。

       所以将顺序队的前后端连接起来就形成了环形队列

1.3.1 环形队列的实现

环形队列相连后,当队尾指针rear = MaxSize - 1后,再前进一个位置到0,让 rear == 0,即从队尾变成队头,为此,可采用求余(%)运算来实现:
队尾指针rear从队尾指向队头,形成循环:rear = (rear + 1)%MaxSize
同理:队头指针front循环增1:front = (front + 1)%MaxSize

1.4 队列的链式存储

1.4.1 链队

采用链式存储结构的队列
采用单链表的方式实现链队

1.4.2 链队的实现方式

链队的实现方式与链表不同,链队的头结点,存放两个指针,一个指向队首结点,一个指向队尾结点,而里面的数据结点还是与单链表相同,存在一个数据域和一个指针域
请添加图片描述

1.4.3 链队的4要素的基本思想

  • 队空:q->rear == NULL || q->front == NULL;
  • 队满:不考虑
  • 进队:新建一个结点存放元素,将其作为尾结点插入
  • 出队:取出队首结点的data值,并将其删除

1.5 双端队列

指的是两端都可以进行进队和出队的操作的队列
请添加图片描述
进队时,从前端进的元素排列在从后端进的元素的前面;
出队时,无论是从前端出还是从后端出,都是先出的元素排列在后出的元素前面。

注:
本文将主要探讨队列的概念,其中提及的各个函数操作已经发布,欢迎朋友们继续观看。

本篇文章的相关算法
数据结构大合集04——队的相关函数运算算法

上一篇文章
数据结构的概念大合集03(栈)

下一篇文章
数据结构的概念大合集05(串)


http://www.kler.cn/a/271583.html

相关文章:

  • 大数据相关职位 职业进阶路径
  • 详解u3d之AssetBundle
  • ESP32-CAM实验集(WebServer)
  • VLLM性能调优
  • 元素的显示与隐藏
  • 获取snmp oid的小方法1(随手记)
  • 学习vue3第五节(reactive 及其相关)
  • 裁员潮下,打工人的自我修养
  • 微信小程序一次性订阅requestSubscribeMessage授权和操作详解
  • MyBatis中 #{} 和 ${} 区别
  • Python实战:NumPy数组与矩阵操作入门
  • 提高安全投资回报:威胁建模和OPEN FAIR™风险分析
  • 数据类型【mysql数据库】
  • 数据可视化-ECharts Html项目实战(2)
  • 【Python循环3/5】条件循环语句
  • SeAndroid 安全策略机制
  • 基于单片机的智能小车泊车系统设计
  • Prompt Engineering(提示工程)
  • Rust的async和await支持多线程运行吗?
  • Unity Timeline学习笔记(2) - PlayableTrack
  • python二级备考(3)-综合应用
  • 【设计模式】Java 设计模式之组合模式(Composite)
  • 爱奇艺 CTR 场景下的 GPU 推理性能优化
  • 什么是http?
  • 【JAVA】JAVA方法的学习和创造
  • 后端系统开发之——创建SpringBoot工程