deque
class collections.deque([iterable[, maxlen]])
返回一个从左到右初始化的新deque对象(使用append())，其中包含来自iterable的数据,如果未指定iterable，则new deque为空。
Deques是堆栈和队列的泛化(名称读作“deck”，是“双端队列 double-ended queue”的缩写)。
Deques 支持线程安全的, 内存高效附加,从deque的任何一边弹出(pop)，在任何方向上的O(1)性能大致相同
虽然list对象支持类似的操作，但是它们针对快速固定长度的操作进行了优化，并且会导致pop(0)和insert(0, v)操作的O(n)内存移动成本，而pop(0)和insert(0, v)操作会改变底层数据表示的大小和位置。
如果未指定maxlen或为None, deques可能会增长到任意长度。否则，deque被限制到指定的最大长度。一旦有界长度deque满了，当添加新项时，将从另一端丢弃相应数量的项。有界长度deques提供了与Unix中的tail过滤器类似的功能。它们还可用于跟踪仅对最近的活动感兴趣的事务和其他数据池。
Deque对象支持以下方法:
- append(x)
在deque的右边加上x - appendleft(x)
在deque的左边加上x - clear()
删除deque中的所有元素，让它的长度为0 - count(x)
计算deque中的元素x的个数 - extend(iterable)
通过添加来自iterable参数的元素来扩展deque的右侧 - extendleft(iterable)
通过添加iterable元素来扩展deque的左侧。注意，左对齐序列的结果是颠倒了可迭代参数中元素的顺序。 - pop()
从deque的右侧删除并返回一个元素。如果不存在元素，则引发一个IndexError - popleft()
从deque的左侧删除并返回一个元素。如果不存在元素，则引发一个IndexError - remove(value)
删除第一个出现的值。如果没有找到，则引发ValueError - reverse()
将deque的元素反向放置，and return None - rotate(n=1)
向右旋转deque n个步骤。如果n是负的，向左旋转。
当deque不为空时，向右旋转一步等价于d.appendleft(d.pop())，向左旋转一步等价于d.append(d.popleft())。
Deque对象还提供一个只读属性:
- maxlen
deque的最大大小，如果无界则为None。就是创建时的maxlen参数
除了上述功能，deques 支持迭代，pickling，len(d), reversed(d), copy.copy(d), copy.deepcopy(d)，
使用in操作符进行成员测试，下标引用，如d[-1]， 索引访问在两端都是O(1)，但在中间变慢到O(n)。对于快速随机访问，使用列表代替。
>>> from collections import deque
>>> d = deque('ghi') # make a new deque with three items
>>> for elem in d: # iterate over the deque's elements
... print elem.upper()
G
H
I
>>> d.append('j') # add a new entry to the right side
>>> d.appendleft('f') # add a new entry to the left side
>>> d # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])
>>> d.pop() # return and remove the rightmost item
'j'
>>> d.popleft() # return and remove the leftmost item
'f'
>>> list(d) # list the contents of the deque
['g', 'h', 'i']
>>> d[0] # peek at leftmost item
'g'
>>> d[-1] # peek at rightmost item
'i'
>>> list(reversed(d)) # list the contents of a deque in reverse
['i', 'h', 'g']
>>> 'h' in d # search the deque
True
>>> d.extend('jkl') # add multiple elements at once
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1) # right rotation
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1) # left rotation
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> deque(reversed(d)) # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear() # empty the deque
>>> d.pop() # cannot pop from an empty deque
Traceback (most recent call last):
File "<pyshell#6>", line 1, in -toplevel-
d.pop()
IndexError: pop from an empty deque
>>> d.extendleft('abc') # extendleft() reverses the input order
>>> d
deque(['c', 'b', 'a'])
