循环队列----队列的顺序表示和实现

1.队列的顺序表示

1）C语言的描述

初始化建空对列时，令front=rear=0,每当插入新的队尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一位置，如图所示。

2）存在问题

假设当前为队列分配的最大空间为6，则当队列处于图3.12（d）的状态时不可再继续插入新的队尾元素，否则会因数组越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际存储空间未占满。一个巧妙的办法是将顺序队列臆造为一个环状空间，称之为循环队列。

2.循环队列的存储结构

#define  MAXQSIZE  100

typedef  struct

{

     QElemType     *base;

     int    front;

     int    rear;

}SqQueue;

3. 基本操作的函数原型

1）创建

Status InitQueue(SqQueue &Q)；

操作结果：构造一个循环队列Q

2）探空

int QueueEmpty(SqQueue Q)；

操作结果：若Q为空，返回TRUE，否则返回FALSE

3）入队

Status EnQueue(SqQueue &Q,QElemType e)；

操作结果：插入元素e为新的队尾元素

4）出队

Status DeQueue(SqQueue &Q,QElemType &e)；

操作结果：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK

                否则返回ERROR

5）获取队头元素

Status GetHead(SqQueue Q,QElemType &e)；

操作结果：若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR

6）求队长

int QueueLength(SqQueue Q)；

操作结果：返回队中元素个数

7）清空

Status ClearQueue(SqQueue &Q)；

操作结果：将Q清为空队列

8）输出队中全部元素

void Print(SqQueue Q)；

操作结果：输出Q中的全部元素

9）销毁

Status DestroyQueue(SqQueue &Q)；

操作结果：销毁队列Q，Q不再存在

4.循环队列及其基本操作示意图

5.附录（实现代码）

//----*----*----*---
//程序名称：循环队列
//编译环境：VC++ 6.0
//作者：Bee_darker
//修改日期：2018-10-25
//----*----*----*---

#define OK   1
#define OVERFLOW -1
#define ERROR 0
#define TRUE  1
#define FALSE 0
#define MAXQSIZE  100       //最大队列长度

#include "stdio.h"
#include "stdlib.h"

typedef int	Status;
typedef int QElemType;
typedef struct
{
	QElemType  *base;       //初始化的动态分配存储空间
	int  front;				//头指针，若队列不空，指向队列头元素
	int  rear;				//尾指针，若队列不空，指向队尾元素的下一位置
}SqQueue;

//创建
Status InitQueue(SqQueue &Q)
{
	Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if(!Q.base)
		exit(OVERFLOW);
	Q.front = Q.rear = 0;
	return OK;
}

//判队空
int QueueEmpty(SqQueue Q)
{
	if(Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}
//入队
Status EnQueue(SqQueue &Q,QElemType e)
{
	if((Q.rear+1) % MAXQSIZE == Q.front)
		return  ERROR;			//队列满
	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 ERROR;		//队列为空
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

//获取队头元素
Status GetHead(SqQueue Q,QElemType &e)
{
	if(Q.front  != Q.rear )
	{
		e = Q.base[Q.front];
		return OK;
	}
	return ERROR;
}

//求队长
int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

//清空
Status ClearQueue(SqQueue &Q)
{
	Q.front = Q.rear ;
	return OK;
}

//输出队中全部元素
void Print(SqQueue Q)
{
	if( Q.front == Q.rear)
		printf("Empty Queue\n");
	QElemType  x;
	printf("Q.front->");
	while(Q.front != Q.rear)
	{
		x = Q.base[Q.front];
		Q.front = (Q.front + 1) % MAXQSIZE;
		printf("%d->",x);
	}
	printf("Q.rear\n");
}

//销毁
Status DestroyQueue(SqQueue &Q)
{
	Q.base = NULL;
	return OK;
}

int main()
{
	SqQueue  Q;
	QElemType x;
	QElemType y;
	InitQueue(Q);
	printf("QueueEmpty:%d\n",QueueEmpty(Q));
	EnQueue(Q,1);
	EnQueue(Q,2);
	EnQueue(Q,3);
	Print(Q);
	printf("GetHead:%d\n",GetHead(Q,y));
	printf("y:%d\n",y);
	DeQueue(Q,x);
	Print(Q);
	ClearQueue(Q);
	printf("QueueLength:%d\n",QueueLength(Q));
	DestroyQueue(Q);
	return 0;
}

6.测试结果