循环队列的学习解析以及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分别指示队列头元素和队列的尾元素的位置。 c b a (1)空队列 (2)a,b,,c相继入队 由于顺序队列所分配的空间有限，根据队列入队和出队的特点可能发生“假溢出”现象，即队尾元素无法在前移。解决的办法就是将队列抽象成为环状，即循环队列。 循环队列 以下是循环队列的几种主要的操作以及C语言实现： /********循环队列的数据结构***********/ #define MAXQSIZE　10 typedef struct { QElemType *base; int front; int rear; } SqQueue; 1、循环队列的初始化 Status InitQueue(SqQueue Q) { //构建一个空队列 Q.base = new QElemType[MAXQSIZE]; 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.base[Q.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.base[Q.front]; Q.front = (Q.front + 1 )%MAXQSIZE; return OK; } 5、取队头元素 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 {