<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Deque — Python Module of the Week</title>
<link rel="stylesheet" href="../_static/sphinxdoc.css" type="text/css" />
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../',
VERSION: '1.132',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="../_static/jquery.js"></script>
<script type="text/javascript" src="../_static/underscore.js"></script>
<script type="text/javascript" src="../_static/doctools.js"></script>
<link rel="author" title="About these documents" href="../about.html" />
<link rel="top" title="Python Module of the Week" href="../index.html" />
<link rel="up" title="collections – Container data types" href="index.html" />
<link rel="next" title="namedtuple" href="namedtuple.html" />
<link rel="prev" title="defaultdict" href="defaultdict.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="namedtuple.html" title="namedtuple"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="defaultdict.html" title="defaultdict"
accesskey="P">previous</a> |</li>
<li><a href="../contents.html">PyMOTW</a> »</li>
<li><a href="../data_types.html" >Data Types</a> »</li>
<li><a href="index.html" accesskey="U">collections – Container data types</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="../contents.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">Deque</a><ul>
<li><a class="reference internal" href="#populating">Populating</a></li>
<li><a class="reference internal" href="#consuming">Consuming</a></li>
<li><a class="reference internal" href="#rotating">Rotating</a></li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="defaultdict.html"
title="previous chapter">defaultdict</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="namedtuple.html"
title="next chapter">namedtuple</a></p>
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/collections/deque.txt"
rel="nofollow">Show Source</a></li>
</ul>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="../search.html" method="get">
<input type="text" name="q" size="18" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="deque">
<span id="id1"></span><h1>Deque<a class="headerlink" href="#deque" title="Permalink to this headline">¶</a></h1>
<p>A double-ended queue, or <tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt>, supports adding and removing
elements from either end. The more commonly used stacks and queues are
degenerate forms of deques, where the inputs and outputs are
restricted to a single end.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">collections</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="s">'abcdefg'</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'Deque:'</span><span class="p">,</span> <span class="n">d</span>
<span class="k">print</span> <span class="s">'Length:'</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">d</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'Left end:'</span><span class="p">,</span> <span class="n">d</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="k">print</span> <span class="s">'Right end:'</span><span class="p">,</span> <span class="n">d</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
<span class="n">d</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="s">'c'</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'remove(c):'</span><span class="p">,</span> <span class="n">d</span>
</pre></div>
</div>
<p>Since deques are a type of sequence container, they support some of
the same operations that lists support, such as examining the contents
with <tt class="xref py py-func docutils literal"><span class="pre">__getitem__()</span></tt>, determining length, and removing elements
from the middle by matching identity.</p>
<div class="highlight-python"><pre>$ python collections_deque.py
Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])</pre>
</div>
<div class="section" id="populating">
<h2>Populating<a class="headerlink" href="#populating" title="Permalink to this headline">¶</a></h2>
<p>A deque can be populated from either end, termed “left” and “right” in the
Python implementation.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">collections</span>
<span class="c"># Add to the right</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">()</span>
<span class="n">d</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="s">'abcdefg'</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'extend :'</span><span class="p">,</span> <span class="n">d</span>
<span class="n">d</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="s">'h'</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'append :'</span><span class="p">,</span> <span class="n">d</span>
<span class="c"># Add to the left</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">()</span>
<span class="n">d</span><span class="o">.</span><span class="n">extendleft</span><span class="p">(</span><span class="s">'abcdefg'</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'extendleft:'</span><span class="p">,</span> <span class="n">d</span>
<span class="n">d</span><span class="o">.</span><span class="n">appendleft</span><span class="p">(</span><span class="s">'h'</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'appendleft:'</span><span class="p">,</span> <span class="n">d</span>
</pre></div>
</div>
<p>Notice that <tt class="xref py py-func docutils literal"><span class="pre">extendleft()</span></tt> iterates over its input and performs
the equivalent of an <tt class="xref py py-func docutils literal"><span class="pre">appendleft()</span></tt> for each item. The end result
is the <tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt> contains the input sequence in reverse order.</p>
<div class="highlight-python"><pre>$ python collections_deque_populating.py
extend : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
append : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
extendleft: deque(['g', 'f', 'e', 'd', 'c', 'b', 'a'])
appendleft: deque(['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'])</pre>
</div>
</div>
<div class="section" id="consuming">
<h2>Consuming<a class="headerlink" href="#consuming" title="Permalink to this headline">¶</a></h2>
<p>Similarly, the elements of the <tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt> can be consumed from
both or either end, depending on the algorithm being applied.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">collections</span>
<span class="k">print</span> <span class="s">'From the right:'</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="s">'abcdefg'</span><span class="p">)</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="k">try</span><span class="p">:</span>
<span class="k">print</span> <span class="n">d</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="k">except</span> <span class="ne">IndexError</span><span class="p">:</span>
<span class="k">break</span>
<span class="k">print</span> <span class="s">'</span><span class="se">\n</span><span class="s">From the left:'</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="s">'abcdefg'</span><span class="p">)</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="k">try</span><span class="p">:</span>
<span class="k">print</span> <span class="n">d</span><span class="o">.</span><span class="n">popleft</span><span class="p">()</span>
<span class="k">except</span> <span class="ne">IndexError</span><span class="p">:</span>
<span class="k">break</span>
</pre></div>
</div>
<p>Use <tt class="xref py py-func docutils literal"><span class="pre">pop()</span></tt> to remove an item from the “right” end of the
<tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt> and <tt class="xref py py-func docutils literal"><span class="pre">popleft()</span></tt> to take from the “left” end.</p>
<div class="highlight-python"><pre>$ python collections_deque_consuming.py
From the right:
g
f
e
d
c
b
a
From the left:
a
b
c
d
e
f
g</pre>
</div>
<p>Since deques are thread-safe, the contents can even be consumed from
both ends at the same time from separate threads.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">collections</span>
<span class="kn">import</span> <span class="nn">threading</span>
<span class="kn">import</span> <span class="nn">time</span>
<span class="n">candle</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="nb">xrange</span><span class="p">(</span><span class="mi">11</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">burn</span><span class="p">(</span><span class="n">direction</span><span class="p">,</span> <span class="n">nextSource</span><span class="p">):</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="k">try</span><span class="p">:</span>
<span class="nb">next</span> <span class="o">=</span> <span class="n">nextSource</span><span class="p">()</span>
<span class="k">except</span> <span class="ne">IndexError</span><span class="p">:</span>
<span class="k">break</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">print</span> <span class="s">'</span><span class="si">%8s</span><span class="s">: </span><span class="si">%s</span><span class="s">'</span> <span class="o">%</span> <span class="p">(</span><span class="n">direction</span><span class="p">,</span> <span class="nb">next</span><span class="p">)</span>
<span class="n">time</span><span class="o">.</span><span class="n">sleep</span><span class="p">(</span><span class="mf">0.1</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'</span><span class="si">%8s</span><span class="s"> done'</span> <span class="o">%</span> <span class="n">direction</span>
<span class="k">return</span>
<span class="n">left</span> <span class="o">=</span> <span class="n">threading</span><span class="o">.</span><span class="n">Thread</span><span class="p">(</span><span class="n">target</span><span class="o">=</span><span class="n">burn</span><span class="p">,</span> <span class="n">args</span><span class="o">=</span><span class="p">(</span><span class="s">'Left'</span><span class="p">,</span> <span class="n">candle</span><span class="o">.</span><span class="n">popleft</span><span class="p">))</span>
<span class="n">right</span> <span class="o">=</span> <span class="n">threading</span><span class="o">.</span><span class="n">Thread</span><span class="p">(</span><span class="n">target</span><span class="o">=</span><span class="n">burn</span><span class="p">,</span> <span class="n">args</span><span class="o">=</span><span class="p">(</span><span class="s">'Right'</span><span class="p">,</span> <span class="n">candle</span><span class="o">.</span><span class="n">pop</span><span class="p">))</span>
<span class="n">left</span><span class="o">.</span><span class="n">start</span><span class="p">()</span>
<span class="n">right</span><span class="o">.</span><span class="n">start</span><span class="p">()</span>
<span class="n">left</span><span class="o">.</span><span class="n">join</span><span class="p">()</span>
<span class="n">right</span><span class="o">.</span><span class="n">join</span><span class="p">()</span>
</pre></div>
</div>
<p>The threads in this example alternate between each end, removing items
until the <tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt> is empty.</p>
<div class="highlight-python"><pre>$ python collections_deque_both_ends.py
Left: 0
Right: 10
Right: 9
Left: 1
Right: 8
Left: 2
Left: 3
Right: 7
Left: 4
Right: 6
Left: 5
Right done
Left done</pre>
</div>
</div>
<div class="section" id="rotating">
<h2>Rotating<a class="headerlink" href="#rotating" title="Permalink to this headline">¶</a></h2>
<p>Another useful capability of the <tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt> is to rotate it in
either direction, to skip over some items.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">collections</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="nb">xrange</span><span class="p">(</span><span class="mi">10</span><span class="p">))</span>
<span class="k">print</span> <span class="s">'Normal :'</span><span class="p">,</span> <span class="n">d</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="nb">xrange</span><span class="p">(</span><span class="mi">10</span><span class="p">))</span>
<span class="n">d</span><span class="o">.</span><span class="n">rotate</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'Right rotation:'</span><span class="p">,</span> <span class="n">d</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">collections</span><span class="o">.</span><span class="n">deque</span><span class="p">(</span><span class="nb">xrange</span><span class="p">(</span><span class="mi">10</span><span class="p">))</span>
<span class="n">d</span><span class="o">.</span><span class="n">rotate</span><span class="p">(</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'Left rotation :'</span><span class="p">,</span> <span class="n">d</span>
</pre></div>
</div>
<p>Rotating the <tt class="xref py py-class docutils literal"><span class="pre">deque</span></tt> to the right (using a positive rotation)
takes items from the right end and moves them to the left
end. Rotating to the left (with a negative value) takes items from the
left end and moves them to the right end. It may help to visualize
the items in the deque as being engraved along the edge of a dial.</p>
<div class="highlight-python"><pre>$ python collections_deque_rotate.py
Normal : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Right rotation: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Left rotation : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])</pre>
</div>
<div class="admonition-see-also admonition seealso">
<p class="first admonition-title">See also</p>
<dl class="last docutils">
<dt><a class="reference external" href="http://en.wikipedia.org/wiki/Deque">WikiPedia: Deque</a></dt>
<dd>A discussion of the deque data structure.</dd>
<dt><a class="reference external" href="http://docs.python.org/lib/deque-recipes.html">Deque Recipes</a></dt>
<dd>Examples of using deques in algorithms from the standard library documentation.</dd>
</dl>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="namedtuple.html" title="namedtuple"
>next</a> |</li>
<li class="right" >
<a href="defaultdict.html" title="defaultdict"
>previous</a> |</li>
<li><a href="../contents.html">PyMOTW</a> »</li>
<li><a href="../data_types.html" >Data Types</a> »</li>
<li><a href="index.html" >collections – Container data types</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright Doug Hellmann.
Last updated on Oct 24, 2010.
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a>.
<br/><a href="http://creativecommons.org/licenses/by-nc-sa/3.0/us/" rel="license"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-nc-sa/3.0/us/88x31.png"/></a>
</div>
</body>
</html>