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

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)

输出结果：

    # 一个无尽循环的跑马灯 
    ------------->-------