queue--线程安全的FIFO实现

python的内置模块queue提供了线程安全的队列数据结构，有基本的先进先出的队列Queue， 后进先出的队列LifoQueue和优先级队列PriorityQueue，本文假定你已经对队列这种数据结构有一定了解，如果不是这样，需要你先阅读一些这方面的参考资料，然后再阅读本文

1. 基本FIFO队列

first in first out, 先进先出队列，将元素从队列的一端放入，从另一端删除

import queue

q = queue.Queue()

for i in range(10):
    q.put(i)

while not q.empty():
    print(q.get())

0是最先放入到队列中的，使用get方法时，第一个取到的数值就是0，当9被取出来时，队列变成了空队列，程序输出结果

0 1 2 3 4 5 6 7 8 9

2. LIFO队列

与FIFO队列相反，LIFO队列是后进先出，这是一种栈结构

import queue

q = queue.LifoQueue()

for i in range(10):
    q.put(i)

while not q.empty():
    print(q.get())

9最后被放入到队列中，第一个被取出来，程序输出结果

9 8 7 6 5 4 3 2 1 0

这种数据结构有很广泛的用途，比如下面这个字符串

((sdf)sdf)(sg()())gsg((sgsg()))

请写算法判断，字符串里的小括号是否是成对出现，使用后进先出这种数据结构，可以非常轻松的实现算法

import queue

string = '((sdf)sdf)(sg()())gsg((sgsg()))'


def is_pair(string):
    q = queue.LifoQueue()

    for item in string:
        if item == '(':
            q.put(item)
        elif item == ')':
            if q.empty():
                return False
            q.get()

    return q.empty()

3.优先队列

前面介绍的队列，都是根据进入队列的顺序来决定出队列的顺序，或是先进先出，或是先进后出，除了这两种情况之外，还需要根据优先级来决定出队列的顺序。当有多个任务进入到队列中，根据任务的优先级来决定先执行哪一个，优先级高的先出队列。

import queue


class Task:
    def __init__(self, priority, description):
        self.priority = priority
        self.description = description

    def __eq__(self, other):
        return self.priority == other.priority

    def __lt__(self, other):
        return self.priority < other.priority

    def __str__(self):
        msg = '{_class} 优先级:{priority} 任务:{task}'
        return msg.format(_class=self.__class__, priority=self.priority, task=self.description)

q = queue.PriorityQueue()
q.put(Task(3, '打游戏'))
q.put(Task(5, '做饭'))
q.put(Task(1, '洗碗'))

while not q.empty():
    print(q.get())

程序输出结果

<class '__main__.Task'> 优先级:1 任务:洗碗
<class '__main__.Task'> 优先级:3 任务:打游戏
<class '__main__.Task'> 优先级:5 任务:做饭