【数据结构取经之路】队列&循环队列

目录

引言

队列的性质

队列的基本操作

初始化

判空

销毁

队列的长度

插入

删除

返回队头元素

循环队列

假溢出

空与满的判定

实现 

初始化

插入

判空

销毁

删除

返回队列长度

返回队列头元素

判满

引言

队列和栈一样，也是数据结构的一种，可以用数组实现，也可以用链表实现。它常用于各种应用程序中，包括操作系统、网络通信等。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果多需要通过通道输出，那就要按请求输出的先后顺序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出作输出操作。

队列的性质

队列的性质与栈相反，它是一种“先进先出”的线性表。它只允许在队列的一端进行插入，在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫队头。

队列的基本操作

队列的操作和栈的操作类似，下面将以链式队列为例，逐一讲解各个操作。因为是用单链表实现队列，如果仅仅记录队头，那么在插入数据时必须得遍历一遍链表，找到队列的尾，才能链接上新的结点，这是一个不小的消耗，所以，除了对链表的结点封装成一个结构体(A)外，还可以再封装一个结构体(B)，B结构体成员里包含结构体A。这么说很抽象，还是看代码吧！

typedef int QueueDataType;

typedef struct QueueNode
{
	QueueDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;//指向链表头
	QueueNode* ptail;//指向链表尾
	int size;//记录长度
}Queue;

这样就方便对队列进行维护了。

初始化

初始化时，可以malloc出一些空间给队列，也可以不用，等到插入时再开辟空间也行，都无可厚非，我这里选择后者。

代码：

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

判空

链表为空的标志是size == 0.

代码：

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

销毁

因为队列底层是用单链表实现，所以在销毁时得一个节点一个节点的释放。在销毁节点A前，需要先记录A的下一个结点，否则把A释放后，将找不到它的下一个节点。销毁链表时还有一个细节，当只有一个节点时，free头结点后，要将头指针和尾指针都置空，如果仅把头指针置空，那么尾指针就是野指针。

代码：

void QueueDestroy(Queue* pq)
{
	assert(pq);

	while (pq->phead)
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		if (next == NULL) pq->ptail = NULL;//只有一个节点时，防止ptail为野指针
	}
}

队列的长度

size就是队列的长度，返回size即可。

代码：

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

插入

由于定义了尾指针，所以在插入前，就不需要遍历链表找尾了。第一种情况，链表不为空，不需要调整头指针，直接将新节点链接到尾节点后面即可，但不要忘了size++。第二种情况，链表为空，插入时，头指针和尾指针的指向都需要修改。

代码：

//创建节点
QueueNode* BuyNode(QueueDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->next = NULL;
	newnode->data = x;

	return newnode;
}

void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);

	QueueNode* newnode = BuyNode(x);

	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;//更新尾指针
	}
	pq->size++;
}

删除

第一点，当队列为空时，无法删除。第二，队列的删除操作是在队头进行的，所以需要更新头指针的指向。最后，不要忘了size--。

代码：

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QueueNode* newhead = pq->phead->next;
	free(pq->phead);
	pq->phead = newhead;
    pq->size--;
}

返回队头元素

通过头指针便可以访问到队头元素。当队列为空时，无法返回。

代码：

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}

循环队列

循环队列是把顺序队列首尾相连，把存储队列元素的数组从逻辑上看成一个环，成为循环队列。在物理上，它就是个数组，在逻辑上，我们要把它想象成一个圆环。循环队列的实现一般定义两个指针，头指针front和尾指针rear，front和rear开始都赋为0，每插入一个元素，rear++，每删除一个元素，front++，这和顺序栈如出一辙。front指向头，rear指向尾元素的下一个位置。

循环队列遵循先进先出的原则。

从队尾入队列，从队头出队列。

用数组实现的循环队列支持下标的随机访问，访问速度快。 

假溢出

请看上图，往队列里插入8个元素使队列呈满的状态，接着删除两个元素，此时，队列里有两个空位，但这两个空位是无法使用的，因为rear已经越界了，无法再继续插入。这种现象就叫作“假溢出”。这就导致了空间的浪费。

