数据结构10：顺序循环队列

摘要：

在我们已知队列的最大长度时，可以使用顺序表来进行队列的相关操作。但是，顺序队列会有一个较大的问题，即数组的“假”溢出。我们画一个图来看一下。
在这里插入图片描述

我们注意到，在出队操作后，数组其实是还有空间的，但是由于顺序表的单向性，rear指针已经指向了最后，代表了数组空间满了。这就是数组的“假”溢出现象。

对于，我们就可以用到今天要讲的顺序循环队列，实现队该数组空间的最大利用。图示如下

在这里插入图片描述

这就很好了，循环队列rear可以回到前面，假溢出现象就不复存在了，最大化的利用数组空间

一.代码块

是这样，由于rear要指向数据的后一个，如果是队满情况呢，rear就直接和front相等了同时队空的情况也是rear=front，两者就不好判断。我们又用到了一个经典的办法：放弃一个空间，不让其首尾相连，如果rear在front后面一个就判断为队满，rear==front就是队空，能储存的数据就比实际申请的空间要少一个

循环的队列该如何处理下标呢？事实上，数组下标正常加就行了，

将其对数组长度取余就会自动转换成我们循环意义上的下标，那么其他

的操作就跟正常的队列差不多了

1）创建

#define MAXSIZE 5

typedef struct circleQueue
{
	int data[MAXSIZE];
	int front;//指向的下标就是第一个 
	int rear; //指向的下标是最后一个数据的后一个 
}*circleQueuePtr;

2）初始化

void circleQueuePtrInit(circleQueuePtr paraPtr)
{
	paraPtr->front = 0;
	paraPtr->rear = 0;
}

3）打印

void outputCircleQueue(circleQueuePtr paraPtr)
{
	if(paraPtr->front  == paraPtr->rear)
	{
		printf("\r\n");
		return ;
	}
	
	int temp = paraPtr->front;
	while(1)
	{
		printf("%d ",paraPtr->data[temp % MAXSIZE]);
		if((temp+1) % MAXSIZE == paraPtr->rear % MAXSIZE)
		{
			break;
		}
		temp++;
		
	}
	printf("\r\n"); 	
}

4）入队

void enqueue(circleQueuePtr paraPtr,int paraData)
{
	if((paraPtr->rear + 1) % MAXSIZE == paraPtr->front % MAXSIZE)
	{
		printf("The queue is full\n");
		return ;
	}
	
	paraPtr->data[paraPtr->rear % MAXSIZE] = paraData;
	paraPtr->rear++;
}

5）出队

int dequeue(circleQueuePtr paraPtr)
{
	int tempData;
	if(paraPtr->front == paraPtr->rear)
	{
		printf("The queue is empty\n");
		return -1;
	}
	tempData = paraPtr->data[paraPtr->front % MAXSIZE];
	paraPtr->front++;
	
	return tempData;
}

6）我的测试函数

void test()//我的测试用例 
{
	circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue));
	circleQueuePtrInit(tempPtr);
	
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	
	enqueue(tempPtr,1);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,2);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,3);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,4);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,5);
	outputCircleQueue(tempPtr);
	
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	
	enqueue(tempPtr,666);
	outputCircleQueue(tempPtr);
}

我的测试函数运行结果

The queue is full
1 2 3 4
Dequeue gets 1
2 3 4
Dequeue gets 2
3 4
Dequeue gets 3
4
Dequeue gets 4

The queue is empty
Dequeue gets -1

666

7）老师的测试函数

void test2()//老师的测试用例 
{
	int i = 10;
	circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue));
	circleQueuePtrInit(tempPtr);
	
	for (; i < 16; i ++) 
	{
		enqueue(tempPtr, i);
	}

	outputCircleQueue(tempPtr);

	for (i = 0; i < 6; i ++) 
	{
		printf("dequeue gets %d\r\n", dequeue(tempPtr));
	}

	enqueue(tempPtr, 8);
	outputCircleQueue(tempPtr);
}

老师的测试函数运行结果

The queue is full
The queue is full
10 11 12 13
dequeue gets 10
dequeue gets 11
dequeue gets 12
dequeue gets 13
The queue is empty
dequeue gets -1
The queue is empty
dequeue gets -1
8

二.全部代码

#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 5

typedef struct circleQueue
{
	int data[MAXSIZE];
	int front;//指向的下标就是第一个 
	int rear; //指向的下标是最后一个数据的后一个 
}*circleQueuePtr;

/*是这样，由于rear要指向数据的后一个，如果是队满情况呢，rear就直接和front相等了
同时队空的情况也是rear==front，两者就不好判断。我们又用到了一个经典的办法：放弃一个空间
，不让其首尾相连，如果rear在front后面一个就判断为队满，rear==front就是队空，能储存的数据
就比实际申请的空间要少一个*/

void circleQueuePtrInit(circleQueuePtr paraPtr)
{
	paraPtr->front = 0;
	paraPtr->rear = 0;
}
/*循环的队列该如何处理下标呢？事实上，数组下标正常加就行了，
将其对数组长度取余就会自动转换成我们循环意义上的下标，那么其他
的操作就跟正常的队列差不多了*/ 
void outputCircleQueue(circleQueuePtr paraPtr)
{
	if(paraPtr->front  == paraPtr->rear)
	{
		printf("\r\n");
		return ;
	}
	
	int temp = paraPtr->front;
	while(1)
	{
		printf("%d ",paraPtr->data[temp % MAXSIZE]);
		if((temp+1) % MAXSIZE == paraPtr->rear % MAXSIZE)
		{
			break;
		}
		temp++;
		
	}
	printf("\r\n"); 	
}

void enqueue(circleQueuePtr paraPtr,int paraData)
{
	if((paraPtr->rear + 1) % MAXSIZE == paraPtr->front % MAXSIZE)
	{
		printf("The queue is full\n");
		return ;
	}
	
	paraPtr->data[paraPtr->rear % MAXSIZE] = paraData;
	paraPtr->rear++;
}

int dequeue(circleQueuePtr paraPtr)
{
	int tempData;
	if(paraPtr->front == paraPtr->rear)
	{
		printf("The queue is empty\n");
		return -1;
	}
	tempData = paraPtr->data[paraPtr->front % MAXSIZE];
	paraPtr->front++;
	
	return tempData;
}

void test()//我的测试用例 
{
	circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue));
	circleQueuePtrInit(tempPtr);
	
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	
	enqueue(tempPtr,1);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,2);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,3);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,4);
	outputCircleQueue(tempPtr);
	enqueue(tempPtr,5);
	outputCircleQueue(tempPtr);
	
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	printf("Dequeue gets %d\n",dequeue(tempPtr));
	outputCircleQueue(tempPtr);
	
	enqueue(tempPtr,666);
	outputCircleQueue(tempPtr);
}

void test2()//老师的测试用例 
{
	int i = 10;
	circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue));
	circleQueuePtrInit(tempPtr);
	
	for (; i < 16; i ++) 
	{
		enqueue(tempPtr, i);
	}

	outputCircleQueue(tempPtr);

	for (i = 0; i < 6; i ++) 
	{
		printf("dequeue gets %d\r\n", dequeue(tempPtr));
	}

	enqueue(tempPtr, 8);
	outputCircleQueue(tempPtr);
}

int main()
{
	test();
	test2(); 
}

原文链接：https://blog.csdn.net/qq_70132617/article/details/124849064

你可能也喜欢