循环队列FIFO原理及C实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了循环队列FIFO原理及C实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5478字，纯文字阅读大概需要8分钟。

内容图文

循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

技术分享图片

入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。

定义一个循环队列结构：

            #define FIFO_HEAD(name, type)                                                        struct name {                                                                        struct type *fifo;                                                        int front, tail, capacity;                                        }

front表示首元素索引

struct type *fifo表示该队列中的元素指针，可以指向任意结构体指针

tail表示最后一个元素索引

capacity表示队列的长度

循环队列初始化：

分配一个连续的空间存储队列元素。

技术分享图片

            #define FIFO_INIT(head, _capacity) do {                                        \
        (head)->fifo = malloc(sizeof(*(head)->fifo) * _capacity);                (head)->front = (head)->tail = -1;                                        (head)->capacity = _capacity;                                        } while (0)

循环队列销毁：

            #define FIFO_EXIT(head) do {                                                \
        (head)->front = (head)->tail = -1;                                        (head)->capacity = 0;                                                        if ((head)->fifo)                                                                free((head)->fifo);                                        } while (0)

队列空判断：

            #define FIFO_EMPTY(head)    ((head)->front == -1)

①队列初始化时，队列是空的，会让front为-1

②出队列时，font++, 当font追上tail表示空了，则可以重新设置起始点，令front = tail = -1

综合①②所以可以用-1判断

队列满判断：

            #define FIFO_FULL(head)     (((head)->front == ((head)->tail + 1)%(head)->capacity))

①当front=0时，那么tail到达capacity-1表示FIFO full.

技术分享图片

②否则，tail追上front后(front = tail + 1)表示FIFO full.

技术分享图片

入队列：

入队列就是尾元素的索引++，也就是tail++，让新元素放进队列的尾部。

            #define FIFO_PUSH(head, elm) do {                                                if (FIFO_EMPTY(head))                                                                (head)->front = (head)->tail = 0;                                else                                                                                (head)->tail = ((head)->tail == (head)->capacity - 1)                                ? 0 : (head)->tail + 1;                                (head)->fifo[(head)->tail] = elm;                                } while (0)

如果队列是空的，则第一个元素入队列，front和tail索引都指向第一个元素，front = tail = 0;

技术分享图片

其他情况入队，让tail++

技术分享图片

出队列：

出队列就是让font对应的元素丢出去，font++。

            #define FIFO_POP(head, pelm) do {                                                *(pelm) = (head)->fifo[(head)->front];                                        if ((head)->front == (head)->tail)                                                (head)->front = (head)->tail = -1;                                else                                                                                (head)->front = ((head)->front == (head)->capacity - 1)                                ? 0 : (head)->front + 1;                } while (0)

当front追上tail后，表示队列空了，重新设置起始点，需要将front = tail = -1

技术分享图片

其他情况出队，丢出front元素，让front++

技术分享图片

队列总元素个数：

            #define FIFO_CAPACITY(head) ((head)->capacity)

队列有效元素个数：

            #define FIFO_SIZE(head)     (FIFO_EMPTY(head) ?         0 : ((((head)->tail + (head)->capacity - (head)->front) % (head)->capacity) + 1))

用tail - front就表示有效元素个数，不过由于循环FIFO,可能tail<front,这个时候就需要取余运算，如下图。

技术分享图片

循环队列遍历：

            #define FIFO_FOREACH(var, head, idx)                                                for (idx = (head)->front;                                idx < (head)->front + FIFO_SIZE(head);                                        var = (head)->fifo[idx++ % (head)->capacity])

获取队列尾元素：

            #define FIFO_GET_TAIL(head, pelm) (*(pelm) = (head)->fifo[(head)->tail])

获取队列头元素：

            #define FIFO_GET_FRONT(head, pelm) (*(pelm) = (head)->fifo[(head)->front])

测试：

#include "fifo.h"
#include <stdio.h>

struct person{
        int age;
        int id;
        char name[20];
};
 
FIFO_HEAD(person_q, person*);
/*
        struct person_q {                                                                        struct person* *fifo;                                                        int front, tail, capacity;                                        }
*/struct person_q person1_queue;
struct person_q person2_queue;

