循环队列的学习解析以及C语言实现.docx
《循环队列的学习解析以及C语言实现.docx》由会员分享，可在线阅读，更多相关《循环队列的学习解析以及C语言实现.docx（7页珍藏版）》请在冰点文库上搜索。
循环队列的学习解析以及C语言实现
循环队列的学习解析以及C语言实现
首先我们先来了解一下队列的概念：
队列是一种先进先出的线性表只能在表头删除在表尾插入，操作系统的作业队列就是队列的一个很好的应用。
也有可以在两端均可进行插入和删除操作的队列，称为双端队列，但其用处并没有一般队列广泛。
ADTQueue{
数据对象：
D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}
数据关系：
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（））访问队列
}ADTQueue
队列也有两种存储结构，分别是顺序存储和链式存储。
队列的顺序结构和顺序表以及顺序栈的存储结构类似，他们所运用的都是一组地址连续的存储。
其中队列需要附设两个整形变量front和rear分别指示队列头元素和队列的尾元素的位置。
c
b
a
5
4
Q.rear
→
3
2
1
→
Q.front
→
Q.front
→
Q.rear
0
（1）空队列
（2）a,b,,c相继入队
由于顺序队列所分配的空间有限，根据队列入队和出队的特点可能发生“假溢出”现象，即队尾元素无法在前移。
解决的办法就是将队列抽象成为环状，即循环队列。
队空条件：
Q.front=Q.rear
{
队满条件：
（Q.rear+1）%MAXQSIZE
循环队列
以下是循环队列的几种主要的操作以及C语言实现：
/********循环队列的数据结构***********/
#defineMAXQSIZE 10
typedefstruct
{
QElemType*base;
intfront;
intrear;
}SqQueue;
1、循环队列的初始化
StatusInitQueue（SqQueue&Q）
{//构建一个空队列
Q.base=newQElemType[MAXQSIZE];
if（Q.base=NULL）//存储分配失败
exit（OVERFLOW）;
Q.front=Q.rear=0;//头尾指针置为零，队列为空
returnOK;
}
2、求循环队列长度
intQueueLength（SqueueQ）
{
return（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE;
}
3、入队
StatusEnQueue（SqQueue&Q,QElemTypee）
{
if（（Q.rear+1）%MAXQSIZe==Q.front）
returnERROW;
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
returnOK:
}
4、出队
StatusDeQueue（SqQueue&Q,QElemType&e）
{
if（Q.front==Q.rear）
returnERROW;
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
returnOK;
}
5、取队头元素
SElemTypeGetHead（SqQueueQ）
{
if（Q.front!
=Q.rear）
returnQ.base[Q.front];
}
队列的链式表示和实现。
/********队列的链式存储结构********/
typedefstructQNonde
{
QElemTypedate;
structQNode*next;
}QNode,QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
1、初始化
StatusInitQueue（LinkQueue&Q）
{
Q.front=Q.rear=newQNode;
Q>front->next=NULL;
returnOK;
}
2、入队
StatusEnQueue（LinkQueue&Q,QElemTypee）
{
p=newQNode;
p->date=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}
3、出队
StatusDequeue（LinkQueue&Q,QElemType&e）
{
if（Q.front==Q.rear）
returnERROR;
e=p->date;
Q.front->next=p->next;
if（Q.rear==p）
Q.rear=Q.front;
deletep;
returnOK;
}
4、取队头元素
SElemTypeGetHead（LinkQueueQ）
{
if（Q.front!
=Q.rear）
returnQ>front->next->date;
}
升级会员 