一.什么是队列

队列和栈一样，也是一种特殊的线性表，不同于栈的是：

队列要求数据只能从一端插入，从另一端删除。因此队列具有先进先出的特点，就类似于我们生活中的排队。

那么关于队列也有两个专用名词：

• 队头：进行插入操作的一端，称为队头，执行入队列操作。
• 队尾：进行删除操作的一端，称为队尾，执行出队列操作。

---

二.队列的实现

根据我们现在对队列的了解，要实现一个好的队列，就需要在头删和尾插上更加便捷。

所以我们首先排除使用数组，头删比较麻烦，那么就在单链表和双链表里选。

双链表无论是实现栈还是队列都可以，但是都有点小题大作，仅仅是对头尾的单独操作，不需要使用两个指针，所以队列我们选择用单链表实现。

typedef int QDataType;

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

但是这样的实现方法有一个问题，就是必须要使用二级指针才能对队列进行操作。

但是我们不喜欢用二级指针，该怎么避免使用呢？？？ 

其实很简单，如果是对结构体里的数据进行操作，我们只需要用结构体类型的一级指针即可，所以我们再定义一个嵌套结构体，单独用来记录队列的头、尾，就可以使用一级指针来操作啦。

typedef int QDataType;

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

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

同时我们为了方便记录队列长度，额外定义size变量。

---

三.队列的操作

1.队列初始化

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

---

2.入队

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush->malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

入队，实际上就是尾插。

值得注意的一点是，我们要考虑一下队列是否为空。

因为如果队列为空，那么入队之后，对头和队尾都需要指向该数据，但是如果队列已经存在数据，那就只需要让原队尾指向新数据，再让新数据称为队尾即可。

---

3.出队

//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	//判空
	assert(pq->phead);
	QNode* head = pq->phead;
	pq->phead = pq->phead->next;
	free(head);
	head = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

出队，也就是头删。

删除数据肯定首先断言是否为空队列。

其次在考虑，如果只有一个数据，删除之后，队列为空，但是好像ptail还指向该数据的空间，这样ptail就变成了野指针。所以要进行一次判断，让phead和ptail都要指向NULL。

那么判断条件就是队头是否为空，为空就说明队列为空。

接下来的操作就都很简单啦，博主将直接展示代码。

---

4.队列长度

//队列长度
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

---

5.队头数据

//队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->data;
}

---

6.队尾数据

//队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->data;
}

---

7.判断空队列

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

这里是一个技巧，如果phead为空就说明是空队列，返回false，反之返回true。 

---

8.销毁队列

//销毁
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;
}

---

9.测试

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	int size = QueueSize(&q);
	printf("size = %d\n", size);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return 0;
}

这里博主尽可能多的展示了大部分操作，其他操作就靠小伙伴们下去自己制作并测试啦。

结果如下：

---

四.完整代码展示

1.Queue.h

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

typedef int QDataType;

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

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

//初始化
void QueueInit(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//队长
int QueueSize(Queue* pq);
//队头数据
QDataType QueueFront(Queue* pq);
//队尾数据
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

---

2.Queue.c

#include "Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush->malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	//判空
	assert(pq->phead);
	QNode* head = pq->phead;
	pq->phead = pq->phead->next;
	free(head);
	head = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}
//队列长度
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
//队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->data;
}
//队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->data;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//销毁
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;
}

---

五.总结

队列也是在单链表的基础上进行另类操作，没有附加其他实质性有难度的地方，所以相信大家只要掌握好了单链表的知识，对于队列的理解和实现也是不在话下。