数据结构线性表—

数据结构线性表——队列

前言：哈喽小伙伴们，这篇文章我们继续来学习线性表的第五章——队列。

世上无难事，只怕有心人。数据结构看似有很多种类型，但是它们之间都有着千丝万缕的联系。

只要我们能够耐心学习思考，就一定能够将知识串通起来，轻松拿下。

一.什么是队列

二.队列的实现

三.队列的操作

1.队列初始化

2.入队

3.出队

4.队列长度

5.队头数据

6.队尾数据

7.判断空队列

8.销毁队列

9.测试

四.完整代码展示

1.Queue.h

2.Queue.c

五.总结

一.什么是队列

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

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

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

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

二.队列的实现

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

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

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

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。

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

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