您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

FIFO队列一(原理)

系列文章目录
FIFO队列原理


文章目录

  • 前言
  • 一、队列定义
  • 二、队列分类
    • 2.1、链式队列
    • 2.2、数组队列
  • 三、静态队列必是循环队列
  • 四、队列参数
    • 4.1、front
    • 4.2、rear
    • 4.3、队列初始化
    • 4.4、队列非空
    • 4.5、队列空
  • 五、循环队列伪算法
    • 5.1、循环队列 入队伪算法
    • 5.2、循环队列 出队伪算法
    • 5.3、判断循环队列是否为空
    • 5.4、判断循环队列是否为满


前言

硬件:百问网100ASK_STM32F103_MINI开发板(STM32F103C8T6)
IDE:KEIL 5
按键GPIO口为:PA0
串口为:PA10(USART1_RX)、PA9(USART1_TX)
原理图如下:
在这里插入图片描述


提示:以下是本篇文章正文内容,下面案例可供参考

一、队列定义

是一种可以实现选进先出 的存储结构。重点:它是一种数据结构。类似于人到银行排队办业务,如果银行营业厅只有一个业务窗口,有人来办业务,就要银行排队叫号系统的机器上面打印一个号

,如果只有一个人来办理业务,就直接去窗口办理业务
在这里插入图片描述

如果办理业务的人多,就要取号后到消息区排队

在这里插入图片描述

二、队列分类

2.1、链式队列

用链表实现

2.2、数组队列

用数组实现

三、静态队列必是循环队列

在这里插入图片描述

如上图所示一块内存中,数组用来实现队列,数组元素的下标为 0、1、2、3、4、5,队头 f(front)和队尾 r(rear),刚开始队头在下标为 0 的元素位置,队尾在数组下标为5 的元素位置。如果进行出队操作,先进先出,则从队头 f 开始先出,假如出队到数组下标为 3 的元素位置,此位置变成了队头 f,那么数组下标为 0/1/2 的元素内存被释放。出队后的数组元素内存无法重新入队, 因为入队是从队尾 r 开始,不能从队头 f 之前进行入队,而且数组中入队操作达到数组最大下标后,就无法入队操作,同理出队到数组最大下标,也无法出队操作,数组卡死,所以对 静态队列必须使用 循环队列来提高 数组的 利用 率。
如果要删除元素(出队),f 只能加(往数组最大下标方向增加);如果要增加元素(入队),r 只能加(往数组最大下标方向增加)。 (按照一般数组的方法)。r 指向当前队列的下一个位置。

四、队列参数

4.1、front

队列头相当于银行办业务排队最前面的人

4.2、rear

队列尾 ,相当于银行办业务排队最后面的人

4.3、队列初始化

front和rear的值都是0

4.4、队列非空

front 代表的是队列的第一个元素,rear 代表的是队列的最后一个有效元素的下一个元素

4.5、队列空

front 和 rear 的值相等,但不一定是零

五、循环队列伪算法

5.1、循环队列 入队伪算法

1、 入队前要先判断 r 的位置,因为 r 有可能正指向数组最后一个元素,r 再加 1 就越界了。
2、 如何知道 r 是否快越界了,r+1 后对整个数组长度求余数(%),余数为 0,则 r+1 处于最后一个数组元素位置,即将越界。
两步完成:
第1步.将值存入 r 所代表的位置
第2步.错误的写法:r=r+1;
正确写法是:r=(r+1)%数组的长度

5.2、循环队列 出队伪算法

同入队的伪算法一样:f=(f+1)%数组的长度

5.3、判断循环队列是否为空

如果 front 于 rear 的值相等,则该队列就一定为空。

5.4、判断循环队列是否为满

已知: front 的值和 rear 的值没有规律,即可以大(3>1),小(0<4),等(f=r)。刚开始 f=r 一定为空,那么之后经过一个循环后 r 又等于 f 了,但此时 r=f 为满, 即不能通过 过 r=f 这个条件 来判断 其 既是空又是满。所以必须通过 f 和 r 的其他关系来判断其为满。
那么问题:若 f、r 相等,不知道队列到底是空还是满?
两种方式:
1.多增加一个标志参数(但每次对队列进行操作这个标志参数都要更新,浪费系统资源)
2. 少用一个元素 【通常使用第二种方式】
如何判断队列已满:如果 f和 和 r 的值紧挨着,则队列已满, ,n-1 个元素可以被使用。
用 C 语言伪算法表示就是:
if( ( (r+1 )% 数组长度==f )
已满
else
不满


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进