如何实现循环队列
http://www.jb51.net/article/69898.htm
2015
本文主要介绍了C语言循环队列的实现,对于数据结构与算法的研究有所帮助,需要的朋友可以参考下
生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列；静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。
#ifndef SQQUEUE_H_INCLUDED
#define SQQUEUE_H_INCLUDED /* 防止重复包含 */
//////////////////////////////////////////
//包含头文件
#include
#include "ds.h" // OK, Status 等定义
//数据元素的类型(缺省使用int型)
#ifndef ElemType
#define ElemType int
#define USE_DEFAULT_ELEMTYPE /* 使用缺省类型的标志 */
#endif //ElemType
//////////////////////////////////////////
//循环队列的存储结构
#define MAXQSIZE 500/* 循环队列的最大容量 */
typedef struct {
/* TODO (#1#): 这里完成循环队列的类型定义 */
ElemType *base;
int front;
int rear;
//....................................
} SqQueue;
//////////////////////////////////////////
//循环队列的基本操作
//构造一个空队列Q
Status InitQueue(SqQueue &Q)
{
/* TODO (#2#): 构造空队列 */
Q.base=(ElemType*)malloc(MAXQSIZE *sizeof(ElemType));
if(!Q.base)exit(OVERFLOW);
QQ.front=Q.rear =0;
return OK; //TODO: 替换这行代码,以下同
//....................................
}
//销毁队列Q
// 前提：队列Q已存在
Status DestroyQueue(SqQueue &Q)
{
/* TODO (#3#): 销毁队列 */
free(Q.base);
Q.base=NULL;
Q.front=0;
Q.rear=0;
return OK;
//....................................
}
//将队列Q清为空队列
// 前提：队列Q已存在
Status ClearQueue(SqQueue &Q)
{
/* TODO (#4#): 清空队列 */
Q.base=0;
Q.rear=0;
return OK;
//....................................
}
//若队列Q为空，则返回TRUE，否则FALSE
// 前提：队列Q已存在
Status QueueEmpty(SqQueue Q)
{
/* TODO (#5#): 判断队列是否为空 */
if(Q.front==Q.rear)
return OK;
else
return ERROR;
//....................................
}
//返回队列Q的元素个数，即队列长度
// 前提：队列Q已存在
int QueueLength(SqQueue Q)
{
/* TODO (#6#): 返回队列长度 */
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
//....................................
}
//取队列Q头元素用e返回
// 前提：队列Q存在且非空
Status GetHead(SqQueue Q,ElemType &e)
{
/* TODO (#7#): 取队头元素存入e */
if(Q.rear==Q.front)
return ERROR;
e=Q.base[Q.front];
//e=*(Q.base+Q.front);
return OK;//返回操作状态(成功:OK,失败:ERROR)
//....................................
}
//插入元素e作为队列Q的新的队尾元素
// 前提：队列Q存在且未满
Status EnQueue(SqQueue &Q, ElemType e)
{
/* TODO (#8#): 元素e入队列 */
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
//e=*(Q.base +Q.rear);
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;//返回操作状态(成功:OK,失败:ERROR)
//....................................
}
//删除队列Q的队头元素，并用e返回
// 前提：队列Q存在且非空
Status DeQueue(SqQueue &Q, ElemType e)
{
/* TODO (#9#): 出队列存入e */
if(Q.front==Q.rear)
return ERROR;
//e=*(Q.base+Q.front);
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;//返回操作状态(成功:OK,失败:ERROR)
//....................................
}
//////////////////////////////////////////
//TODO: 定义好 SqQueue 类型后使用 QueueView 函数
/****** //TODO: 删除此行以便使用QueueView()
#include
//查看队列状态(调试用)
void QueueView(SqQueue Q)
{
extern void PrintElem(ElemType e);//打印数据用
int i=0;
if(Q.front=MAXQSIZE||Q.rear=MAXQSIZE){
printf("队列未初始化\n");
return ;
}
printf("---Queue View---\n");
printf("front=%d , rear=%d\n", Q.front, Q.rear);
if(Q.rear>=Q.front) {
printf("..... ......\n");
for(i=Q.front; i
printf("%5d\t", i);
PrintElem(Q.base[i]);
printf("\n");
}
if(i
} else {
for(i=0; i
printf("%5d\t", i);
PrintElem(Q.base[i]);
printf("\n");
}
printf("..... ......\n");
for(i=Q.front; i
printf("%5d\t", i);
PrintElem(Q.base[i]);
printf("\n");
}
}
printf("--- view end ---\n");
}
******/ //TODO: 删除此行以便使用QueueView()
//取消ElemType的默认定义，以免影响其它部分
#ifdef USE_DEFAULT_ELEMTYPE
#undef ElemType
#undef USE_EFAULT_ELEMTYPE
#endif
#endif //SQQUEUE_H_INCLUDED
#include
#include
#include "sqqueue.h"
//初始化系统
void Finalize(SqQueue &q);
////////////////////////////////////////////
//主程序
int main()
{
SqQueue q; //循环队列
int x;
//系统初始化
InitQueue(q);
printf("数据元素进队列,以0结束");
scanf("%d",&x);
while(x!=0){
EnQueue(q,x);
scanf("%d",&x);
}
printf("\n队列元素的个数");
printf("%d",QueueLength(q));
printf("\n头元素是：");
if(!QueueEmpty(q)){
if(GetHead(q,x)==OK)
printf("%d",x);
}
printf("\n出队列,先进先出");
if( DeQueue(q,x)==OK)
printf("%d",x);
printf("\n此时的对头是：");
if(!QueueEmpty(q)){
if(GetHead(q,x)==OK)
printf("%d\n",x);
}
}