int main(void)
{
        FIFO_INIT(&person1_queue, 1);
        FIFO_INIT(&person2_queue, 5);

        if (FIFO_CAPACITY(&person1_queue) != 1) {
                printf( "FIFO_CAPACITY 1 NG.\n");
                return -1;
        }

        if (FIFO_CAPACITY(&person2_queue) != 5) {
                printf( "FIFO_CAPACITY 2 NG.\n");
                return -1;
        }
 
        if (FIFO_SIZE(&person1_queue) != 0) {
                printf( "FIFO_SIZE 1 NG.\n");
                return -1;
        }
 
        if (FIFO_SIZE(&person2_queue) != 0) {
                printf( "FIFO_SIZE 2 NG.\n");
                return -1;
        }

        if (!FIFO_EMPTY(&person1_queue)) {
                printf( "FIFO_EMPTY 1 NG.\n");
                return -1;
        }
 
        if (!FIFO_EMPTY(&person2_queue)) {
                printf( "FIFO_EMPTY 2 NG.\n");
                return -1;
        }
 
        struct person *person_a = malloc(sizeof(*person_a));
        person_a->age = 20;
        person_a->id = 1001;
        FIFO_PUSH(&person1_queue, person_a);//把person_a这个结构体指针元素丢进FIFO,
        //后面对它pop出来又能拿到它，所以不用担心地址弄丢导致无法释放.if (!FIFO_FULL(&person1_queue)) {
                printf( "FIFO_FULL 1 NG.\n");
                return -1;
        }
 
        person_a = malloc(sizeof(*person_a));
        person_a->age = 30;
        person_a->id = 1002;
        FIFO_PUSH(&person2_queue, person_a);

        if (FIFO_FULL(&person2_queue)) {
                printf( "FIFO_FULL 2 NG.\n");
                return -1;
        }

        if (FIFO_SIZE(&person1_queue) != 1) {
                printf( "FIFO_SIZE 3 NG.\n");
                return -1;
        }

        if (FIFO_SIZE(&person2_queue) != 1) {
                printf( "FIFO_SIZE 4 NG.\n");
                return -1;
        }

        FIFO_POP(&person1_queue, &person_a);
        if (person_a->age != 20) {
                printf( "FIFO_POP content NG.\n");
                return -1;
        }
        free(person_a);

        if (FIFO_SIZE(&person1_queue) != 0) {
                printf( "FIFO_SIZE 5 NG.\n");
                return -1;
        }
 
        person_a = malloc(sizeof(*person_a));
        person_a->age = 40;
        person_a->id = 1003;
        FIFO_PUSH(&person2_queue, person_a);

        FIFO_GET_FRONT(&person2_queue, &person_a);
        if (person_a->age != 30) {
                printf( "FIFO_GET_FRONT NG.\n");
                return -1;
        }
 
        FIFO_GET_TAIL(&person2_queue, &person_a);
        if (person_a->age != 40) {
                printf( "FIFO_GET_TAIL NG.\n");
                return -1;
        }
 
        FIFO_POP(&person2_queue, &person_a);
        if (person_a->age != 30) {
                printf( "FIFO_POP content NG.\n");
                return -1;
        }
        free(person_a);

        if (FIFO_SIZE(&person2_queue) != 1) {
                printf( "FIFO_SIZE 6 NG.\n");
                return -1;
        }

        FIFO_POP(&person2_queue, &person_a);
        if (person_a->age != 40) {
                printf( "FIFO_POP content NG.\n");
                return -1;
        }
        free(person_a);
 
        if (FIFO_SIZE(&person2_queue) != 0) {
                printf( "FIFO_SIZE 7 NG.\n");
                return -1;
        }
 
        struct person *person_arr[5];
        int i=0;

        while (!FIFO_FULL(&person2_queue))
        {
                person_arr[i] = malloc(sizeof(*person_arr[0]));
                person_arr[i]->age = i;
                person_arr[i]->id = 1000 + i;
                FIFO_PUSH(&person2_queue, person_arr[i]);
                i++;
        }

        while (!FIFO_EMPTY(&person2_queue))
        {
                FIFO_POP(&person2_queue, &person_a);
                printf( "age:%d, id:%d.\n", person_a->age, person_a->id);
                free(person_a);
        }

        FIFO_EXIT(&person1_queue);
        FIFO_EXIT(&person2_queue);
        return0;
}

View Code

技术分享图片

原文：https://www.cnblogs.com/fuzidage/p/15163399.html

