最近想回过头来看看以前写的一些代码，做的一些项目，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些笔记和代码，这些代码有的是参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。

                                                                                                                                    ------Shawn

数据结构中最简单和基本的三中数据结构就是表（List），栈（Stack）和队列（Queue），并且，每一个有意义的程序都会使用至少一种这样的数据结构。这篇文章将简单介绍三种基本数据结构以及在C++上的实现。

3.队列（Queue）

队列也是表，然而，使用队列时插入是在一端进行，而删除是在另外一端进行的。

先进先出。

3.1队列模型

3.2 队列的操作

队列通常提供的操作：

入队： 通常命名为push()

出队： 通常命名为pop()

求队列中元素个数

判断队列是否为空

获取队首元素

3.3 队列的存储结构

队列与栈一样是一种线性结构，因此以常见的线性表如数组、链表作为底层的数据结构。

本文中，我们以数组、链表为底层数据结构构建队列。

3.4队列的数组实现

对于每一个队列数组结构，保留一个数组the array以及位置front和back，代表队列的两端。此外，还需要记录队列的大小，即记录的元素的个数currentsize

要enqueue元素x，可将currentsize和back增1，然后置theArray[back]=x.

要dequeue一个元素，可以置返回值为theArray[front],将currentsize减1，再将front增1.

潜在的问题：

 多次执行enqueue后，队列似乎满了。

解决方法：

只要front或back到达数组的尾端，就绕回到开头。以循环数组实现。

以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作：

可能有人说，把队首标志往后移动不就不用移动元素了吗？的确，但那样会造成数组空间的“流失”。

我们希望队列的插入与删除操作都是O(1)的时间复杂度，同时不会造成数组空间的浪费，我们应该使用循环队列。

所谓的循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

那么我们如何判断队列是空队列还是已满呢？

栈空： 队首标志=队尾标志时，表示栈空，即红绿两个标志在图中重叠时为栈空。

栈满 : 队尾+1 = 队首时，表示栈空。图三最下面的队列即为一个满队列。尽管还有一个空位，我们不存储元素。

代码实现：

3.5 队列的链实现

链队列是基于链表实现的队列，它不存在数组的O（n）的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首，哪头做队尾。

显然我们应该以链表头部为队首，链表尾部为队尾。存储一个指向队尾的指针，方便从链表尾插入元素；使用带头节点的链表，方便从链表头删除元素。

代码实现：

参考

循环队列：https://github.com/huanzheWu/Data-Structure/blob/master/LoopQueue/LoopQueue/LoopQueue.h

链队列：https://github.com/huanzheWu/Data-Structure/blob/master/LinkQueue/LinkQueue/LinkQueue.h