数据结构——队列的模拟实现

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

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

一：队列简介

首先来认识一下队列：

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

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

队列的特点就是：队尾入，对头出，先进先出（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.题目一：

使用两个队列实现后入先出的栈

队列的特点是先入队的数据先出队，栈的特点是后入栈的数据先出栈。

我们可以使用两个队列来实现栈的功能。

我们先将1 2 3 4依次放入一个队列中，出数据的话要先出4，但是队列只能先出1 2 3.

这时候我们就要用到第二个队列，将1 2 3存放到第二个队列中，再出4就可以了。

下一步出3，先将1 2导入另一个空队列中就可以出3了。

如果要插入数据（数据进栈）的话就在有数据的那个队列尾部插入数据

依次进行，使用两个队列实现栈就完工了。

2.题目二：

使用两个栈实现先进先出的队列

队列的特点是先入队的数据先出队，栈的特点是后入栈的数据先出栈。

我们可以使用两个栈来实现队列的功能。

一个栈只管用来出数据，另外一个栈只管用来进数据。

比如：将数据1 2 3 4进入到一个栈中，由于队列的特性是先进先出，因此出数据的话要先出1，但按照栈的逻辑要先出4.因此此时要用到另外一个栈来导数据。将4 3 2导入另外一个栈中，然后出1。4 3 2就可以依次出栈了，入数据的话就只在另一个栈中入数据，当4 3 2全部出完后，再将入数据的栈中的数据导入出数据的栈中，这样往复，就可以实现使用两个栈来实现队列。

完：