数据结构之循环队列

客官°小女子只卖身不卖艺 2022-06-03 10:48 262阅读 0赞

继续学习数据结构。今天学习循环队列，在学习循环队列之前，我们得先知道什么是队列呀，然后才可以继续往下学习。

首先我们回顾下队列的相关知识。

**队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。**

**队列是一种先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。**

![Center][]

队列同样是一种线性表，队列也有类似线性表的各种操作，不同的是插入的数据是在队尾进行，删除数据只能在队头进行。

那么我们同样可以使用顺序存储结构去实现队列。试想下我们使用使用数组进行队列的插入删除操作，会有什么效果呢？

如果我们将队列的元素限制在数组的前n个单元，那么在队尾追加元素不需要移动任何元素，时间复杂度O（1），但是从队头也就是下标为0删除一个元素，每个元素都要向前移动一个位置，时间复杂度为O（n）。

当然也可以不将队头设置在下标为0的位置，队头队尾用动态指针进行指向，删除元素后front指针指向数组中间时，继续添加元素队尾指针会指向队外了，虽然数组还有空闲元素，但是显示队列已满，这种就是**假溢出**。就好比我们上公交车，上车后，发现车后面没有位置，但是前面还有位置，难道我们还得下去么，我们肯定会去前面找位置坐下呗。

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。**我们把队列的这种头尾相接的顺序存储结构称为循环队列****。**那么此时问题又来了，当空队列时，front=rear，现在队列满了front=rear,那么如何判断此时的队列究竟是空还是满呢？

这里有2种方法

方法一：设置标志位，flag，当front=rear，且flag= 0时为队列为空，当front=rear，且flag=1时为队列满。

方法二：front=rear时队列为空，当队列满时，我们修改其条件，保留一个元素空间，也就是说，队列满时，数组中还有一个空闲单元。不允许出现将数组全部填充满。如图：

![Center 1][]

删除3个元素又添加3个元素后的指向

![Center 2][]

我们重点来讨论第二种方法。当队列满的时候，rear可能比front大，也可能比front小(当rear超圈时)。**队列满的条件是(rear+1)%QueueSize == front.**我们继续看一下**队列的长度**（队列中元素的个数）当rear>front是时，队列的长度为rear-front,当rear<front时，队列长度 = QueueSize-front + rear – 0 = rear-front + QueueSize 可改成通用**(rear-front+QueueSize)/QueueSize  **

知道上面的知识后，现在来实现循环队列的代码就不难了。

循环队列的顺序存储结构代码：

typedef structSeqQueue

EleType data\[QUEUESIZE\];

int front;//头结点下标

int rear;//尾结点下标

\} SeqQueue;

下面是整个的代码：

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #define QUEUESIZE 10
    #define ERROR 0 
    #define OK 1 
    #define TRUE 1 
    #define FALSE 0
    #define EleType int 
    #define Status int
    //循环队列数据结构
    typedef struct SeqQueue 
    {
    	EleType data[QUEUESIZE];
    	int front;//头结点下标
    	int rear;//尾结点下标
    } SeqQueue;
    /*
    初始化循环队列
    */
    Status InitSeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	queue->front = queue->rear = 0;
    	return OK;
    }
    /*
    清空队列
    */
    Status ClearSeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	queue->front = queue->rear = 0;
    	return OK;
    }
    /*
    判断循环队列是否为空
    */
    Status EmptySeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == queue->rear)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }
    /*
    循环队列的元素个数
    */
    int LengthSeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == queue->rear)
    	{
    		return 0;
    	}
    	//留的那个空单元不算做元素个数 
    	return (queue->rear - queue->front + QUEUESIZE)% QUEUESIZE;
    }
    /*
    获取循环队列头元素
    */
    Status GetHead(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	return queue->data[queue->front];
    }
    /*
    往队尾添加元素
    */
    Status AddQueue(SeqQueue* queue,EleType e)
    {
    	//队满或空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//刚好队尾再走一个单元就到队头，说明栈满了。
    	if ((queue->rear + 1) % QUEUESIZE == queue->front)
    	{
    		return ERROR;
    	}
    	queue->data[queue->rear] = e;
    	queue->rear = (queue->rear + 1) % QUEUESIZE;//若到队尾转到数组头部
    	return OK;
    }
    /*
    队头删除元素
    */
    Status DelQueue(SeqQueue* queue,EleType *e)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//队空
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	*e = queue->data[queue->front];
    	queue->front = (queue->front + 1) % QUEUESIZE;//若到队尾转到数组头部
    	return OK;
    }
    void PrintfQueue(SeqQueue* queue)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//队空
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	int begin = queue->front;
    	while (begin!=queue->rear)
    	{
    		printf("%d,", queue->data[begin]);
    		if (begin < QUEUESIZE-1)
    		{
    			begin++;
    		}
    		else
    		{
    			begin = begin + 1 - QUEUESIZE;
    		}
    
    	}
    	printf("\n");
    	return;
    }
    int main(int argc, char *argv[])
    {
    	SeqQueue queue;
    	InitSeqQueue(&queue);
    	AddQueue(&queue, 1);
    	AddQueue(&queue, 2);
    	AddQueue(&queue, 3);
    	AddQueue(&queue, 4);
    	AddQueue(&queue, 5);
    	AddQueue(&queue, 6);
    	AddQueue(&queue, 7);
    	AddQueue(&queue, 8);
    	AddQueue(&queue, 9);
    	printf("展示队列元素：");
    	PrintfQueue(&queue);
    	printf("队列元素个数：%d\n", LengthSeqQueue(&queue));
    	EleType e1, e2;
    	DelQueue(&queue, &e1);
    	printf("删除队头元素：%d\n", e1);
    	DelQueue(&queue, &e2);
    	printf("删除队头元素：%d\n", e2);
    	printf("现在的队头元素：%d\n", GetHead(&queue));
    	printf("展示队列元素：");
    	PrintfQueue(&queue);
    	printf("队列元素个数：%d\n", LengthSeqQueue(&queue));
    	AddQueue(&queue, 10);
    	AddQueue(&queue, 11);
    	printf("继续添加2个元素10，11\n");
    	printf("展示队列元素：");
    	PrintfQueue(&queue);
    	//此时 front指向下标为2的元素,rear指向下标为1的元素
    	printf("front:%d,rear:%d\n", queue.front, queue.rear);
    
    	return 0;
    }

验证结果截图：

![Center 3][]

**这样循环队列就不用像顺序存储的线性表那样频繁的移动元素位置，而在用通过下标的移动和循环来操作。这样时间性能比较高。但是仍然面临的是顺序存储结构都会面临的问题数组长度不够的情况。**

[Center]: /images/20220603/d78d99494ebf4dd1aedd1accb93d4b11.png
[Center 1]: /images/20220603/1197b5e637d84da7a67684ccb848db98.png
[Center 2]: /images/20220603/d46f39e5a3474094af895c6d799d22f4.png
[Center 3]: /images/20220603/c84746bb36f8484b969fa70f3def4e34.png