【数据结构】队列的概念、结构和实现详解

        本文来介绍一下数据结构中的队列，以及如何用C语言去模拟实现。 

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

特点：数据先进先出FIFO（first in first out）。

入队列：进行插入操作，这一端称为队尾。

出队列：进行删除操作，这一端称为队头。

 数据的入栈顺序是1234，出来顺序也是1234，先进先出。

队列的应用场景很多，比如说去医院排号，先来先叫号，或者比较火爆的饭店，想吃的话也要等号，也是先来先排号先吃。

2.实现队列的底层方法选择

两种底层结构，数组和链表。

数组在这里一定是不选的，因为数组无论怎样都实现不好一端进一端出的情况。 

所以我们要考虑的是链表，链表按理来说是可以实现的，但是我们选单向链表还是双向链表？如果单向链表可以实现，尽量选单向的，因为双向链表一个节点存两个指针，单链表只存一个，节省内存。

 3.队列的实现

3.1 准备工作

我们选择采用函数声明和定义分离的方法，所以首先要新建一个头文件queue.h，两个源文件queue.c 和 test.c。

 点开queue.h文件，在这个文件里面我们要先加上后面会用到的相关头文件，在这里定义队列的结构，以及给类型和栈的结构取别名。

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

typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

因为是单链表，所以我们找尾节点的效率会比较低，每插入一个数据就要找一次尾节点。所以我们需要两个指针，一个指向头节点，一个指向尾节点。

并且由于形参的改变不影响实参，所以想改变队列还要传的是phead和ptail的指针，就是二级指针了。

//插入
void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
//删除
void QueuePop(QNode** pphead, QNode** pptail);

但是我们很多函数都要用到这两个指针，每次都传两次指针就会很麻烦，所以我们把这两个指针一起存在一个结构体Queue里面。顺便这个结构体改个名。

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
}Queue;

有了Queue这个结构体，我们在传参数的时候就只要传这个结构体的指针就可以了。

void QueuePush(Queue* pq, QDataType x);//插入
void QueuePop(Queue* pq);//删除

并且此时我们还不需要用二级指针了。

为了方便后续的函数实现，我们还可以在结构体Queue里面多加一个成员变量size，记录队列的有效个数。

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

3.2 初始化和size

在queue.h中进行声明。

void QueueInit(Queue* pq);//初始化
int QueueSize(Queue* pq);//个数

在queue.c中进行实现。 

初始状态下，头节点和尾节点都是NULL，队列里面还没有数据，所以size初始化为0。

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

我们前面在Queue结构体里面增加了size这个成员变量，QueueSize的实现就方便多了。 

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

3.3 尾部插入

在queue.h中进行声明。

void QueuePush(Queue* pq, QDataType x);//插入

在queue.c中进行实现。 

首先我们要malloc出一个节点，并检查是否申请成功，用于尾插。用为整个队列只有这一个地方需要插入，所以创建节点就不需要单独封装成一个函数了。

void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

}

然后对这个新节点进行操作。

void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	//处理新节点
	newnode->next = NULL;
	newnode->val = x;
	
}

现在就可以插入到队列里了。插入的时候分两种情况，一是插入时队列还没有数据，二是插入时队列里有数据，不管有没有，插入数据之后size要+1。

void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	//处理新节点
	newnode->next = NULL;
	newnode->val = x;
	if (pq->ptail == NULL)//队列一个数据都没有
	{
		pq->phead = pq->ptail = newnode;
	}
	else//队列有数据
	{
		pq->ptail->next = newnode;//尾插
		pq->ptail = newnode;//更新尾节点
	}
	pq->size++;//有效数据++
}

在test.c中测试初始化和插入的代码。

void test1()
{
	Queue q;
	QueueInit(&q);//初始化
	QueuePush(&q, 1);//尾部插入
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
}

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

3.4 头部删除

在queue.h中进行声明。

void QueuePop(Queue* pq);//删除

在queue.c中进行实现。 

首先链表不能为空，要有节点，才能删。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

}

我们进行头删之前，需要保存头结点的下一个节点，不然释放头节点之后找不到下一个节点了。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);
	QNode* next = pq->phead->next;//保存下一个节点

}

然后释放头节点，更新phead，size减1。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);
	QNode* next = pq->phead->next;//保存下一个节点
	free(pq->phead);
	pq->phead = next;
	pq->size--;
}

但是如果此时队列里只剩一个节点了呢？我们简单分析一下。

 此时的ptail就是野指针了。所以我们还要处理一下这个ptail。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);
	if (pq->phead->next == NULL)//一个节点
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else//多个节点
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

在test.c中测试代码。

void test2()
{
	Queue q;
	QueueInit(&q);//初始化
	QueuePush(&q, 1);//尾部插入
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePop(&q);//头部删除
}

3.5 获取队头和队尾的数据

在queue.h中进行声明。

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

 在queue.c中进行实现。 

获取队头数据就直接返回头节点phead的数值。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

获取队尾数据就直接返回尾节点ptail的数值。

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

在test.c中测试代码。

void test3()
{
	Queue q;
	QueueInit(&q);//初始化
	QueuePush(&q, 1);//尾部插入
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	printf("%d\n", QueueFront(&q));
	printf("%d\n", QueueBack(&q));
}

3.6 判空

在queue.h中进行声明。

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

void QueueDestroy(Queue* pq);//销毁

在queue.c中进行实现。 

size等于0的时候，队列就是空队列，不为0就不为空。

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

队列的销毁就是从头到尾遍历，一个一个释放就好了。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

在test.c中测试代码。

队列的相关知识就介绍到这里，我们下篇再见~