<!DOCTYPE html PUBLIC
"-//W3C//DTD HTML 4.0 Transitional//EN">
<link rel=
"STYLESHEET" href=
"lib.css" type='text/css'
/>
<link rel=
"SHORTCUT ICON" href=
"../icons/pyfav.png" type=
"image/png" />
<link rel='start' href='../index.html' title='Python Documentation Index'
/>
<link rel=
"first" href=
"lib.html" title='Python Library Reference'
/>
<link rel='contents' href='contents.html'
title=
"Contents" />
<link rel='index' href='genindex.html' title='Index'
/>
<link rel='last' href='about.html' title='About this document...'
/>
<link rel='help' href='about.html' title='About this document...'
/>
<link rel=
"prev" href=
"module-collections.html" />
<link rel=
"parent" href=
"module-collections.html" />
<link rel=
"next" href=
"module-heapq.html" />
<meta name='aesop' content='information'
/>
<title>5.12.1 Recipes
</title>
<div id='top-navigation-panel' xml:id='top-navigation-panel'
>
<table align=
"center" width=
"100%" cellpadding=
"0" cellspacing=
"2">
<td class='online-navigation'
><a rel=
"prev" title=
"5.12 collections "
href=
"module-collections.html"><img src='../icons/previous.png'
border='
0' height='
32' alt='Previous Page' width='
32'
/></A></td>
<td class='online-navigation'
><a rel=
"parent" title=
"5.12 collections "
href=
"module-collections.html"><img src='../icons/up.png'
border='
0' height='
32' alt='Up One Level' width='
32'
/></A></td>
<td class='online-navigation'
><a rel=
"next" title=
"5.13 heapq "
href=
"module-heapq.html"><img src='../icons/next.png'
border='
0' height='
32' alt='Next Page' width='
32'
/></A></td>
<td align=
"center" width=
"100%">Python Library Reference
</td>
<td class='online-navigation'
><a rel=
"contents" title=
"Table of Contents"
href=
"contents.html"><img src='../icons/contents.png'
border='
0' height='
32' alt='Contents' width='
32'
/></A></td>
<td class='online-navigation'
><a href=
"modindex.html" title=
"Module Index"><img src='../icons/modules.png'
border='
0' height='
32' alt='Module Index' width='
32'
/></a></td>
<td class='online-navigation'
><a rel=
"index" title=
"Index"
href=
"genindex.html"><img src='../icons/index.png'
border='
0' height='
32' alt='Index' width='
32'
/></A></td>
<div class='online-navigation'
>
<b class=
"navlabel">Previous:
</b>
<a class=
"sectref" rel=
"prev" href=
"module-collections.html">5.12 collections
</A>
<b class=
"navlabel">Up:
</b>
<a class=
"sectref" rel=
"parent" href=
"module-collections.html">5.12 collections
</A>
<b class=
"navlabel">Next:
</b>
<a class=
"sectref" rel=
"next" href=
"module-heapq.html">5.13 heapq
</A>
<!--End of Navigation Panel-->
<H2><A NAME=
"SECTION0071210000000000000000"></A><A NAME=
"deque-recipes"></A>
This section shows various approaches to working with deques.
The
<tt class=
"method">rotate()
</tt> method provides a way to implement
<tt class=
"class">deque
</tt>
slicing and deletion. For example, a pure python implementation of
<code>del d[n]
</code> relies on the
<tt class=
"method">rotate()
</tt> method to position
<div class=
"verbatim"><pre>
To implement
<tt class=
"class">deque
</tt> slicing, use a similar approach applying
<tt class=
"method">rotate()
</tt> to bring a target element to the left side of the deque.
Remove old entries with
<tt class=
"method">popleft()
</tt>, add new entries with
<tt class=
"method">extend()
</tt>, and then reverse the rotation.
With minor variations on that approach, it is easy to implement Forth style
stack manipulations such as
<code>dup
</code>,
<code>drop
</code>,
<code>swap
</code>,
<code>over
</code>,
<code>pick
</code>,
<code>rot
</code>, and
<code>roll
</code>.
A roundrobin task server can be built from a
<tt class=
"class">deque
</tt> using
<tt class=
"method">popleft()
</tt> to select the current task and
<tt class=
"method">append()
</tt>
to add it back to the tasklist if the input stream is not exhausted:
<div class=
"verbatim"><pre>
def roundrobin(*iterables):
pending = deque(iter(i) for i in iterables)
>>> for value in roundrobin('abc', 'd', 'efgh'):
Multi-pass data reduction algorithms can be succinctly expressed and
efficiently coded by extracting elements with multiple calls to
<tt class=
"method">popleft()
</tt>, applying the reduction function, and calling
<tt class=
"method">append()
</tt> to add the result back to the queue.
For example, building a balanced binary tree of nested lists entails
reducing two adjacent nodes into one by grouping them in a list:
<div class=
"verbatim"><pre>
pair = [d.popleft(), d.popleft()]
>>> print maketree('abcdefgh')
[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
<div class='online-navigation'
>
<table align=
"center" width=
"100%" cellpadding=
"0" cellspacing=
"2">
<td class='online-navigation'
><a rel=
"prev" title=
"5.12 collections "
href=
"module-collections.html"><img src='../icons/previous.png'
border='
0' height='
32' alt='Previous Page' width='
32'
/></A></td>
<td class='online-navigation'
><a rel=
"parent" title=
"5.12 collections "
href=
"module-collections.html"><img src='../icons/up.png'
border='
0' height='
32' alt='Up One Level' width='
32'
/></A></td>
<td class='online-navigation'
><a rel=
"next" title=
"5.13 heapq "
href=
"module-heapq.html"><img src='../icons/next.png'
border='
0' height='
32' alt='Next Page' width='
32'
/></A></td>
<td align=
"center" width=
"100%">Python Library Reference
</td>
<td class='online-navigation'
><a rel=
"contents" title=
"Table of Contents"
href=
"contents.html"><img src='../icons/contents.png'
border='
0' height='
32' alt='Contents' width='
32'
/></A></td>
<td class='online-navigation'
><a href=
"modindex.html" title=
"Module Index"><img src='../icons/modules.png'
border='
0' height='
32' alt='Module Index' width='
32'
/></a></td>
<td class='online-navigation'
><a rel=
"index" title=
"Index"
href=
"genindex.html"><img src='../icons/index.png'
border='
0' height='
32' alt='Index' width='
32'
/></A></td>
<div class='online-navigation'
>
<b class=
"navlabel">Previous:
</b>
<a class=
"sectref" rel=
"prev" href=
"module-collections.html">5.12 collections
</A>
<b class=
"navlabel">Up:
</b>
<a class=
"sectref" rel=
"parent" href=
"module-collections.html">5.12 collections
</A>
<b class=
"navlabel">Next:
</b>
<a class=
"sectref" rel=
"next" href=
"module-heapq.html">5.13 heapq
</A>
<span class=
"release-info">Release
2.4.2, documentation updated on
28 September
2005.
</span>
<!--End of Navigation Panel-->
See
<i><a href=
"about.html">About this document...
</a></i> for information on suggesting changes.