队列

什么是队列

队列是一种 先进先出 的线性数据结构，其定义了队头和队尾两个端，限制只能从队头弹出数据，从队尾压入数据

队列在日常生活中也很常见，比如我们去食堂打饭的时候，人多就需要排队，排在前面的先打了饭走了，排在后面的需要等到前面的打完饭才能打饭

队列的类型

队列可以使用 数组 或者 链表 实现，使用数组实现的叫做顺序队列，使用链表实现的叫做链式队列。还有一些基于这两种队列实现的队列，比如：循环队列( 顺序队列不用数据搬移 )、阻塞队列( 入队出队可阻塞 )、并发队列( 线程安全 ) 等

数组实现队列

数组实现队列要点：

1. 入队 数据直接放到 tail指针 位置
2. 出队 将 head指针 后移就行，不用搬移数据，在 tail 指针到达数组末尾的时候一起搬移，效率更高

链表实现队列

链表实现队列要点：

1. 入队数据直接放到链表末尾
2. 出队直接将 head指针 后移

循环队列

基于数组可以实现循环队列，即在 tail指针 到达数组末尾的时候，再将其移动到数组头部，直到 数组只剩 tail指针一个空位

循环队列

循环队列主要是如何判断对空、队满，从上图可以看出，如果队满，tail指针 应该是在 head指针 '前面' 一个位置，所以当 (tail +1)%length === head 的时候，队列应该就是满了，因为判断的时候 tail指针 位置没有数据存放，所以循环队列在队满的时候 tail指针所在位置是放空的，队空的判断就是 head === tail

在实现的时候，要注意 head、tail指针 在赋值的时候 需要对数组长度进行取余，而不是单纯的+1，因为要从数组末尾再回到数组头部形成环

思考

1. 基于数组和链表实现的队列有何区别？

基于链表可以实现一个支持可以无限排队的无界列队，基于数组可以实现支持有限排队的有界队列