时间:2021-05-19
循环队列——队列的顺序表示和实现
前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在:
相同点:
在顺序队列和循环队列中,进行出队、入队操作时,队首、队尾指针都要加 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 6typedef 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 = 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){ 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));}运行截图:
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例为大家分享了C语言实现循环队列的具体代码,供大家参考,具体内容如下注意事项:1、循环队列,是队列的顺序表示和实现。因为是尾进头出,所以和顺序栈不同的是需
Android消息队列模型详解及实例Android系统的消息队列和消息循环都是针对具体线程的,一个线程可以存在(当然也可以不存在)一个消息队列(MessageQ
本文讲的是循环队列,首先我们必须明白下面几个问题循环队列的基础知识1.循环队列需要几个参数来确定循环队列需要2个参数,front和rear2.循环队列各个参数的
数据结构–用C++实现循环顺序队列队列的操作特性:先进先出队列中元素具有相同类型相邻元素具有前驱和后继关系设置队头、队尾两个指针,以改进出队的时间性能约定:队头
复习了下数据结构,用Java的数组实现一下循环队列。队列的类//循环队列classCirQueue{privateintQueueSize;privateint