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

Python  /  管理员 发布于 7年前   362

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

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

例如：

queue = deque()# append values to wait for processingqueue.appendleft("first")queue.appendleft("second")queue.appendleft("third")# pop values when readyprocess(queue.pop()) # would process "first"# add values while processingqueue.appendleft("fourth")# what does the queue look like now?queue # deque(['fourth', 'third', 'second'])

作为一个双端队列，deque还提供了一些其他的好用方法，比如 rotate 等，下面我们一起来看一下：

填充
deque可以从任意一端填充，在python实现称为“左端”和“右端”。

import collectionsd1 = collections.deque()d1.extend('abcdefg')print 'extend:', d1d1.append('h')print 'append:', d1d2 = collections.deque()d2.extendleft(xrange(6))print 'extendleft', d2d2.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 collectionsprint "From the right:"d = collections.deque('abcdefg')while True: try:  print d.pop(), except IndexError:  breakprintprint "\nFrom the left:"d = collections.deque(xrange(6))while True: try:  print d.popleft(), except IndexError:  breakprint

使用pop()可以从deque右端删除一个元素，使用popleft()可以从deque左端删除一个元素。

From the right:g f e d c b aFrom the left:0 1 2 3 4 5

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

import collectionsimport threadingimport timecandle = 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 returnleft = 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 collectionsd = collections.deque(xrange(10))print 'Normal:', dd= collections.deque(xrange(10))d.rotate(2)print 'Right roration:', dd = 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 sysimport timefrom collections import dequefancy_loading = deque('>--------------------')while True: print '\r%s' % ''.join(fancy_loading), fancy_loading.rotate(1) sys.stdout.flush() time.sleep(0.08)

输出结果：

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

您可能感兴趣的文章:

• Python实现的数据结构与算法之双端队列详解
• Python编程实现双链表，栈，队列及二叉树的方法示例
• Python collections中的双向队列deque简单介绍详解
• python实现堆栈与队列的方法
• Python中线程的MQ消息队列实现以及消息队列的优点解析
• python队列queue模块详解
• python异步任务队列示例
• Python实现简单多线程任务队列
• python队列Queue的详解
• 详解Python中的四种队列
• Python实现优先级队列结构的方法详解
• python双端队列原理、实现与使用方法分析