初阶数据结构------队列的实现
目录
前言
队列的介绍
队列的实现
声明
实现
初始化
销毁
入队列
出队列
队列中元素个数
队列是否为空
取队尾元素
取队首元素
前言
此博客较为详细地讲解了如何基于C语言中的链表，实现一种非常重要的数据结构--队列。
队列的介绍
首先，什么是队列呢？队列是一种特殊的线性表。所谓线性表是一类在逻辑结构上连续的数据结构的统称。
队列只允许在其一端插入数据，即入队列；在其另一端删除数据，即出队列。插入数据的一端被称为队尾，删除数据的一端被称作队头。同时队列还遵守FIFO（先进先出）原则，即不管数据先入几个再入几个，数据只有一种出队列的顺序。
队列的实现
那我们怎么具体实现队列呢？我们立刻能想到数组和链表两种方式。相比于数组，链表实现队列要更优一些。为什么呢？如果我们基于数组实现一个动态的队列除了每次扩容的消耗外，我们在删除数据时还要移动后面的元素，要麻烦许多。所以这里我们讲的是基于链表实现一个队列。
那我们怎么基于链表实现队列呢？我们假设将链表的头作为队头，链表的尾作为队尾，这里我们需要两个指针，一个指向队头，另一个指向队尾。在入队列时，我们只需要申请一个新的节点，让尾结点的next指针指向新节点，再让rear指针指向新申请的节点即可。那删除数据呢？我们只需要把第一个节点释放了，再改变head指针的指向即可。经过这么一分析，链表很好的契合了队列的要求。
声明
下面就看具体的代码实现部分了。
在Queue.h文件中我们首先包含一下后续会使用到的头文件。
接着我们来定义队列的节点，每一个节点都包含两个成员：存的数据val和下一个节点的地址next。
接下来注意了！我们再设计一个新的结构体struct Queue。
那我们为什么要设计这个结构体呢？这就需要结合我们需要实现的一些方法来说了。
我们后续会实现一些有关队列的方法，包括初始化、销毁、入队列、出队列等等。在实现这些方法，我们就以队列的初始化为例。要将队列初始化，我们就要把head指针还有rear指针都置为空。所以在函数中我们如果想通过形参的改变来影响实参，这个时候我们就需要传变量的地址了，在这里也就是二级指针。也就是说我们需要传递两个二级指针。这样不论在使用还是维护时都非常的麻烦。所以，我们这里就设计一个结构体struct Queue，然后把两个指针都放在这个结构体里面，然后后续我们直接传递结构体的地址就能在函数中改变head和rear这两个指针的指向了。
那么我为什么又在结构体中加了一个成员size呢？这依然和我们后续会实现的方法有关。我们后续会实现一个方法，也就是展示队列中的元素个数。正常来说的话，我们每次在调用这个函数的时候都要从头遍历一次我们的链表，时间复杂度为O（N），这样的未免有些麻烦。
所以我们就在设计的结构体中加一个成员size，后续每次入队列时我们都让size加一，出队列时再让它减一，这样在实现展示队列中的元素个数时，我们直接return size就行了。
实现
前面铺垫了那么多，我们就可以直接进入代码部分了。我们就开始一个一个的实现我们的方法。
初始化
首先是初始化，这里没什么好说的，直接将head和rear指针置空，再把size置为0即可。
销毁
接下来是队列的销毁
在销毁队列时就有个细节要注意了，我们的队列是在堆上申请的，如果我们只是将head和rear指针置空但是堆上的队列并没有销毁，这要就会导致内存泄漏。所以我们要先释放队列的每个节点再把指针置空。
入队列
然后就是入队列了。入队列分为两种情况。一种是队列为空，另一种是队列不为空。队列为空时我们就要同时改变head和rear指针的指向了。队列不为空，我们只需要让尾节点指向新节点，再让rear指针指向新的尾节点即可。最后不要忘了让size++。
出队列
再就是出队列。注意队列的数据都是从队头出队列的。首先队列不能为空，我们用assert暴力判断一下。我们保存一下第一个节点的下一个节点的地址再把第一个节点释放了最后再改变head指针的指向即可。注意！！！这里有坑！当队列只有一个节点时我们把节点释放后，改变了head指针的指向，但是rear指针并没有改变，它指向的空间已经被释放了，rear指针也就成了野指针。后续在使用的过程中后有可能会出现非法访问的问题。所以这里我们得判断一下，如果只有一个节点那么rear指针也要置空！最后不要忘了让size--。
队列中元素个数
这里没什么好说的，直接return obj中的size即可。
队列是否为空
我们直接利用size来判断即可。
取队尾元素
先判断一下obj是否有效以及队列是否为空，再直接返回rear节点中的值即可。
取队首元素
同样，我们先判断一下，再直接返回head节点中的值即可。
以上就是本篇博客中的所有内容了，希望对大家有帮助，有问题也欢迎指正交流。