内容总结

以上是互联网集市为您收集整理的循环队列FIFO原理及C实现全部内容，希望文章能够帮你解决循环队列FIFO原理及C实现所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1244027.html

来源：【匿名】

【上一篇】GDB常用命令【下一篇】关于IE的RegExp.exec的问题

更多 ►

【循环队列FIFO原理及C实现】教程文章相关的互联网学习教程文章

循环队列FIFO原理及C实现【代码】【图】

循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。定义一个循环队列结构：#define FIFO_HEAD(name, type) struct name { struct type *fifo; ...

语法：while(循环条件){//循环操作}就是在什么条件成立时不断地做什么事情。例子：循环输出一百次好好学习；int i=1;while(i<=100){System.out.println("第"+i+“次输出：好好学习”);i++;}上面这个i++，就是1到100循环中i变化的规律，每次加1；例子2:public class ShiYan { 　　public static void main(String[] args){ 　　　　Scanner input=new Scanner(System.in); 　　　　　　String am; 　　　　　　System.out.prin...

循环结构实验报告【代码】【图】

C程序设计实验报告实验项目： 5.3.1习2 5.3.2习2 5.3.3 5.3.4 5.3.5习1 5.3.5习2 5.3.5习3 姓名：李宏远实验地点：1教524 实验时间：2021.5.6 一、实验目的与要求 (1)熟练掌握使用while. d-.while 及for语句实现循环的方法。 (2)了解3种循环语句的区别和转换、各自的适应性、循环嵌套的使用。 (3)掌握在循环语句中使用break和continue语句改变程序流程的方法。 (4)能在程序设计中用循环的方法实现各种算法。二、实验内容...

VB的判断语句和循环语句

判断语句?If语句if语句共有4种写法: 第一种语法: If 条件判断语句 then 程序代码第二种语法:If 条件判断语句 then 程序代码 else 程式代码第三种语法: If 条件判断语句 then 程式代码 Else 程式代码 End if 第四种语法 If 条件判断语句 then ...

day10-选择结构、循环结构（while循环、do...while循环）【图】

选择结构 if单选择结构我们很多时候需要去判断一个东西是否可行，然后我们才去执行，这样一个过程在程序中用if语句来表示。语法 if (布尔表达式){ //如果布尔表达式为true将执行的语句 }if双选择结构那现在有个需求，公司要收购一个软件，成功了，给人支付100万元；失败了，自己找人开发。这样的需求用一个if就搞不定了，我们需要有两个判断，需要一个双选择结构，所以就有了if-else结构。语法 if(布尔表达式){ ...

循环题目【代码】

1.下面代码的执行结果为（） #include <stdio.h> int main() {int i = 0;for (i = 0; i < 10; i++) {if (i = 5)printf("%d,", i);}return 0; } A.1,2,3,4,5,6,7,8,9,10B.5,5,5,5,5,5,5,5,5,5C.死循环的打印5D.0,1,2,3,4,5,6,7,8,9正确答案选：C 解析：if(i=5）是赋值！！！2.关于if语句说法正确的是（）A.if语句后面只能跟一跳语句。B.if语句是一种分支语句，可以实现单分支，也可以实现多分支。C.if语句中0表示假，1表示真。D.els...

for、foreach和MoveNext循环效率粗比较【代码】

今天没事对for循环、foreach循环、MoveNext循环，执行效率进行了对比；粗略测试代码如下： staticvoid Main(string[] args){#region 三种方式循环执行效率测试List<int> intList = new List<int>();for (int i = 0; i < 100000000; i++){intList.Add(i);}#region for循环执行时间测试Stopwatch sw_1 = new Stopwatch();string excuteTime_1;int sum1 = 0;sw_1.Start();for (int i = 0; i < intList.Count; i++){sum1 += intList[i]...

(转)SQL中的循环、for循环、游标【代码】【图】

DECLARE My_Cursor CURSOR --定义游标FOR (SELECT * FROM dbo.MemberAccount) --查出需要的集合放到游标中OPEN My_Cursor; --打开游标FETCH NEXT FROM My_Cursor ; --读取第一行数据WHILE @@FETCH_STATUS = 0 BEGIN --UPDATE dbo.MemberAccount SET UserName = UserName + ‘A‘ WHERE CURRENT OF My_Cursor; --更新 --DELETE FROM dbo.MemberAccount WHERE CURRENT OF My_Cursor; --删除 FETCH NEXT FROM...

Spring源码--debug分析循环依赖--构造器注入【代码】【图】

目的：源码调试构造器注入，看看是怎么报错的。 spring：5.2.3 jdk：1.8 一、准备首先准备两个循环依赖的类：userService和roleServic<bean id="userService" class="com.chris.spring.service.UserServiceImpl"><constructor-arg ref="roleService"/> </bean> <bean id="roleService" class="com.chris.spring.service.RoleService"><constructor-arg ref="userService"/> </bean>二、开始调试因为依赖注入的触发点是容器初始化所...

Node.js回调函数和事件循环机制

1.Node.js回调函数 Node.js 是单进程单线程应用程序，但是因为 V8 引擎提供的异步执行回调接口，通过这些接口可以处理大量的并发，所以性能非常高。所以，node.js是采用异步编程，具体实现就是回调函数。回调函数在完成任务后就会被调用，Node 使用了大量的回调函数，Node 所有 API 都支持回调函数。因此，同步是按顺序执行的，是阻塞的，而异步是非阻塞的，是不需要按顺序的，所以如果需要处理回调函数的参数，我们就需要写在回调...

smarty模板引擎中section循环loop与total的区别【代码】

在smarty模板引擎的section循环中$data=[101,102,103,105,104];section的两个属性total与loop{section foo $data start=1 step=2}　　{$smarty.section.foo.total}--输出2　　{$smarty.section.foo.loop}--输出5 {/section}意即：使用total输出的是循环执行的次数，使用loop输出的是所循环数据的count原文：http://www.cnblogs.com/Bin-x/p/4563627.html

with_items标准循环【代码】

1.为不同用户定义不同组--- - hosts: web2remote_user: roottasks:- user:name: "{{item.name}}"group: "{{item.group}}"password: "{{‘123456‘|password_hash(‘sha512‘)}}"with_items:- {name: "aa", group: "users"}- {name: "bb", group: "mail" }- {name: "cc", group: "wheel"}- {name: "dd", group: "root" }运行# ansible-playbook add.yml 注意item.name 中间是点，组是自己存在的 2.嵌套循环，循环添加多用户--- - ...

斐波那契数组-递归和循环实现

static void Main(string[] args) { Console.WriteLine(getnumfor(100)); Console.ReadKey(); } static long getnum(long index) { if (index==1||index==2) { return 1; } else { return getnum(index - 1) + getnum(index - 2); } } static long getnumfor(...

for循环【图】

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { //语句的分类 //顺序语句 //选择语句 //循环语句 //循环的四要素：初始条件，循环条...

for循环

for循环的语法结构 for循环的执行过程 C201_04_07_for实现自然数求和 for循环的理解 for循环可以理解为一个范围，描述范围需要起点、终点和步长三者来描述，而for循环中的三个部分正好就相对应 C201_04_08_判断完数：判断一个数是否为完数，完数：一个数所有因子(包括1但不包括本身)的和相加等于这个数本身 public class C201_04_08_判断完数 { public static void main(String[] args) { /* 思路：（1）...

首页 / 更多教程 / 循环队列FIFO原理及C实现

循环队列FIFO原理及C实现

内容导读

内容图文

定义一个循环队列结构：

循环队列初始化：

循环队列销毁：

队列空判断：

队列满判断：

入队列：

出队列：

队列总元素个数：

队列有效元素个数：

循环队列遍历：

获取队列头元素：

测试：

内容总结

内容备注

内容手机端

【循环队列FIFO原理及C实现】教程文章相关的互联网学习教程文章

循环队列FIFO原理及C实现【代码】【图】

while循环

循环结构实验报告【代码】【图】

VB的判断语句和循环语句

day10-选择结构、循环结构（while循环、do...while循环）【图】

循环题目【代码】

for、foreach和MoveNext循环效率粗比较【代码】

(转)SQL中的循环、for循环、游标【代码】【图】

Spring源码--debug分析循环依赖--构造器注入【代码】【图】

Node.js回调函数和事件循环机制

smarty模板引擎中section循环loop与total的区别【代码】

with_items标准循环【代码】

斐波那契数组-递归和循环实现

for循环【图】

for循环

循环 - 相关标签

更多教程 - 最新教程

更多教程 - 最热教程