很久没有写文章了。因为放假了嘛，给自己稍微放松了一下，所以最近的更新很慢。呜呜下一次一定改。然后咧。今天我想与大家分享的是队列。虽然这个知识点我们应该在讲了堆的实现就应该写的，但是后面忘了，以为自己是写了的。但是昨天看了看自己写的目录才发现自己忘了写队列了。所以今天把队列补上，并且当我们写了队列后我们会写队列与堆的相互实现。

队列的含义

        大家如果一直有在看我的文章的话可能已经了解了队列的含义了，但按照规矩我还是向大家解释一下队列的含义。队列咧。就像我们排队买奶茶一样。先进行排队的人可以先买后进行排队的人后买，我们大家都遵守的规则，然后队列也遵守这个规则。就好比我们的堆是后进先出一样。队列必须遵守这个。还有就是队列他只能头删和尾插。当然还有一些其他的基本上做比如说什么判空或者返回头元素之类的。那么接下里我们就来康康实现队列需要怎么搞。

实现队列

     创建结构体

       我们都说了，队列与堆可以相互出现，其实就代表他们的大体结构是差不多的。就只需要注意一下他们的定义的区别就可以了。那么我们应该也会要像他们一样先创建一个结构体来储存数据。但是我们创建结构体又不能指向开始一样只创建一个结构体。因为如果我们只创建一个结构体的话，我们需要数据节点为头节点，还需要再一个数组的个数还需要一个尾节点。然后还有指向的一个数据。如果都放在一个这个里面的话会比较麻烦，但是我们可以将头节点和尾节点直接单独拎出来。但是我们创建的结构里面的数据还是以最开始的节点为基准。大家可以先看一下我的代码是怎么样的：

typedef int QDateType;//队列存储数据类型

typedef struct QueueNode //队列元素节点
{
	QDateType val;//队列的元素个数
	struct QueueNode* next;//指向的下一个节点
}QueueNode;

typedef	struct Queue //队列
{
	QueueNode* head;//头节点
	QueueNode* tail;//尾节点
}Queue;

        大家可以稍微看一下，我这个可能会比较抽象，但确实就像这样子。就好像创建了一个结构体，然后在他结构体里面再分化一下。 

队列的初始化

       对于队列的初始化，这样就很是很简单的，因为我们只需要将它的头节点和尾节点置为空就可以了。

void QueueInti(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

队列的销毁

       相较于队列的初始化，队列的销毁就相对会麻烦一点。因为我们首先需要判断是否为空指针。然后再创建一个指针为头指针，依次销毁置空。然后再将头尾节点置为空就结束了。虽然也是很简单的，但是相较于初始化确实多了几行代码。

void QueueDestory(Queue* pq)
{
	assert(pq); //防止pq为空指针
	QueueNode* cur = pq->head;//创建一个零时节点以免对代码实现干扰
	while (cur)
	{//依次销毁，并且换到下一个
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->tail = pq->head = NULL;//头尾置为空
}

队列的入队列 

      我们在前面说我们队列是先进先出的，那么入队列肯定也是依次从头节点开始进入。所以我们对入队列就是需要开辟一个新的节点来存储数据。然后将他放在尾节点的后面然后将尾节点移位，那么这个头插就结束了。但是我们还需要思考的是并不是我们每一次使用开始队列就有数据了。那我们是不是需要区分一下，如果对于你开始里面没有数据应该怎么处理？就是当头节点和尾节点都是同一个的时候，还没有数据的时候。那么我们是不是应该让头节点和尾节点的同时置于相同的数据。因为这个时候我们头和尾节点是相同的呀。所以这也是我们需要考虑的一点。

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq); //防止pq为空指针

	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));//创建新节点存放数据
	if (NULL == newNode)//判断是否创建好了
	{
		printf("malloc error\n");
		exit(-1);
	}
	newNode->val = x;
	newNode->next = NULL;//开辟一个新节点存储数据

	if (pq->tail == NULL)//判断是否为空队列
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

队列的出队列

       我们在前面实现了尾插后，接下来就应该实现头删了。既然是头删，那么我们是不是要思考一下。假如只有一个指针的话，就是例如我刚插入一个之后，我就立马删除了。已经有很多个元素了，我再删除这两种区别。所以我们就需要分别的对待这两件事情。大家想一想，如果只有一个指针的话，我们是不是只需要将头和尾直接置为空就可以了？因为只有一个节点嘛，然后我删除一个节点，那是不是周围空了？所以就只需要将头和尾置空一下就好了。然后还有就是正常情况下，我们不能直接将头删掉，如果删掉的话是不是就不能找到下一个节点了？所以我们正常的情况下需要创建一个临时节点，然后再来删除。

void QueuePop(Queue* pq)
{
	assert(pq);//防止pq为空指针
	assert(pq->head && pq->tail); //防止队列为空队列
	if (pq->head->next == NULL)//假如只有一个节点的话，就全部置为空
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//有多个节点就创建一个零时节点然后来释放置空
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

队列的头元素

        对于队列的取头元素这是比较简单的，因为我们在最开始创建的时候就已经写了一个头节点和尾节点了。只需要判断节点是否为空就可以了。

QDateType QueueFront(Queue* pq)
{
	assert(pq);//防止pq为空指针
	assert(pq->head && pq->tail); //防止队列为空队列

	return pq->head->val;
}

   队列的判空

       关于队列的判空呢其实也是比较简单的。如果当头节点和尾节点相同，并且为都为空的话，那么肯定就是空的队列了。当然我们还是需要判断指针是否为空。

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

队列的元素个数

         对于判断队列的元素个数，我的这个方法其实是比较麻烦的，我是像在需要队列个数的时候重新执行一遍便利的过程，这样我们就可以得出元素的个数了。但是也可以在创建结构体的那个地方再加一个size反正就是一个计数的就可以了，那么如果当我们计数的为零，那么就说明是队列为空，并且对于我们计算元素个数也是很方便的，当然这也是另外一种的方法，我这里就先写我原本的遍历一遍就好了，大家如果感兴趣的话，后面可以尝试一下。

int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;//创建一个临时节点，更加方便操作
	int count = 0;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;//返回个数
}

总结

       好了，上面就是关于队列的大部分使用方法了。当然还有很多对于这个的延伸，这就可能会用在后面的题目上。后面的面试题之类的。那可以多尝试一下练题，然后就能加深一下对队列的一些的相关知识的巩固。那么接下来来我就这样所有的代码给大家看一下。

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

typedef int QDateType;

typedef struct QueueNode
{
	QDateType val;
	struct QueueNode* next;
}QueueNode;

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

void QueueInti(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->tail = pq->head = NULL;
}

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

	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newNode)
	{
		printf("malloc error\n");
		exit(-1);
	}
	newNode->val = x;
	newNode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}

}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->val;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	int count = 0;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}