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

梦里梦外; 2023-03-12 12:23 17阅读 0赞

**基于队头指针和队列中的元素个数实现环形队列**

对于环形队列来说，如果知道队头指针和队列中元素个数，则可以计算出队尾指针。也就是说，可以用队列中元素个数代替队尾指针。

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

已知front、rear，求队中元素个数：

count=(rear-front+MaxSize)%MaxSize

已知front、count，求rear：

rear=(front+rear)%MaxSize

已知rear、count，求front：

front=(rear-count+MaxSize)%MaxSize

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70][]

**环形队列的基本操作：**

*  队空条件：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);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70]: /images/20230312/8662056cd9d24cd28b389f2ef5a76a8f.png