循环队列的基本操作

ゝ一世哀愁。 2022-03-22 03:27 264阅读 0赞

## 循环队列设置不同队空与队满条件的解决方案 ##

**为了解决顺序队列假溢出的问题，我们采用的方案是少用一个元素空间，此时的指针状态是队尾指针加1才与队头指针重合，于是此时队满的判定条件变为（rear+1）%MAXSIZE等于front,队空的判定条件依然是front等于rear,这样就能区分出来是队满还是队空状态了。**

**运行代码如下：**

**一、循环队列的定义：**

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    #define OK    1
    #define ERROR 0
    #define TRUE  1
    #define FALSE 0
    #define MAXSIZE 10
    
    typedef  int  Elemtype;
    typedef  int  Status;
    typedef  struct {
    	Elemtype *base;
    	int front;
    	int rear;
    }SqQueue;

**二、循环队列的初始化：**

void InitQueue(SqQueue *Q)
    {
    	Q->base=(Elemtype*)malloc(sizeof(Elemtype)*MAXSIZE);
    	assert(Q->base!=NULL);
    	Q->front=Q->rear=0;
    }

**三、入队操作：**

Status EnQueue(SqQueue*Q,Elemtype e)
    {
    	if((Q->rear+1)%MAXSIZE==Q->front)
    	{
    		return ERROR;
    	}
    	Q->base[Q->rear]=e;
    	Q->rear=(Q->rear+1)%MAXSIZE;
    	return OK;
    }

**四、判断队列是否为空：**

Status QueueEmpty(SqQueue *Q)
    {
    	if(Q->rear==Q->front)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }

**五、求队列长度：**

Status QueueLength(SqQueue *Q)
    {
    	return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
    }

**六、获取队头元素：**

Status GetHead(SqQueue *Q,Elemtype *e)
    {
    	if(Q->rear==Q->front)
    	{
    		return ERROR;
    	}
    	*e=Q->base[Q->front];
    	return OK;
    }

**七、清空队列：**

void ClearQueue(SqQueue *Q)
    {
    	Q->front=Q->rear=0;
    }

**八、销毁队列：**

void DestoryQueue(SqQueue *Q)
    {
    	if(Q->base)
    	{
    		free(Q->base);
    	}
    	Q->base=0;
    	Q->front=Q->rear=0;
    }

**九、出队操作：**

Status DeQueue(SqQueue *Q,Elemtype *e)
    {
    	if(Q->rear==Q->front)
    	{
    		return ERROR;
    	}
    	*e=Q->base[Q->front];
    	Q->front=(Q->front+1)%MAXSIZE;
    	return OK;
    }

**十、遍历队列：**

void QueueTraverse(SqQueue *Q,void(*visit)(Elemtype))
    {
    	int i=Q->front;
    	while(i!=Q->rear)
    	{
    		visit(Q->base[i]);
    		i=(i+1)%MAXSIZE;
    	}
    	printf("\n");
    }
    void Print(Elemtype e)
    {
    	printf("%d ",e);
    }

**十一、主函数：**

int main()
    {
    	int i,k;
    	Elemtype d,e;
    	SqQueue Q;
    	InitQueue(&Q);
    	printf("请输入%d个队列元素:\n",MAXSIZE-1);
    	for(i=1;i<MAXSIZE;i++)
    	{
    		scanf("%d",&d);
    		EnQueue(&Q,d);
    	}
    	printf("队列元素为:");
    	QueueTraverse(&Q,Print);
    	printf("队列长度为%d\n",QueueLength(&Q));
    	
    	k=QueueLength(&Q);
    	printf("连续%d次由对头删除元素，队尾插入元素:\n",k/2);
    	for(i=0;i<k/2;i++)
    	{
    		DeQueue(&Q,&e);
    		printf("删除的队列的元素是：%d,请输入插入的元素：",e);
    		scanf("%d",&d);
    		EnQueue(&Q,d);
    	}
    	printf("新的队列元素为：\n");
    	QueueTraverse(&Q,Print);
    	
    	int n=GetHead(&Q,&e);
    	if(n)printf("对头元素为：%d\n",e);
    	else {
    		printf("队空!\n");	return -1;
    	}
    	ClearQueue(&Q);
    	printf("清空队列后队列是否为空：%d\t(1:为空 ,0:不为空)\n",QueueEmpty(&Q));
    	DestoryQueue(&Q);
    	printf("销毁队列后:\nQ.base=%u\tQ.front=%d\tQ.rear=%d\t\n",Q.base,Q.front,Q.rear);
    	return 0;
    }

**十二、运行效果截图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]: /images/20220322/7cca92d58e2b4fc0b0f9e94a635a77c8.png