详解Python的collections模块中的deque双端队列结构_Python

deque 是 double-ended queue的缩写，类似于 list，不过提供了在两端插入和删除的操作。

appendleft 在列表左侧插入
popleft 弹出列表左侧的值
extendleft 在左侧扩展

例如：

				?

									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实现称为“左端”和“右端”。

				?

									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()相同的处理。

				?

									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元素，取决于应用的算法。

				?

									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左端删除一个元素。

				?

									From the right:

									g f e d c b a

									From the left:

									0 1 2 3 4 5

由于双端队列是线程安全的，可以在不同的线程中同时从两端利用队列的内容。

				?

									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为空。

				?

									Left: 0 Right: 4

									Right: 3 Left: 1

									Right: 2 Left done

									Right done

旋转
deque另外一个作用可以按照任意一个方向旋转，而跳过一些元素。

				?

									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

结果：

				?

									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])

再举个例子：

				?

									# -*- 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)

输出结果：

				?

									# 一个无尽循环的跑马灯 

									------------->-------

详解Python的collections模块中的deque双端队列结构

相关文章

热门资讯