队列实现方式、效率分析及应用场景

一、什么是队列

队列是一种特殊的线性表，遵循先入先出、后入后出的基本原则，一般来说，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，但是Java的某些队列允许在任何地方插入删除（Python则不能），这是因为这些队列实现了Collections接口；比如我们常用的LinkedList集合，它实现了Queue接口，因此，我们可以理解为 LinkedList 就是一个队列；再比如优先级队列PriorityQueue实现了Queue接口，Queue接口中的remove()方法删除对头元素，同时实现了Collection接口，Collection接口提供了remove(Object o)方法用于删除队列中任意存在的元素，但该方法效率较低。

二、队列特性

队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分；

阻塞和非阻塞

阻塞队列
入列(添加元素)时，如果元素数量超过队列总数，会进行等待（阻塞），待队列的中的元素出列后，元素数量未超过队列总数时，就会解除阻塞状态，进而可以继续入列；

出列(删除元素)时，如果队列为空的情况下，也会进行等待（阻塞），待队列有值的时候即会解除阻塞状态，进而继续出列；
阻塞队列的好处是可以防止队列容器溢出；只要满了就会进行阻塞等待；也就不存在溢出的情况；
只要是阻塞队列，都是线程安全的；

非阻塞队列
不管出列还是入列，都不会进行阻塞.
入列时，如果元素数量超过队列总数，则会抛出异常，出列时，如果队列为空，则取出空值；

一般情况下，非阻塞式队列使用的比较少，一般都用阻塞式的对象比较多；阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法：

出队阻塞方法 ： take()
入队阻塞方法 ： put()

有界和无界

有界：有界限，大小长度受限制
无界：无限大小，其实说是无限大小，其实是有界限的，只不过超过界限时就会进行扩容，就行ArrayList一样，在内部动态扩容

单向链表和双向链表

单向链表 ： 每个元素中除了元素本身之外，还存储一个指针，这个指针指向下一个元素；

双向链表 ：除了元素本身之外，还有两个指针，一个指针指向前一个元素的地址，另一个指针指向后一个元素的地址；

三、Java队列接口继承图

四、Java队列常用方法

队列除了基本的 Collection 操作外，还提供特有的插入、提取和检查操作(如上)。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的；在大多数实现中，插入操作不会失败。

Queue是java中实现队列的接口，它总共只有6个方法，我们一般只用其中3个就可以了。Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList。

Queue的6个方法分类：

• 压入元素（添加）：add()、offer()
  相同：未超出容量，从队尾压入元素，返回压入的那个元素。
  区别：在超出容量时，add()方法会对抛出异常，offer()返回false

• 弹出元素（删除）：remove()、poll()
  相同：容量大于0的时候，删除并返回队头被删除的那个元素。
  区别：在容量为0的时候，remove()会抛出异常，poll()返回false

• 获取队头元素（但不删除）：element()、peek()
  相同：容量大于0的时候，都返回队头元素。但是不删除。
  区别：容量为0的时候，element()会抛出异常，peek()返回null。

	抛出异常	返回特殊值
插入	add(e)	offer(e)
删除	remove()	poll()
检查	element()	peek()

知识点： offer、poll、remove、element、peek 其实是属于Queue接口。

五、队列实现方式与效率分析

数组队列：通过数组（可变数组）实现一个队列；

数组是连续存储，添加元素、删除元素很慢，时间复杂度O(n)（这是因为添加元素需要动态扩容，删除某位置元素后，需要将其后元素整体前移）；改查很快（不需要改变数据结构）

链表队列：通过链表实现一个对列；

链表是非连续存储，增删很快，添加删除元素的时间复杂度都是O(1)；但是改查很慢，因为没有索引，需要遍历链表找到元素位置进行删除。

栈队列：通过两个栈实现一个队列；

在20万数据循环操作下，链表实现的队列最快，是栈队列的2572倍，是数组的643倍。这个数值具体看设备算力，这里只做参考。

六、队列的应用场景

用于解决图和树等数据结构中的搜索问题。
广度优先搜索：广度优先搜索可以通过队列来实现对节点的遍历，通常就会从搜索候补中选择最早的数据作为下一个顶点。此时，在候补顶点的管理上就可以使用队列。

Dijkstra算法：优先队列

A*算法：优先队列

七、Python中队列与优先级队列使用

Python的Queue模块中提供了同步的、线程安全的队列类，包括FIFO（先入先出)队列Queue，LIFO（后入先出）队列LifoQueue，和优先级队列PriorityQueue。这些队列都实现了锁原语，能够在多线程中直接使用。可以使用队列来实现线程间的同步。

常用方法：

• Queue.qsize() 返回队列的大小
• Queue.empty() 如果队列为空，返回True,反之False
• Queue.full() 如果队列满了，返回True,反之False，Queue.full 与 maxsize 大小对应
• Queue.get([block[, timeout]])获取队列，timeout等待时间
• Queue.get_nowait() 相当于Queue.get(False)，非阻塞方法
• Queue.put(item) 写入队列，timeout等待时间
• Queue.task_done() 在完成一项工作之后，Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务，接下来task_done()调用告诉队列该任务已经处理完毕。
• Queue.join() 实际上意味着等到队列为空，再执行别的操作

import queue

queue = queue.Queue()

添加元素至队列

queue.put("zhangsan")

查看队列元素

print(queue) # 直接打印队列不行
print(queue.queue)

<queue.Queue object at 0x0000022B05E98430>
deque(['zhangsan'])

判断元素是否在队列中

print("zhangsan" in queue.queue)

True

删除队头元素

print(queue.get())
print(queue.queue)
print(queue.qsize)

zhangsan
deque([])
<bound method Queue.qsize of <queue.Queue object at 0x0000022B05E98430>>

判断队列是否为空

print(queue.empty())

True

优先级队列的使用
创建优先级队列

import queue
queue = queue.PriorityQueue()

添加元素至优先队列，查看队列元素

# 添加元素至优先队列
queue.put((3,"古力热巴"))
queue.put((2,"马儿扎哈"))
queue.put((1,"迪丽热巴"))
queue.put((9,"仓央嘉措"))
# 查看队列元素
print(queue.queue)

[(1, '迪丽热巴'), (3, '古力热巴'), (2, '马儿扎哈'), (9, '仓央嘉措')]

判断元素是否在队列中

print((1,"迪丽热巴") in queue.queue)

True

删除并返回队头

# 删除队头
print(queue.get())
print(queue.queue)

(1, '迪丽热巴')
[(2, '马儿扎哈'), (3, '古力热巴'), (9, '仓央嘉措')]

参考：
https://blog.csdn.net/xijinno1/article/details/132114694