队列

队列（queue）是一种先进先出（first-in, first-out）（FIFO）的数据结构。

允许添加元素的一端为队尾（rear），允许删除元素的一端为队头（front）。

队列的空间复杂度为O(n)。

队列操作及时间复杂度

队列的所有操作均可以在常数时间（O(1)）完成。

使用deque

Python在collections模块里有一个用作双向队列的数据结构deque。用它来实现所有的队列操作。

判空操作，同样的，可以len，也可以try-except，我更推荐try-except。

from collections import deque  
  
q = deque()  
  
# enqueue  
q.append(1)  
q.append(2)  
  
# dequeue  
front = q.popleft()  
  
# peek  
front_item = q[0]  
  
# is_empty  
is_empty = len(q) == 0

同样的，也可以封装一下

from collections import deque  
  
  
class Queue:  
    def __init__(self):  
        self._data = deque()  
  
    def enqueue(self, item):  
        self._data.append(item)  
  
    def dequeue(self):  
        return self._data.popleft()  
  
    def peek(self):  
        return self._data[0]  
  
    def is_empty(self):  
        try:  
            self._data.popleft()  
        except IndexError:  
            return True  
        else:  
            return False