deque 是 double-ended queue的缩写,类似于 list,不过提供了在两端插入和删除的操作。
- appendleft 在列表左侧插入
- popleft 弹出列表左侧的值
- extendleft 在左侧扩展
例如:
1
2
3
4
5
6
7
8
9
10
11
|
queue = deque() # append values to wait for processing queue.appendleft( "first" ) queue.appendleft( "second" ) queue.appendleft( "third" ) # pop values when ready process(queue.pop()) # would process "first" # add values while processing queue.appendleft( "fourth" ) # what does the queue look like now? queue # deque(['fourth', 'third', 'second']) |
作为一个双端队列,deque还提供了一些其他的好用方法,比如 rotate 等,下面我们一起来看一下:
填充
deque可以从任意一端填充,在python实现称为“左端”和“右端”。
1
2
3
4
5
6
7
8
9
10
11
|
import collections 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()相同的处理。
1
2
3
4
|
extend: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g']) append: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']) extendleft deque([5, 4, 3, 2, 1, 0]) appendleft deque([6, 5, 4, 3, 2, 1, 0]) |
利用
可以从两端利用deque元素,取决于应用的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import collections print "From the right:" d = collections.deque( 'abcdefg' ) while True : try : print d.pop(), except IndexError: break print print "\nFrom the left:" d = collections.deque( xrange ( 6 )) while True : try : print d.popleft(), except IndexError: break print |
使用pop()可以从deque右端删除一个元素,使用popleft()可以从deque左端删除一个元素。
1
2
3
4
5
|
From the right: g f e d c b a From the left: 0 1 2 3 4 5 |
由于双端队列是线程安全的,可以在不同的线程中同时从两端利用队列的内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import collections import threading import time candle = collections.deque( xrange ( 5 )) def burn(direction, nextSource): while True : try : next = nextSource() except IndexError: break else : print '%8s: %s' % (direction, next ) time.sleep( 0.1 ) print '%8s done' % 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为空。
1
2
3
4
5
6
7
|
Left: 0 Right: 4 Right: 3 Left: 1 Right: 2 Left done Right done |
旋转
deque另外一个作用可以按照任意一个方向旋转,而跳过一些元素。
1
2
3
4
5
6
7
8
9
|
import collections d = collections.deque( xrange ( 10 )) print 'Normal:' , d d = collections.deque( xrange ( 10 )) d.rotate( 2 ) print 'Right roration:' , d d = collections.deque( xrange ( 10 )) d.rotate( - 2 ) print 'Left roration:' , d |
结果:
1
2
3
|
Normal: deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) Right roration: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7]) Left roration: deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1]) |
再举个例子:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# -*- coding: utf-8 -*- """ 下面这个是一个有趣的例子,主要使用了deque的rotate方法来实现了一个无限循环 的加载动画 """ import sys import time from collections import deque fancy_loading = deque( '>--------------------' ) while True : print '\r%s' % ''.join(fancy_loading), fancy_loading.rotate( 1 ) sys.stdout.flush() time.sleep( 0.08 ) |
输出结果:
1
2
|
# 一个无尽循环的跑马灯 ------------->------- |