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

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

环形队列实现原理/链式实现环形队列是在实际编程极为有用的数据结构,它有如下特点。  它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。  因为有简单高效的原因，甚至在硬件都实现了环形队列.   环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列. 一.环形队列实现原理------------------------------------------------------------  内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。  因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。  为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。   环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.   如何判断环形队列为空，为满有两种判断方法。  1.是附加一个标志位tag     当head赶上tail，队列空，则令tag=0,     当tail赶上head，队列满，则令tag=1, 2.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。      队列空：  head==tail     队列满：  (tail+1)%MAXN==head 二.附加标志实现算法采用第一个环形队列有如下结构typedefstructringq{  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->tail+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;/*为空还是为满的标志位*/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(RINGQ*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/*__RINGQ_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(RINGQ*p_queue,intdata){print_ringq(p_queue);if(ringq_is_full(p_queue)){printf("ringqisfull ");return-1;}p_queue->space[p_queue->tail]=data; p_queue->tail=(p_queue->tail+1)%p_queue->size;/*这个时候一定队列满了*/if(p_queue->tail==p_queue->head){p_queue->tag=1;}returnp_queue->tag;}intringq_poll(RINGQ*p_queue,int*p_data){print_ringq(p_queue);if(ringq_is_empty(p_queue)){printf("ringqisempty ");return-1;}*p_data=p_queue->space[p_queue->head];p_queue->head=(p_queue->head+1)%p_queue->size;/*这个时候一定队列空了*/if(p_queue->tail==p_queue->head){p_queue->tag=0;}returnp_queue->tag;}测试代码/*测试第一种环形队列*/voidtest5(){RINGQrq,*p_queue;inti,data;p_queue=&rq;ringq_init(p_queue);for(i=0;i=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data); if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);ringq_free(p_queue);}/*测试第一种环形队列,更加复杂的情况*/voidtest6(){RINGQrq,*p_queue;inti,data;p_queue=&rq;ringq_init(p_queue);ringq_push(p_queue,1);ringq_push(p_queue,2);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);ringq_push(p_queue,3);ringq_push(p_queue,4);ringq_push(p_queue,5);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);ringq_push(p_queue,6);if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data); if(ringq_poll(p_queue,&data)>=0)PRINT_INT(data);ringq_free(p_queue);}三.预留空间环境队列  ------------------------------------------------------------------- 不采用tag,只留一个空间   初始化状态: q->head=q->tail=q->tag=0;队列为空:(q->head==q->tail)队列为满:(((q->tail+1)%q->size)==q->head)入队操作:如队列不满，则写入    q->tail= (q->tail+1)%q->size;出队操作：如果队列不空，则从head处读出。   下一个可读的位置在 q->head= (q->head+1)%q->size 头文件 ringq.h#ifndef__RINGQ_H__#define__RINGQ_H__#ifdef__cplusplusextern"C"{#endif#defineRINGQ_MAX20 typedefstructringq{  inthead;/*头部，出队列方向*/  inttail;/*尾部，入队列方向*/  intsize;/*队列总尺寸*/  intspace[RINGQ_MAX];/*队列空间*/}RINGQ;/* 取消tag.限制读与写之间至少要留一个空间 队列空head==tail. 队列满是(tail+1)%MAX==head  初始化是head=tail=0;  */externintringq_init(RINGQ*p_ringq);externintringq_free(RINGQ*p_ringq);externintringq_push(RINGQ*p_ringq,intdata);externintringq_poll(RINGQ*p_ringq,int*p_data);#defineringq_is_empty(q)(q->head==q->tail)#defineringq_is_full(q)(((q->tail+1)%q->size)==q->head)#defineprint_ringq2(q,d)printf("ringhead%d,tail%d,data%d ",q->head,q->tail,d);#ifdef__cplusplus}#endif#endif/*__QUEUE_H__*/实现代码ringq.c#include#include"ringq.h"intringq_init(RINGQ*p_ringq){ p_ringq->size=RINGQ_MAX;   p_ringq->head=0; p_ringq->tail=0;  returnp_ringq->size;}intringq_free(RINGQ*p_ringq){ return0;}/*往队列加入数据*/intringq_push(RINGQ*p_ringq,intdata){  print_ringq(p_ringq,data);    if(ringq_is_full(p_ringq))    {        printf("ringqisfull,data%d ",data);          return-1;    }          p_ringq->space[p_ringq->tail]=data;    p_ringq->tail=(p_ringq->tail+1)%p_ringq->size;        returnp_ringq->tail;}intringq_poll(RINGQ*p_ringq,int*p_data){  print_ringq(p_ringq,-1); if(ringq_is_empty(p_ringq))  {    printf("ringqisempty ");    return-1;  }    *p_data=p_ringq->space[p_ringq->head];    p_ringq->head=(p_ringq->head+1)%p_ringq->size;    returnp_ringq->head; }作者：AndrewHuang bluedrum@163.com环形队列的链式实现from:http://www.cnblogs.com/herbert/archive/2011/01/17/1937787.html程序是用codeblock写的，中间碰到了一个又一个的问题，都最终解决了。这个结构可以作为所有结构体的实现的一个模式。写写这些程序可以不断让自己更加深入认识指针，更加熟悉指针的各种使用。经常锻炼C基础，心里写程序更有底.#include#include#includetypedefintQueue_Type;//定义队列节点结构typedefstructCQUEUE_NODE{Queue_Typevalue;structCQUEUE_NODE*next;}QNode,*PNode;//定义队列结构typedefstructCQUEUE{unsignedintsize;PNodefront,retail;}LQueue;//创建环形队列voidCreate_Queue(LQueue*L,intn){PNodefront=(PNode)malloc(sizeof(QNode));PNoderetail=(PNode)malloc(sizeof(QNode));if(front==NULL||retail==NULL)exit(1);scanf("%d",&front->value);front->next=NULL;//只有一个节点的时候，头尾指向同一个点retail=front;//多个点情况inti; for(i=1;ivalue);retail->next=p;retail=p;}//结束后，尾节点指向头节点retail->next=front;L->front=(PNode)malloc(sizeof(QNode));L->retail=(PNode)malloc(sizeof(QNode));if(L->front==NULL||L->retail==NULL)exit(1);L->front=front;L->retail=retail;L->size=n;}//销毁队列voidDestory_Queue(LQueue*L){//如果队列为空if(L->front==NULL)exit(1);//这里注意必须重新申请一个节点//直接使用L->retail->next会有类型不能识别的错误PNodep=(PNode)malloc(sizeof(QNode));if(p==NULL)exit(1);p=L->front;intsize=L->size;//队列是多个节点情况while(size!=0){L->front=p->next;free(p);p=L->front;size--;} //这里一定要记得处理//将frontretail指向NULL在上面的处理过程中，只是free并没有指向NULL//如果不指向NULL,front,retail将是野指针//还要记得将L->size重新赋值，上面size只是读取size，并不改变size的值L->front=NULL;L->retail=NULL;L->size=size;}//入列操作在尾节点插入voidEnqueue(LQueue*L,Queue_Typevalue){PNodep=(PNode)malloc(sizeof(QNode));if(p==NULL)exit(1);p->value=value;intsize=L->size;//如果队列是个空队列if(size==0){L->front=(PNode)malloc(sizeof(QNode));L->retail=(PNode)malloc(sizeof(QNode));L->front=p;L->retail=p;p->next=NULL;size++;}//如果队列不是空队列//头节点倒是没有必要重新开辟空间PNodep1=(PNode)malloc(sizeof(QNode));if(p1==NULL)exit(1);p1=L->retail;p1->next=p;p->next=L->front;L->retail=p;//这里没发现啊，害我找了很久size++;L->size=size;}//出列操作 Queue_TypeDequeue(LQueue*L){intsize=L->size;Queue_Typen;//如果队列为空if(size==0){printf("Thequeueisempty. ");exit(1);}PNodep=(PNode)malloc(sizeof(QNode));if(p==NULL)exit(1);p=L->front;//如果队列只有一个节点if(size==1){n=p->value;free(p);L->front=L->retail=NULL;p=NULL;size--;L->size=size;returnn;}if(size==2){n=p->value;L->front=L->retail;free(p);p=NULL;size--;L->size=size;returnn;}//头节点倒是没有必要重新开辟空间PNodep1=(PNode)malloc(sizeof(QNode));if(p1==NULL)exit(1); p1=L->retail;n=p->value;L->front=p->next;p1->next=L->front;free(p);p=NULL;size--;L->size=size;returnn;}//判断队列是否为空boolIs_Empty(LQueueL){if(L.size==0)returnfalse;elsereturntrue;}//打印队列voidPrint_Queue(LQueueL){//如果队列为空if(L.size==0){printf("Thesizeofthequeueis:%d ",L.size);exit(1);}printf("Thesizeofthequeueis:%d ",L.size);printf("Thefollowingaretheelementsofthequeue: ");PNodep=(PNode)malloc(sizeof(QNode));if(p==NULL)exit(1);p=L.front;while(p!=L.retail){printf("%d ",p->value);p=p->next;} if(p==L.retail){printf("%d ",p->value);}}intmain(){LQueueL;intn;printf("Inputthenumberofthenodesofthequeue: ");scanf("%d",&n);printf("------------------------------------------- ");Create_Queue(&L,n);printf("------------------------------------------- ");Print_Queue(L);printf("------------------------------------------- ");printf("Enqueueanode: ");intn1,n2,n3;scanf("%d",&n1);Enqueue(&L,n1);printf("------------------------------------------- ");Print_Queue(L);printf("Dequeueonenode------------------------- ");n2=Dequeue(&L);printf("Node1is%d ",n2);Print_Queue(L);printf("Dequeueanothernode------------------------- ");n3=Dequeue(&L);printf("Node2is%d ",n3);Print_Queue(L);printf("------------------------------------------- ");printf("Destorythequeue--------------------------- ");Destory_Queue(&L);Print_Queue(L);return0;}关于指针可能碰到的问题，在注释里差不多都说明了。需要特别注意几个问题：一，结构作为参数传递。这个传递方式也是和其他一样的，当需要改变传入参数的值的时候，用地址传递，使用指针参数。参数的传递类似于一般的int了，使用结构体指针就行。二，结构体参数值传递和地址传递的调用方式的不同。结构体参数如果是以普通值传递进入 参数，使用结构体.成员来访问。如果是以地址传递，也就是传入的是指针参数，就是结构体->成员来访问。这个就是结构体和结构体指针访问数据成员的差异。三，像队列这种包含头尾队列点的结构体，在初始化的时候，要为每个一个指针结构申请空间，也就是里面的L->front=(PNode)malloc(sizeof(QNode));L->retail=(PNode)malloc(sizeof(QNode));四，在取结构体成员指针指向的数据的时候，不要使用 结构体指针->指针成员->指针成员指向的数据。这样多个"->"连接会导致编译不能识别“结构体指针->指针成员”这个指针类型，会报错的。相应的处理方法是申请一个指针指向它就行。然后操作这个指针。五，对于特定临界点情况的处理要慎重，比如队列数据点为0，1，2这几个情况对于环形队列是不同的，需要额外注意。具体的算法，上面的程序里面都有了。都经过了简单的测试，应该没什么问题。 顺道说下CODEBLOCK的debug，到现在我不太知道，怎样使用，几次加入Watch变量都没反应囧，出错了，只能一个一个自己分析。注：这个问题后来查了相关的论坛，原来codeblock不允许项目路径有空格和中文字符导致