欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

环形队列-基于队头指针和队列中元素的个数的另一种实现

程序员文章站 2022-06-06 20:55:59
...

由队头指针和元素个数进行如下计算

已知front、rear,求队中元素个数:

   count=(rear-front+MaxSize)%MaxSize

已知front、count,求rear:

   rear=(front+rear)%MaxSize

已知rear、count,求front:

   front=(rear-count+MaxSize)%MaxSize

 

环形队列-基于队头指针和队列中元素的个数的另一种实现

环形队列的基本操作:

队空条件:count=0
队满条件:count=MaxSize
进队e操作:rear=(rear+1)%MaxSize; 将e放在rear处
出队操作:front=(front+1)%MaxSize;取出front处元素e;
这样的环形队列中最多可放置MaxSize个元素。
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize];
	int front;			//队头指针
	int count;			//队列中元素个数
} QuType;
void InitQueue(QuType *&qu)						//初始化队运算算法
{	qu=(QuType *)malloc(sizeof(QuType));
	qu->front=0;
	qu->count=0;
}
void DestroyQueue(QuType *&qu)
{
	free(qu);
}
bool EnQueue(QuType *&qu,ElemType x)			//进队运算算法
{	int rear;									//临时队尾指针
	if (qu->count==MaxSize)						//队满上溢出
		return false;
	else
	{	rear=(qu->front+qu->count)%MaxSize;	//求队尾位置
		rear=(rear+1)%MaxSize;					//队尾循环增1
		qu->data[rear]=x;
		qu->count++;							//元素个数增1
		return true;
	}
}
bool DeQueue(QuType *&qu,ElemType &x)			//出队运算算法
{	if (qu->count==0)							//队空下溢出
		return false;
	else
	{	qu->front=(qu->front+1)%MaxSize;		//队头循环增1
		x=qu->data[qu->front];
		qu->count--;							//元素个数减1
		return true;
	}
}
bool QueueEmpty(QuType *qu)						//判队空运算算法
{
	return(qu->count==0);
}
void main()
{
	QuType *q;
	ElemType e;
	InitQueue(q);
	EnQueue(q,1);
	EnQueue(q,2);
	EnQueue(q,3);
	EnQueue(q,4);
	printf("出队顺序:");
	while (!QueueEmpty(q))
	{
		DeQueue(q,e);
		printf("%d ",e);
	}
	printf("\n");
	DestroyQueue(q);
}