什么是队列？
队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
这是维基百科上对队列的解释，队列和栈一样，也是一种受限的线性表结构。队列有两个操作，入队和出队，队列可以用数组和链表来实现，用数组实现的称为顺序队列，用链表实现的称为链式队列。
入队和出队操作
与栈不同的是，队列中有两个指针，分别为队列头指针 head 和队列尾指针 tail 。当 head == tail 时，队为空；当 tail == n 时，队满，不能再加入新的元素。当元素出队时， head + 1，当元素入队时，tail + 1。假设用数组实现队的操作，下面用一段Python代码描述一下具体过程(自己写的代码，可能有不对的地方)。
class Queue(object):
def __init__ (self,head,tail,arr):
self.head = head #传入的头指针
self.tail = tail #传入的尾指针
self.arr = arr #传入的队列
self.len = len(arr)
def enqueue (self,element):
if (self.tail == self.len-1): #判断队列是否满
print ("The queue is full!")
return self.arr,self.head,self.tail
self.arr[self.tail] = element #在队尾插入新的元素
self.tail += 1#尾指针加 1
print ("The element entered")
return self.arr,self.head,self.tail #返回新的队列
def dequeue (self):
if (self.head == self.tail): #判断队列是否为空
print ("The queue is empty!")
return self.arr,self.head,self.tail
headData = self.arr[self.head]
print ("The head data is %d"%(headData)) #输出队头元素
self.head += 1#头指针加 1
return self.arr,self.head,self.tail #返回新的队列
work = Queue(0,1,[1,2,0])
Arrin,Hin,Tin = work.enqueue(5)
for i in range(Tin-Hin):
print (Arrin[Hin+i]) #打印入队后新的队列
#Arrout,Hout,Tout = work.dequeue()
#for j in range(Tout-Hout):
# print (Arrout[Hout+j]) #打印出队后新的队列
仔细看一下，会发现。入队和出队，head 指针和tail 指针不断移动的，当 tail == n 时 ，不管数组有没有存储空间，就不能再有新元素入队了。前面学习数组的时候，遇到这种问题，需要用数据搬移来解决，但是每一次搬移，时间复杂度都是 O(n)，为了降低平均时间复杂度，只有在tail ==n & head !=0 的情况下，才触发一次数据搬移，具体代码就不写了，画张图看一下就很清晰了。
循环队列
还有一种不需要数据搬移的队列，叫做循环队列，它将队列转变成一种抽象的环形结构，如图所示。
当新的元素入队时， tail 不会更新为 8，而是更新为 0，后面新入队的元素一次放入 0、1、2，当 tail 为 3 时，队满。
具体怎么判断堆满呢，根据规律可得，当 (tail + 1)%n == head 时，队满，这样的话会浪费一个数组的存储空间。具体实现代码如下。
class Queue(object):
def __init__ (self,head,tail,arr):
self.head = head
self.tail = tail
self.arr = arr
self.len = len(arr)
def enqueue (self,element):
if ((self.tail+1)%self.len == self.head): #判断队列是否满
print ("The queue is full!")
return self.arr,self.head,self.tail,self.len
if (self.tail == self.len-1):
self.arr[self.tail] = element
self.tail = 0
else :
self.tail += 1
print ("The element entered")
return self.arr,self.head,self.tail,self.len
def dequeue (self):
if (self.head == self.tail): #判断队列是否为空
print ("The queue is empty!")
return self.arr,self.head,self.tail,self.len
headData = self.arr[self.head]
print ("The head data is %d"%(headData))
if (self.head == self.len-1):
self.head = 0
else:
self.head += 1
return self.arr,self.head,self.tail,self.len
work = Queue(4,7,[1,2,3,4,5,6,7,8])
#Arrin,Hin,Tin,Lin = work.enqueue(5)
#for i in range(Lin-Hin+Tin):
# if (Hin+i >= Lin):
# print (Arrin[Hin+i-Lin])
# else:
# print (Arrin[Hin+i])
Arrout,Hout,Tout,Lout = work.dequeue()
if (Tout < Hout):
for j in range(Lout-Hout+Tout):
if (Hout+j >= Lout):
print (Arrout[Hout+j-Lout])
else:
print (Arrout[Hout+j])
else:
for j in range(Tout-Hout):
print (Arrout[Hout+j])
阻塞队列和并发队列
阻塞队列 就是在阻塞的基础上加入了阻塞操作。就是，当队为空时，出队阻塞，当有数据时阻塞才结束。当队满时，入队阻塞，当队列中有空闲位置时阻塞才结束。
这就相当于定义了一个生产者-消费者模型，需要协调生产者和消费者的个数，来提高数据处理的效率。
例如，可以配置多个消费者来应对一个生产者，这样会涉及到多线程的问题，多线程操作，需要在数据入队或出队时加锁，同一时刻只允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。
小结
队列是一种先进先出的数据结构，可以用链表和数组实现，针对响应时间比较敏感的系统，数组更合适，但要设计好队列的大小。对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”来实现请求排队。
