本文共 2753 字，大约阅读时间需要 9 分钟。

一、队列概念

1、队列(queue)是一种只允许在一端进行插入操作，而在另一端进行删除的操作的线性表

2、队列是一种先进先出(first in first out)的线性表，简称FIFO。允许插入的一端成为队尾，允许删除的一端成为对头。假设队列是q=(a1,a2,...,an),那么a1就是对头元素，an就是队尾元素。这样我们删除时，总是从a1开始，而插入时，列在最后。

二、循环队列

1、为了解决顺序队列插入和删除时需要移动数据、"假溢出"问题，引入循环队列。循环队列的定义：我们把队列的这种头尾相接的顺序存储结构成为循环队列。

2、顺序队列的插入删除的时间复杂度为O（1）。

二、循环队列数据结构

typedef int QElemType;//根据实际情况而定，这里假设为int/********循环队列的顺序存储数据结构**********/typedef struct queue {	QElemType *pBase;	  //顺序存储内存分配基地址	int front;    //指向队列第一个元素	int rear;    //指向队列最后一个元素的下一个元素	int maxsize; //循环队列的最大存储空间}QUEUE,*PQUEUE;

三、循环队列基本操作

1、创建队列

bool CreateQueue(PQUEUE Q,int maxsize){	if(!Q)		return false;	Q->pBase = (QElemType *)malloc(sizeof(QElemType)*maxsize);	if(!Q->pBase)	{		printf("Memory allocation failure");		return false;	}	else	{		Q->front=0;         //初始化参数		Q->rear=0;		Q->maxsize=maxsize;	}		return true;}

2、空队列

bool EmptyQueue(PQUEUE Q){	if(!Q)		return false;	if(Q->front==Q->rear)    //判断是否为空		return true;	else		return false;}

3、满队列

bool FullQueue(PQUEUE Q){	if(!Q)		return false;	if(Q->front==(Q->rear+1)%Q->maxsize)    //判断循环链表是否满，留一个预留空间不用		return true;	else		return false;}

4、入队

bool Enqueue(PQUEUE Q, QElemType val){	if(!Q)		return false;	if(FullQueue(Q))		return false;	else	{		Q->pBase[Q->rear]=val;		Q->rear=(Q->rear+1)%Q->maxsize;		return true;	}}

5、出队

bool Dequeue(PQUEUE Q, QElemType *val){	if(!Q)		return false;	if(EmptyQueue(Q))	{		return false;	}	else	{		*val=Q->pBase[Q->front];		Q->front=(Q->front+1)%Q->maxsize;		return true;	}}

6、获取队列长度

int QueueLength(PQUEUE Q){	if(!Q)return -1;	else		return (Q->rear-Q->front+Q->maxsize)%Q->maxsize;}

7、

bool GetHead(PQUEUE Q, QElemType *val) {	if(EmptyQueue(Q))	{		return false;	}	else	{		*val=Q->pBase[Q->front];		return true;	}}

8、清空队列

bool ClearQueue(PQUEUE Q){	if(!Q)		return false;	Q->front = Q->rear;	return true;}

9、销毁队列

int DestroyQueue(PQUEUE Q){	if(!Q)		return false;	if(Q->pBase)		free(Q->pBase);	Q->pBase = NULL;	return true;}

10、遍历队列

bool TraverseQueue(PQUEUE Q){	if(!Q)		return false;			int i=Q->front;	printf("队中的元素是:\n");	while(i%Q->maxsize!=Q->rear)	{		printf("%d ",Q->pBase[i]);		i++;	}	printf("\n");	return true;}

四、测试代码及测试结果

void main(void){		QUEUE MyQueue;	int ret = CreateQueue(&MyQueue,10);	if(false == ret)		return;	QElemType i;	for(i = 0;i < 20;i++)	{		if(false == Enqueue(&MyQueue,i)) break;		else			printf("依次入队元素：%d\n",i);	}	int len = QueueLength(&MyQueue);	printf("===========len：%d===========\n",len);	TraverseQueue(&MyQueue);	QElemType val;	GetHead(&MyQueue,&val);	printf("===========对头元素：%d===========\n",val);	for(i = 0;i < 5;i++)	{		if(false == Dequeue(&MyQueue,&val)) break;		else			printf("依次出队元素：%d\n",val);	}	TraverseQueue(&MyQueue);	ClearQueue(&MyQueue);	DestroyQueue(&MyQueue);	system("pause");}

注意:此循环队列/环形缓冲，当缓冲区满时，只实现了不覆盖old data

转载地址：http://lnxxb.baihongyu.com/