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

循环队列的学习解析以及C语言实现首先我们先来了解一下队列的概念：队列是一种先进先出的线性表只能在表头删除在表尾插入，操作系统的作业队列就是队列的一个很好的应用。也有可以在两端均可进行插入和删除操作的队列，称为双端队列，但其用处并没有一般队列广泛。ADT Queue {数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系：R1＝{ a i-1,ai | 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分别指示队列头元素和队列的尾元素的位置。cba (1)空队列 (2)a,b,,c相继入队 由于顺序队列所分配的空间有限，根据队列入队和出队的特点可能发生“假溢出”现象，即队尾元素无法在前移。解决的办法就是将队列抽象成为环状，即循环队列。循环队列以下是循环队列的几种主要的操作以及C语言实现：/********循环队列的数据结构***********/#define MAXQSIZE　10 typedef struct { QElemType *base; int front; int rear; } SqQueue;循环队列的初始化Status InitQueue(SqQueue Q){ //构建一个空队列 Q.base = new QElemType[MAXQSIZE]; if( Q.base = NULL) //存储分配失败 exit(OVERFLOW) ; Q.front = Q.rear = 0; //头尾指针置为零，队列为空 return OK;}求循环队列长度 int QueueLength(Squeue Q) { return (Q.rear - Q.front + MAXQSIZE )%MAXQSIZE; }入队 Status EnQueue (SqQueue Q , QElemType e) { if((Q.rear+1)%MAXQSIZe == Q.front)return ERROW;Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) %MAXQSIZE; return OK: }出队 Status DeQueue(SqQueue Q,QElemType e) { if(Q.front==Q.rear)return ERROW;e=Q.base[Q.front]; Q.front = (Q.front + 1 )%MAXQSIZE; return OK; }取队头元素 SElemType GetHead(SqQueue Q){ if(Q.front ! = Q.rear) return Q.base[Q.front];}队列的链式表示和实现。/********队列的链式存储结构********/typedef struct QNonde{QElemType date;struct QNode *next; } QNode,QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue;初始化Status InitQueue(LinkQueue Q){Q.front = Q.rear = new QNode;Qfront - next = NULL;return OK;} 入队Status EnQueue(LinkQueue Q,QElemType e){p = new QNode ;p - date = e;p - ne