环形队列实现原理 链式实现

《环形队列实现原理 链式实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、环形队列实现原理/链式实现环形队列是在实际编程极为有用的数据结构,它有如下特点。  它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。  因为有简单高效的原因，甚至在硬件都实现了环形队列.   环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列. 一.环形队列实现原理-------------------------------------------------

2、-----------  内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。  因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。  为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。   环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时

3、，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.   如何判断环形队列为空，为满有两种判断方法。  1.是附加一个标志位tag     当head赶上tail，队列空，则令tag=0,     当tail赶上head，队列满，则令tag=1,2.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。      队列空：  head==tail     队列满：  (tail+1)%MAXN==head 二.附加标志实现算法采用第一个环形队列有如下结构typedefstruc

4、tringq{  inthead;/*头部，出队列方向*/  inttail;/*尾部，入队列方向*/  inttag;  intsize;/*队列总尺寸*/  intspace[RINGQ_MAX];/*队列空间*/ }RINGQ;初始化状态: q->head=q->tail=q->tag=0;队列为空:(q->head==q->tail)&&(q->tag==0)队列为满:((q->head==q->tail)&&(q->tag==1))入队操作:如队列不满，则写入    q->tail= (q->t

5、ail+1)%q->size;出队操作：如果队列不空，则从head处读出。   下一个可读的位置在 q->head= (q->head+1)%q->size 完整代码   头文件ringq.h#ifndef__RINGQ_H__#define__RINGQ_H__#ifdef__cplusplusextern"C"{#endif#defineQUEUE_MAX20typedefstructringq{inthead;/*头部，出队列方向*/inttail;/*尾部，入队列方向*/inttag;/*为空还是

6、为满的标志位*/intsize;/*队列总尺寸*/intspace[QUEUE_MAX];/*队列空间*/}RINGQ;/*第一种设计方法:当head==tail时，tag=0为空，等于=1为满。*/externintringq_init(RINGQ*p_queue);externintringq_free(RINGQ*p_queue);/*加入数据到队列*/externintringq_push(RINGQ*p_queue,intdata);/*从队列取数据*/externintringq_poll(R

7、INGQ*p_queue,int*p_data);#defineringq_is_empty(q)((q->head==q->tail)&&(q->tag==0))#defineringq_is_full(q)((q->head==q->tail)&&(q->tag==1))#defineprint_ringq(q)printf("ringhead%d,tail%d,tag%d",q->head,q->tail,q->tag);#ifdef__cplusplus}#endif#endif/*__RIN

8、GQ_H__*/实现代码ringq.c#include#include"ringq.h"intringq_init(RINGQ*p_queue){p_queue->size=QUEUE_MAX;p_queue->head=0;p_queue->tail=0;p_queue->tag=0;return0;}intringq_free(RINGQ*p_queue){return0;}intringq_push(R