【数据结构】线性表--队列

一.什么是队列

情景引入：
你们在用电脑时有没有经历过，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算reset时,突然它像酒醒了一样，把你刚才单击的所有操作全部都按顺序执行了一遍。这是因为操作系统在当时可能CPU一时忙不过来，等前面的事忙完后，后面多个指令需要通过一个通道输出，按先后次序排队执行造成的结果。
再比如像移动、联通、电信等客服电话，客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待，直至有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。
操作系统和客服系统中,都是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

概念理解：
队列也是一种操作受限的线性表，与栈不同的是，队列要求在一端插入数据，在另一端删除数据（就类似于日常生活中的排队一样）。
我们将插入数据的一端称为队尾，删除数据的一端称为队头。队列满足FIFO（first in first out）原则。如图所示：

二.队列的实现

队列也有两种表示方法：①顺序存储②链式存储。

顺序存储即采用数组做为底层结构，由于在一端插入数据，另一端删除数据，此时需要大量移动元素。

链式存储可以使用单链表，也可以使用双向链表。
使用单链表时，可以将链表头作为队头，链表尾作为队尾，此时删除数据的操作即是头删，时间复杂度为O(1)，但是插入数据时，需要进行频繁的尾插操作，时间复杂度为O(n)，因此可以再设立一个尾指针指向最后一个结点，避免每次尾插需要遍历整个链表，优化时间复杂度为O(1)。
使用双链表时，即头插尾删，或头删尾插。
本文使用单链表实现队列。

1.队列结构定义：

因为使用单链表来实现队列，所以先定义出结点结构。结点需要存储数据本身信息，以及保存下一个结点的位置信息。

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

因为队列需要进行频繁的尾插操作，所以再定义一个结构，用头指针和尾指针来保存队列的头结点和尾结点的信息，以优化尾插操作的时间复杂度。

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

2.队列初始化函数：

队列初始化即将头指针和尾指针均置为空即可。

//初始化函数
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}

3.队列销毁函数：

队列的销毁即通过头指针来找到各个结点，将结点空间依次释放，最后再将头尾指针再次置空。

//销毁函数
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

4.入队列函数（尾插）：

数据元素入队列：先以元素的值申请一个新结点，然后通过尾指针找到最后一个结点，将新结点链接到最后一个结点的next指针，最后再将尾指针指向新结点。

//入队列函数
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//处理申请空间失败的情况
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空时，将头尾指针指向同一个结点
	if (pq->head == NULL)
		pq->head = pq->tail = newnode;
	else
	{
		//先将新结点链接到队列的队尾
		pq->tail->next = newnode;
		//再将尾指针指向新结点
		pq->tail = newnode;
	}
}

5.出队列函数（头删）：

出队列时需要注意先判断队列是否为空，当队列为空时不能出数据，可以使用assert断言，也可以直接返回。
不为空时通过头指针找到第一个结点，再顺着找到下一个结点（若下一个结点为空，则代表此时链表只有一个结点，直接删除），释放掉第一个结点，并将头指针指向下一个结点。

//出队列函数
void QueuePop(Queue* pq)
{
	assert(pq);
	
	//队列为空时不能出数据（或者使用断言）
	if (pq->head == NULL)
	{
		return;
	}
	else
	{
		//先记录头指针的下一个结点
		//需要先判断下一个结点是不是空
		if (pq->head->next == NULL)
		{
			free(pq->head);
			pq->head = pq->tail = NULL;
		}
		else
		{
			QNode* next = pq->head->next;

			//释放头指针指向的结点
			free(pq->head);
			//将头指针指向下一个结点，成为新的队头
			pq->head = next;
		}
	}
}

6.取队头元素：

取队头元素也要注意判断队列是否为空，使用断言判断，不为空直接返回头指针指向第一个结点的值。

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//队为空不能取数据

	return pq->head->data;
}

7.取队尾元素：

取队尾元素也要注意判断是否为空，使用断言判断。不为空时直接返回尾指针指向结点的值。

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//队为空不能取数据

	return pq->tail->data;
}

8.求队长：

求队长直接用一个int变量，通过头指针依次遍历到尾指针，该变量++即可。

//求队长（数据个数）
int QueueSize(Queue* pq)
{
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

9.判空：

直接看头指针是否为空即可判断队列是否为空。

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;//队列为空返回true，否则返回false
}

三.总结

除了上述实现的普通队列，还有循环队列、优先队列、双端队列、阻塞队列等队列，感兴趣可以上网搜索一下相关实现。
以下是本文全部源码：
Queue.h:

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

//初始化函数
void QueueInit(Queue* pq);

//销毁函数
void QueueDestory(Queue* pq);

//入队列函数
void QueuePush(Queue* pq, QDataType x);

//出队列函数
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);

//取队尾数据
QDataType QueueBack(Queue* pq);

//求队长（数据个数）
int QueueSize(Queue* pq);

//判空
bool QueueEmpty(Queue* pq);

Queue.c:

#include"Queue.h"

//初始化函数
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}

//销毁函数
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//入队列函数
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//处理申请空间失败的情况
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空时，将头尾指针指向同一个结点
	if (pq->head == NULL)
		pq->head = pq->tail = newnode;
	else
	{
		//先将新结点链接到队列的队尾
		pq->tail->next = newnode;
		//再将尾指针指向新结点
		pq->tail = newnode;
	}
}

//出队列函数
void QueuePop(Queue* pq)
{
	assert(pq);
	
	//队列为空时不能出数据（或者使用断言）
	if (pq->head == NULL)
	{
		return;
	}
	else
	{
		//先记录头指针的下一个结点
		//需要先判断下一个结点是不是空
		if (pq->head->next == NULL)
		{
			free(pq->head);
			pq->head = pq->tail = NULL;
		}
		else
		{
			QNode* next = pq->head->next;

			//释放头指针指向的结点
			free(pq->head);
			//将头指针指向下一个结点，成为新的队头
			pq->head = next;
		}
	}
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//队为空不能取数据

	return pq->head->data;
}

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//队为空不能取数据

	return pq->tail->data;
}

//求队长（数据个数）
int QueueSize(Queue* pq)
{
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;//队列为空返回true，否则返回false
}

test.c:

//测试各个函数功能
void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	QueueDestory(&q);
}

int main()
{
	test();
	return 0;
}

感谢阅读！^_^