【数据结构】队列

什么是队列

• FIFO：先进先出
• 只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列实现

1.利用列表实现
注意：列表是线性表，队列在列表尾部入队（O(1)）,列表头部出队(O(n)),出队时间开销大。所以不推荐用列表

# 环形队列
class Queue:
    def __init__(self, size=100):
        self.queue = [0] * size
        self.size = size
        self.rear = 0
        self.front = 0

    def push(self, value):
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = value
        else:
            raise IndexError('Queue is filled')

    def pop(self):
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise  IndexError('Queue is empty')

    def is_empty(self):
        return self.rear == self.front

    def is_filled(self):
        return (self.rear + 1) % self.size == self.front

    def get_rear(self):
        return self.queue[self.rear]

    def get_front(self):
        return self.queue[self.front]

2.collections.deque模块

deque是双端队列（double-ended queue）的缩写

返回一个新的双向队列对象，从左到右初始化(用方法 append()) ，从 iterable （迭代对象) 数据创建。如果 iterable 没有指定，新队列为空。maxlen：Deque的最大尺寸，如果没有限定的话就是 None 。
Deque 支持线程安全，内存高效添加(append)和弹出(pop)，从两端都可以，两个方向的大概开销都是 O(1) 复杂度。
虽然 list 对象也支持类似操作，不过这里优化了定长操作和 pop(0) 和 insert(0, v) 的开销。它们引起 O(n) 内存移动的操作，改变底层数据表达的大小和位置。

• append(x)：添加 x 到右端。
• appendleft(x)：添加 x 到左端。
• clear()：移除所有元素，使其长度为0.
• copy()：创建一份浅拷贝。
• count(x)：计算 deque 中元素等于 x 的个数。
• extend(iterable)：扩展deque的右侧，通过添加iterable参数中的元素。
• extendleft(iterable)：扩展deque的左侧，通过添加iterable参数中的元素。注意，左添加时，在结果中iterable参数中的顺序将被反过来添加。
• index(x[, start[, stop]])：返回 x 在 deque 中的位置（在索引 start 之后，索引 stop 之前）。 返回第一个匹配项，如果未找到则引发 ValueError。
• insert(i, x)：在位置 i 插入 x 。如果插入会导致一个限长 deque 超出长度 maxlen 的话，就引发一个 IndexError。
• pop()：移去并且返回一个元素，deque 最右侧的那一个。 如果没有元素的话，就引发一个 IndexError。
• popleft()：移去并且返回一个元素，deque 最左侧的那一个。 如果没有元素的话，就引发 IndexError。
• remove(value)：移除找到的第一个 value。 如果没有的话就引发 ValueError。
• reverse()：将deque逆序排列。返回 None 。
• rotate(n=1)：向右循环移动 n 步。 如果 n 是负数，就向左循环。
  Deque对象同样提供了一个只读属性:

除了以上操作，deque 还支持迭代、封存、len(d)、reversed(d)、copy.copy(d)、copy.deepcopy(d)、成员检测运算符 in 以及下标引用例如通过 d[0] 访问首个元素等。 索引访问在两端的复杂度均为 O(1) 但在中间则会低至 O(n)。 如需快速随机访问，请改用列表。

Deque从版本3.5开始支持 __add__(), __mul__(), 和 __imul__() 。

 代码示例：

from collections import deque
Queue = deque(maxlen=3)
Queue.append(1)
Queue.append(2)
Queue.popleft()
Queue.count(2)
# Queue.clear()
print(Queue)
# deque([2], maxlen=3)
Queue1 = deque(range(4), maxlen=None)
new_queue = Queue + Queue1   # __add__操作中maxlen是前者
print(new_queue)
# deque([1, 2, 3], maxlen=3)

3.queue模块

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

• FIFO：先添加的任务先取回
• LIFO ：最近被添加的条目先取回(操作类似一个堆栈)
• Priority：条目将保持排序( 使用 heapq 模块 ) 并且最小值的条目第一个返回。

常用方法：

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() 实际上意味着等到队列为空，再执行别的操作
示例代码：

from queue import Queue,LifoQueue,PriorityQueue
#先进先出队列
q=Queue(maxsize=5)
#后进先出队列
lq=LifoQueue(maxsize=6)
#优先级队列
pq=PriorityQueue(maxsize=5)


from queue import Queue
import time,threading
q=Queue(maxsize=0)

def product(name):
  count=1
  while True:
    q.put('第{}个冰淇凌'.format(count))
    print('{}做冰淇凌第{}个'.format(name, count))
    count+=1
    time.sleep(1)
def consume(name):
  while True:
    print('{}吃了{}'.format(name, q.get()))
    time.sleep(5)
    q.task_done()
t1=threading.Thread(target=product,args=('小狗',))
t2=threading.Thread(target=consume,args=('小猫',))
t3=threading.Thread(target=consume,args=('小猪',))

t1.start()
t2.start()
t3.start()

4.asyncio.Queue

queue.Queue和asyncio.Queue都是支持多生产者、多消费者的队列，基于collections.deque，他们都提供了Queue（FIFO队列）、PriorityQueue（优先级队列）、LifoQueue（LIFO队列），接口方面也相同。

区别在于queue.Queue适用于多线程的场景，asyncio.Queue适用于协程场景下的通信，由于asyncio的加成，queue.Queue下的阻塞接口在asyncio.Queue中则是以返回协程对象的方式执行，具体差异如下表：

5.multiprocessing.Queue

multiprocessing提供了三种队列，分别是Queue、SimpleQueue、JoinableQueue。 

multiprocessing.Queue既是线程安全也是进程安全的，相当于queue.Queue的多进程克隆版。和threading.Queue很像，multiprocessing.Queue支持put和get操作，底层结构是multiprocessing.Pipe。

multiprocessing.Queue底层是基于Pipe构建的，但是数据传递时并不是直接写入Pipe，而是写入进程本地buffer，通过一个feeder线程写入底层Pipe，这样做是为了实现超时控制和非阻塞put/get，所以Queue提供了join_thread、cancel_join_thread、close函数来控制feeder的行为，close函数用来关闭feeder线程、join_thread用来join feeder线程，cancel_join_thread用来在控制在进程退出时，不自动join feeder线程，使用cancel_join_thread有可能导致部分数据没有被feeder写入Pipe而导致的数据丢失。

和threading.Queue不同的是，multiprocessing.Queue默认不支持join()和task_done操作，这两个支持需要使用mp.JoinableQueue对象。

SimpleQueue是一个简化的队列，去掉了Queue中的buffer，没有了使用Queue可能出现的问题，但是put和get方法都是阻塞的并且没有超时控制。