详解Python的collections模块中的deque双端队列结构
deque是double-endedqueue的缩写，类似于list，不过提供了在两端插入和删除的操作。
- appendleft在列表左侧插入
- popleft弹出列表左侧的值
- extendleft在左侧扩展
例如：
queue=deque()
#appendvaluestowaitforprocessing
queue.appendleft("first")
queue.appendleft("second")
queue.appendleft("third")
#popvalueswhenready
process(queue.pop())#wouldprocess"first"
#addvalueswhileprocessing
queue.appendleft("fourth")
#whatdoesthequeuelooklikenow?
queue#deque(['fourth','third','second'])
作为一个双端队列，deque还提供了一些其他的好用方法，比如rotate等，下面我们一起来看一下：
填充
deque可以从任意一端填充，在python实现称为“左端”和“右端”。
importcollections
d1=collections.deque()
d1.extend('abcdefg')
print'extend:',d1
d1.append('h')
print'append:',d1
d2=collections.deque()
d2.extendleft(xrange(6))
print'extendleft',d2
d2.appendleft(6)
print'appendleft',d2
extendleft()迭代处理其输入，对每个元素完成与appendleft()相同的处理。
extend:deque(['a','b','c','d','e','f','g']) append:deque(['a','b','c','d','e','f','g','h']) extendleftdeque([5,4,3,2,1,0]) appendleftdeque([6,5,4,3,2,1,0])
利用
可以从两端利用deque元素，取决于应用的算法。
importcollections
print"Fromtheright:"
d=collections.deque('abcdefg')
whileTrue:
try:
printd.pop(),
exceptIndexError:
break
print
print"\nFromtheleft:"
d=collections.deque(xrange(6))
whileTrue:
try:
printd.popleft(),
exceptIndexError:
break
print
使用pop()可以从deque右端删除一个元素，使用popleft()可以从deque左端删除一个元素。
Fromtheright: gfedcba Fromtheleft: 012345
由于双端队列是线程安全的，可以在不同的线程中同时从两端利用队列的内容。
importcollections
importthreading
importtime
candle=collections.deque(xrange(5))
defburn(direction,nextSource):
whileTrue:
try:
next=nextSource()
exceptIndexError:
break
else:
print'%8s:%s'%(direction,next)
time.sleep(0.1)
print'%8sdone'%direction
return
left=threading.Thread(target=burn,args=('Left',candle.popleft))
right=threading.Thread(target=burn,args=('Right',candle.pop))
left.start()
right.start()
left.join()
right.join()
线程交替处理两端，删除元素，知道这个deque为空。
Left:0Right:4 Right:3Left:1 Right:2Leftdone Rightdone
旋转
deque另外一个作用可以按照任意一个方向旋转，而跳过一些元素。
importcollections d=collections.deque(xrange(10)) print'Normal:',d d=collections.deque(xrange(10)) d.rotate(2) print'Rightroration:',d d=collections.deque(xrange(10)) d.rotate(-2) print'Leftroration:',d
结果：
Normal:deque([0,1,2,3,4,5,6,7,8,9]) Rightroration:deque([8,9,0,1,2,3,4,5,6,7]) Leftroration:deque([2,3,4,5,6,7,8,9,0,1])
再举个例子：
#-*-coding:utf-8-*-
"""
下面这个是一个有趣的例子，主要使用了deque的rotate方法来实现了一个无限循环
的加载动画
"""
importsys
importtime
fromcollectionsimportdeque
fancy_loading=deque('>--------------------')
whileTrue:
print'\r%s'%''.join(fancy_loading),
fancy_loading.rotate(1)
sys.stdout.flush()
time.sleep(0.08)
输出结果：
#一个无尽循环的跑马灯 ------------->-------