克服假溢出的方法有两种，第一种，把数组元素往前挪动，使其起始位置从0开始，显然，这种方法是很浪费时间的。第二种方法，就是使用循环队列，当存到最后一个地址后，下一个存放的位置就是从0开始。这也使得用数组实现的循环队列长度是固定的，不能动态增长。 

空与满的判定

循环队列的循环效果是用取余运算来实现的。在实现循环队列之前，我们首先搞清楚下面的问题——如何区分循环队列的空与满。

对比图a和图d1，我们发现，当循环队列为空时，存在front == rear，当循环队列满时，也存在front == rear，这样，就导致无法区分循环队列的空和满。解决方案有两种，第一种，令设一个变量来记录队列中的元素个数，以区分空和满；第二种，留出一个元素的空间，当队列头指针在队列尾指针的下一位置时，队列为满，队列为空的标志是front == rear，这样就将空和满这两种情况给区分开了。 

实现 

#define MIXSIZE 10

typedef int CQueueDataType;

typedef struct CycleQueue
{
	CQueueDataType a[MIXSIZE];
	int front;
	int rear;
}CycleQueue;

初始化

代码：

void CycleQueueInit(CycleQueue* pcq)
{
	assert(pcq);
	pcq->front = 0;
	pcq->rear = 0;
}

插入

如果队列已满，那么将无法插入。因为循环队列是定长的，长度不可动态增长。往队列中插入数据时还有以下细节：

第一种情况，直接rear++即可。第二种情况，在插入数据以后，如果直接rear++，将会越界，需要做特殊处理。

以上两种情况的统一处理方式为：

rear = （rear + 1）% MIXSIZE； 

当rear为最后一个元素的下标时，rear + 1 就是MIXSIZE，再模上MIXSIZE，正好为0，回到了数组的起始位置。由于取模操作本质上是去掉整除的部分，所以当rear < MIXSIZE时，进行取模操作后也可以得到正确的结果。

代码：

void CycleQueuePush(CycleQueue* pcq, CQueueDataType x)
{
	assert(pcq);
	assert(!CycleQueueFull(pcq));

	pcq->a[pcq->rear] = x;
	pcq->rear = (pcq->rear + 1) % MIXSIZE;
}

判空

循环队列为空的标志是：front == rear。

代码：

bool CycleQueueEmtpy(CycleQueue* pcq)
{
	assert(pcq);
	return pcq->front == pcq->rear;
}

销毁

代码：

void CycleQueueDestroy(CycleQueue* pcq)
{
	assert(pcq);
	free(pcq->a);
	pcq->front = 0;
	pcq->rear = 0;
}

删除

由于循环队列是用数组实现，所谓的删除并不是抹除数据，而是通过控制下标，让该元素在删除后无法被访问到。这里和插入时一样，有一个很类似的细节：

front++后可能会越界，统一的处理方式如下：

front = （front + 1）% MIXSIZE； 

代码：

void CycleQueuePop(CycleQueue* pcq)
{
	assert(pcq);
	pcq->front = (pcq->front + 1) % MIXSIZE;
}

返回队列长度

求循环队列长度的公式：

len = (rear - front + MIXSIZE) % MIXSIZE;

代码：

int CycleQueueLen(CycleQueue* pcq)
{
	assert(pcq);
	return (pcq->rear - pcq->front + MIXSIZE) % MIXSIZE;
}

返回队列头元素

队列头元素的下标为front。

代码：

CQueueDataType CycleQueueFront(CycleQueue* pcq)
{
	assert(pcq);
	return pcq->a[pcq->front];
}

判满

循环队列满的标志：

（rear + 1）% MIXSIZE == front； 

代码：

bool CycleQueueFull(CycleQueue* pcq)
{
	assert(pcq);
	return (pcq->rear + 1) % MIXSIZE == pcq->front;
}

 完！ 

————————————————————————————————————————————————————————————