循环队列的学习解析以及C语言实现.doc

循环队列的学习解析以及C语言实现首先我们先来了解一下队列的概念：队列是一种先进先出的线性表只能在表头删除在表尾插入，操作系统的作业队列就是队列的一个很好的应用。也有可以在两端均可进行插入和删除操作的队列，称为双端队列，但其用处并没有一般队列广泛。ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n （约定其中a1 端为队列头， an 端为队列尾）基本操作 ： InitQueue(&Q) 初始化队列 DestroyQueue(&Q) 销毁队列 QueueEmpty(Q) 判断队列空否 QueueLength(Q) 求取队长 GetHead(Q, &e) 取对头元素 ClearQueue(&Q) 清空对列 EnQueue(&Q, e) 入队一个元素 DeQueue(&Q, &e) 出队一个元素 QueueTravers(Q, visit()） 访问队列 ADT Queue 队列也有两种存储结构，分别是顺序存储和链式存储。队列的顺序结构和顺序表以及顺序栈的存储结构类似，他们所运用的都是一组地址连续的存储。其中队列需要附设两个整形变量front和rear分别指示队列头元素和队列的尾元素的位置。cba54Q.rear321Q.frontQ.frontQ.rear0 (1)空队列 (2)a,b,c相继入队 由于顺序队列所分配的空间有限，根据队列入队和出队的特点可能发生“假溢出”现象，即队尾元素无法在前移。解决的办法就是将队列抽象成为环状，即循环队列。队空条件：Q.front=Q.rear 队满条件：(Q.rear+1)%MAXQSIZE循环队列以下是循环队列的几种主要的操作以及C语言实现：/*循环队列的数据结构*/#define MAXQSIZE10 typedef struct QElemType *base; int front; int rear; SqQueue;1、 循环队列的初始化 Status InitQueue(SqQueue &Q) /构建一个空队列 Q.base = new QElemTypeMAXQSIZE; if( Q.base = NULL) /存储分配失败 exit(OVERFLOW) ; Q.front = Q.rear = 0; /头尾指针置为零，队列为空 return OK;2、 求循环队列长度 int QueueLength(Squeue Q) return (Q.rear - Q.front + MAXQSIZE )%MAXQSIZE; 3、 入队 Status EnQueue (SqQueue &Q , QElemType e) if(Q.rear+1)%MAXQSIZe = Q.front)return ERROW;Q.baseQ.rear = e;Q.rear = (Q.rear + 1) %MAXQSIZE; return OK: 4、 出队 Status DeQueue(SqQueue &Q,QElemType &e) if(Q.front=Q.rear)return ERROW;e=Q.baseQ.front; Q.front = (Q.front + 1 )%MAXQSIZE; return OK; 5、 取队头元素 SElemType GetHead(SqQueue Q) if(Q.front ! = Q.rear) return Q.baseQ.front; 队列的链式表示和实现。/*队列的链式存储结构*/typedef struct QNondeQElemType date;struct QNode *next; QNode,QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue;1、 初始化 Status InitQueue(LinkQueue &Q)Q.front = Q.rear = new QNode;Qfront - next = NULL;return OK; 2、 入队Status EnQueue(LinkQueue &Q,QElemType e)p = new QNode ;p - date = e;p - next = NULL;Q.rear - next = p;Q.rear = p;return OK;3、 出队Status Dequeue(LinkQueue &Q,QElemType &e)if(Q.front = Q.rear)return ERROR; e = p - date; Q.front - next = p - next; if(Q.rear = p) Q.rear = Q.front; delete p; return OK; 4、 取队头元素 SElemType GetHead(LinkQueue Q)if(Q.front != Q.rear) return Qfront-next-date;