循环队列详解及队列的顺序表示和实现
循环队列——队列的顺序表示和实现
前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在:
相同点:
在顺序队列和循环队列中,进行出队、入队操作时,队首、队尾指针都要加 1 ,朝前移动。
不同点:
1. 在循环队列中当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结果是指向向量的下界 0 。而在顺序队列中,说明队已满,若此时采用的是动态顺序链,可以增加申请内存.若是采用静态顺序链,只能退出程序.
2. 顺序队列中q.front = q.rear 表示队空,q.rear = MAX_QUEUE_SIZE表示队满.而在循环队列中.front=q.rear表示队空,而无法用.rear=MAX_QUEUE_SIZE表示队满.
判断循环队列队满的两种方法(本文采用第二种方法):
1.另设一个标志位以区分队列是空还是满
2.少用一个元素空间,约定以”队列头指针在队列尾指针的下一位置上”,作为队列呈满状态的标志.
第二种方法的实现:
◆ rear 所指的单元始终为空。
◆ 循环队列为空: front=rear 。
◆ 循环队列满: (rear+1)%MAX_QUEUE_SIZE=front 。
循环队列操作及指针变化情况如下图所示:
循环队列虽然可以解决”假溢出”问题,但是它不能通过动态分配的一维数组来实现,所以在实现循环队列之前,一定要为它设定一个最大队列长度.如果无法预估所需的最大队列长度,只能采用来链表实现.
代码实现:
循环队列和顺序队列的头文件是一样的
/* 循环队列的接口定义头文件 */ #define true 1 #define false 0 /* 队的最大长度 */ #define MAX_QUEUE_SIZE 6 /* 队列的数据类型 */ typedef int datatype; /* 静态链的数据结构 */ typedef struct queue{ datatype sp_queue_array[MAX_QUEUE_SIZE]; /* 队头 */ int front; /* 队尾 */ int rear; }cir_queue; /* 静态顺序链的接口定义 */ /* 静态链的初始化 */ cir_queue queue_init(); /* 判断队列是否为空,若为空 * 返回true * 否则返回false */ int queue_empty(cir_queue q); /* 插入元素e为队q的队尾新元素 * 插入成功返回true * 队满返回false */ int queue_en(cir_queue *q, datatype e); /* 队头元素出队 * 用e返回出队元素,并返回true * 若队空返回false */ int queue_de(cir_queue *q, datatype *e); /* 清空队 */ void queue_clear(cir_queue *q); /* 获得队头元素 * 队列非空,用e返回队头元素,并返回true * 否则返回false */ int get_front(cir_queue, datatype *e ); /* 获得队长 */ int queue_len(cir_queue q); /* 遍历队 */ void queue_traverse(cir_queue q, void(*visit)(cir_queue q)); void visit(cir_queue s); /* 循环队列的接口实现文件 */ #include<stdio.h> #include<stdlib.h> #include"cir_queue.h" cir_queue queue_init() { cir_queue q; q.front = q. rear = 0; return q; } int queue_empty(cir_queue q) { return q.front == q.rear; } int queue_en(cir_queue *q, datatype e) { /* 判断队是否已满 */ if (q -> front == (q -> rear + 1) % MAX_QUEUE_SIZE) return false; /* 入队 */ q -> sp_queue_array[q -> rear] = e; q -> rear = (q -> rear + 1) % MAX_QUEUE_SIZE; return true; } int queue_de(cir_queue *q, datatype *e) { /* 判断队列是否为空 */ if(q -> front == q -> rear) return false; /* 用e返回队头元素 */ *e = q -> sp_queue_array[q -> front]; q -> front = (q -> front + 1 ) % MAX_QUEUE_SIZE; return true; } void queue_clear(cir_queue *q) { q -> front = q -> rear = 0; } int get_front(cir_queue q, datatype *e) { /* 判断队列是否为空 */ if (q.front == q.rear) return false; *e = q.sp_queue_array[q.front]; return true; } int queue_len(cir_queue q) { /* 若front > rear */ if(q.front > q.rear) return (q.rear + MAX_QUEUE_SIZE - q.front); else return (q.rear - q.front); } void queue_traverse(cir_queue q, void(*visit)(cir_queue q)) { visit(q); } void visit(cir_queue q) { while(q.front != q.rear) { printf("%d ",q.sp_queue_array[q.front]); q.front = (q.front + 1) % MAX_QUEUE_SIZE; } } int main() { cir_queue q = queue_init(); queue_en(&q, 1); queue_en(&q, 2); queue_en(&q, 3); queue_en(&q, 4); queue_en(&q, 5); printf("此时队长:length=%d\n", queue_len(q)); queue_traverse(q, visit); printf("元素6再入队\n"); queue_en(&q, 6); queue_traverse(q, visit); datatype *x = (datatype *)malloc(sizeof(*x)); queue_de(&q,x); printf("出队:%d,此时队长=%d\n", *x, queue_len(q)); printf("元素6再入队\n"); queue_en(&q, 6); printf("length=%d\n", queue_len(q)); queue_traverse(q,visit); datatype *e = (datatype *)malloc(sizeof(*e)); queue_de(&q,e); printf("queue_de(),e=%d length=%d\n", *e, queue_len(q)); queue_traverse(q, visit); queue_clear(&q); queue_traverse(q, visit); printf("length:%d\n", queue_len(q)); }
运行截图:
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
- 队列的特性很简答,就是先进先出,一般利用数组来实现,本文就介绍了C#队列的简单使用,文中根据实例编码详细介绍的十分详尽,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-17
- 这篇文章主要介绍了SpringBoot集成Redis实现消息队列的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-10
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
C#使用RabbitMq队列(Sample,Work,Fanout,Direct等模式的简单使用)
这篇文章主要介绍了C#使用RabbitMq队列(Sample,Work,Fanout,Direct等模式的简单使用),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-12-08- 这篇文章主要介绍了Nodejs 数组的队列以及forEach的应用详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-25
asp.net通过消息队列处理高并发请求(以抢小米手机为例)
这篇文章主要介绍了asp.net通过消息队列处理高并发请求(以抢小米手机为例),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-09-22- 这篇文章主要介绍了C#队列Queue用法,实例分析了队列的功能、定义及相关使用技巧,需要的朋友可以参考下...2020-06-25
- 本篇文章小编为大家介绍,基于条件变量的消息队列 说明介绍。需要的朋友参考一下...2020-04-25
- 这篇文章主要介绍了c语言尾队列tailq使用示例,大家参考使用吧...2020-04-25
- 这篇文章主要介绍了C++循环队列实现模型,较为详细的分析了循环队列算法的原理与实现方法,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 本篇文章是对消息队列的应用进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C#队列Queue多线程用法,实例分析了队列的相关使用技巧,需要的朋友可以参考下...2020-06-25
- 在生活中很多时候都会用到延迟队列,本文基于Redis延迟队列的实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-05-13
- 在本篇文章里小编给大家整理的是一篇关于php双向队列如何理解的相关内容及实例,需要的朋友们可以跟着学习下。...2021-11-05
- 这篇文章主要介绍了C#多线程处理多个队列数据的方法,涉及C#线程与队列的相关操作技巧,需要的朋友可以参考下...2020-06-25
- 队列的特点是节点的排队次序和出队次序按入队时间先后确定,即先入队者先出队,后入队者后出队,这篇文章主要给大家介绍了关于java固定大小队列的几种实现方式,需要的朋友可以参考下...2021-07-15
- 这篇文章主要介绍了基于JavaScript的数据结构队列动画实现示例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-06
- 本篇文章是对C++无锁队列的实现进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C#环形缓冲区(队列)完全实现代码,感兴趣的小伙伴们可以参考一下...2020-06-25
- 其实,单调队列和单调栈是类似的,在我看来,这两个东西只是名字不一样 - - ! 比较容易想的一道题啦! 首先,这题的两个关键点: 1、区间的和。这个简单,地球人都知道! 2、区间的最小值。...2020-04-25