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

循环队列的学习解析以及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

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语言实现：
/********循环队列的数据结构***********/

#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
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

1、 初始化

Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = new QNode;
Q>front -> 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 Q>front->next->date;
}