队列概览
# 队列概览
队列是一种线性表。不同于栈所服从的先进后出的原则，队列的原则是**先进先出**。
它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
进行插入操作的端称为队尾，进行删除操作的端称为队头，当队列中没有元素时，称为空队列
在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出
# 队列的种类
顺序队列
用数组实现的队列，叫做 顺序队列：
链式队列
用链表实现的队列，叫做 链式队列：
循环队列
循环队列是指队列是前后连成一个圆圈，它以循环的方式去存储元素，但还是会按照队列的先进先出的原则去操作。循环队列是基于数组实现的队列，但它比普通数据实现的队列带来的好处是显而易见的，它能更有效率的利用数组空间，且不需要移动数据。
普通的数组队列在经过了一段时间的入队和出队以后，尾指针 rear 就指向了数组的最后位置了，没法再往队列里插入数据了，但是数组的前面部分（front 的前面）由于旧的数据曾经出队了，所以会空出来一些空间，这些空间就没法利用起来
当然可以在数组尾部已满的这种情况下，去移动数据，把数据所有的元素都往前移动以填满前面的空间，释放出尾部的空间，以便尾部还可以继续插入新元素。但是这个移动也是消耗时间复杂度的。
而循环队列就可以天然的解决这个问题
循环队列也是一种线性数据结构，只不过它的最后一个位置并不是结束位。对于循环队列，头指针 front 始终指向队列的前面，尾指针 rear 始终指向队列的末尾。在最初阶段，头部和尾部的指针都是指向的相同的位置，此时队列是空的
- 优先队列
优先队列（priority Queue）是一种特殊的队列，它不遵守先进先出的原则，它是按照优先级出队列的。分为最大优先队列（是指最大的元素优先出队）和最小优先队列（是指最小的元素优先出队）。
一般用堆来实现优先队列
额外补充：队列存储结构的实现有以下两种方式：（两者的区别同样在于数据元素在物理存储结构上的不同。）
顺序队列：在顺序表的基础上实现的队列结构；
链队列：在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
# 栈和队列
不同点：
删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。
队列先进先出，栈先进后出。
顺序栈能够实现多栈空间共享，而顺序队列不能。
遍历数据速度不同。
栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来。
队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历无需开辟临时空间，速度要快的多。
相同点：
都是线性结构。
插入操作都是限定在表尾进行。
都可以通过顺序结构和链式结构实现。
插入与删除的时间复杂度与空间复杂度上两者均相同。