大家好，上一篇博客我带领大家进行了数据结构当中的栈的模拟实现

今天我将带领大家实现一个新的数据结构————队列

一：队列简介

首先来认识一下队列：

队列就像我们上学时的排队一样，有一个队头也有一个队尾。

有人入队的话就从对尾入队，出队只能从对头出队，队头出队之后后面的人才可以选择出队。

队列的特点就是：队尾入，对头出，先进先出（first in first out）（先入队的先出队）。

1 2 3 4 入——1 2 3 4出。

队列的模拟实现是选择数组还是链表呢？

队列的特定规则需要两个指针分别指向首元素和尾原元素，如果选用数组的话，删除队首的数据就比较复杂（向前覆盖，时间复杂度为O（N））。

相较于数组，使用链表删除队首的数据就简单了很多，因此我们选择通过链表的形式来实现队列。

给出两个指针（一个把住头，一个把住尾），一个指向队首结点（负责队首出数据），一个指向队尾结点（负责队尾插入数据）。

二：队列的模拟实现

0.队列结构题的创建

与前面几个数据结构相比，队列这一数据结构需要两个指针，一个指向队首，一个指向队尾。

这里为了方便，将两个结点指针用另一个结构体分装。（否则的话每次传参传两个结点指针变量就很麻烦）。

size表示队列中结点个数。

2.队列的初始化

队列的模拟实现使用的是链表，队列中的数据是存储在链表的结点中的，因此，队列的初始化就是先给上两个空指针，后续有了结点之后再使用。

3.队尾插入数据（入队）

插入数据首先要开辟一个结点的空间用来存储数据。

插入数据之前首先要判断是否队列为空：

如果队列为空，就让两个指针都指向新结点。

如果队列不为空，队头结点不动，建立队尾结点与新结点之间的关系。

4.队头删除数据（出队）

删除数据就要先断言是否有数据

删除数据就是改变头结点指针的指向关系。

这里也要分两种情况进行讨论：

如果队列中只有一个结点，直接free就好了。

如果队列中不仅仅只有一个结点，free之前要先保留第二个结点的位置，否则后续就找不到了。

5.求队列中的数据个数

6.获取队首数据

想要获取队列中的数据就先要断言判断队列不能为空。

7.获取队尾数据

想要获取队列中的数据就先要断言判断队列不能为空。

8.队列的销毁

队列的销毁和单链表的销毁类似，还是从前到后，依次free

注意：free掉前一个结点之前一定要保留下一个结点的位置，否则free掉对头其余的结点就再也找不到了，会造成内存泄漏。

9.队列的测试

三：队列的经典题目

1.题目一：

2.题目二：

未完待续！！！！！！！！！！！