https://wcipeg.com/wiki/index.php?title=Deque&feed=atom&action=historyDeque - Revision history2024-03-28T13:44:59ZRevision history for this page on the wikiMediaWiki 1.25.2https://wcipeg.com/wiki/index.php?title=Deque&diff=1044&oldid=prevJargon: /* Array implementation */ fix pop_back(x) → pop_back2011-03-04T03:35:19Z<p><span dir="auto"><span class="autocomment">Array implementation: </span> fix pop_back(x) → pop_back</span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 03:35, 4 March 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L37" >Line 37:</td>
<td colspan="2" class="diff-lineno">Line 37:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           first = (first + 1) mod N</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           first = (first + 1) mod N</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return return_val</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return return_val</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>     function pop_back<del class="diffchange diffchange-inline">(x)</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>     function pop_back</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           last = (last - 1) mod N</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           last = (last - 1) mod N</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return A[last]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return A[last]</div></td></tr>
</table>Jargonhttps://wcipeg.com/wiki/index.php?title=Deque&diff=1041&oldid=prevBrian at 22:34, 3 March 20112011-03-03T22:34:03Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 22:34, 3 March 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>A '''deque''' is a data structure containing zero or more items, all of the same type, which may be thought to represent the items lined up in single file with a front and a back. It supports four basic operations:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>A '''deque''' <ins class="diffchange diffchange-inline">(pronounced /dɛk/ or /dik/) </ins>is a data structure containing zero or more items, all of the same type, which may be thought to represent the items lined up in single file with a front and a back. It supports four basic operations:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* ''Push'' an element into the ''front'' of the deque.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* ''Push'' an element into the ''front'' of the deque.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* ''Push'' an element into the ''back'' of the deque.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* ''Push'' an element into the ''back'' of the deque.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="L14" >Line 14:</td>
<td colspan="2" class="diff-lineno">Line 14:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>These peek operations are not really necessary; ''peek front'' is the same as ''pop front'' followed by ''push front'', if the popped element is copied and then pushed back on; ''peek back'' can be defined analogously. And the ''test if empty'' operation is really a test of whether the result of the ''find size'' operation is zero.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>These peek operations are not really necessary; ''peek front'' is the same as ''pop front'' followed by ''push front'', if the popped element is copied and then pushed back on; ''peek back'' can be defined analogously. And the ''test if empty'' operation is really a test of whether the result of the ''find size'' operation is zero.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>=Terminology=</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=</ins>=Terminology<ins class="diffchange diffchange-inline">=</ins>=</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The term ''deque'' is a shortened form of ''double-ended queue''. It is said to be double-ended because pushes and pops from both ends are possible; here the term ''queue'' is the name of a general class of data structures which allow insertion and removal of elements (but not search). The ''first'' element is the one at the front of the deque, and the ''last'' is the one at the back of the deque. An element can be described as ''before'' another if the former is closer to the front than the latter; the latter is referred to as being ''after'' the former. To ''push'' means to add an element, and to ''pop'' means to remove an element. Note that the front and the back of the deque are fully equivalent; we could interchange the terms ''front'' and ''back'' throughout our algorithms and they would work exactly as they did before.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The term ''deque'' is a shortened form of ''double-ended queue''. It is said to be double-ended because pushes and pops from both ends are possible; here the term ''queue'' is the name of a general class of data structures which allow insertion and removal of elements (but not search). The ''first'' element is the one at the front of the deque, and the ''last'' is the one at the back of the deque. An element can be described as ''before'' another if the former is closer to the front than the latter; the latter is referred to as being ''after'' the former. To ''push'' means to add an element, and to ''pop'' means to remove an element. Note that the front and the back of the deque are fully equivalent; we could interchange the terms ''front'' and ''back'' throughout our algorithms and they would work exactly as they did before.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>=Implementation=</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=</ins>=Implementation<ins class="diffchange diffchange-inline">=</ins>=</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Array implementation===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Array implementation===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>In an array implementation of a deque, the contents of the deque are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop from the front, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. The same applies if we want to push at the front; all elements currently in the deque would have to be shifted over to make room for the new element. These operations can both take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the deque. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped, and we insert a pushed element at the index just before the current front element. That is, we maintain two indices into the array: one to the front and one to the back. When we push at the front, we add an element to the front and decrement the front index; when we push at the back, we add an element to the back and increment the back index; when we pop from the front, we remove the element from the front and increment the front index; when we pop from the back, we remove the element from the back and decrement the back index. However, consider what happens if, for example, we continually push one element at the front, then pop one from the back, then push another, and pop another, and so on: the size of the deque doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>In an array implementation of a deque, the contents of the deque are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop from the front, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. The same applies if we want to push at the front; all elements currently in the deque would have to be shifted over to make room for the new element. These operations can both take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the deque. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped, and we insert a pushed element at the index just before the current front element. That is, we maintain two indices into the array: one to the front and one to the back. When we push at the front, we add an element to the front and decrement the front index; when we push at the back, we add an element to the back and increment the back index; when we pop from the front, we remove the element from the front and increment the front index; when we pop from the back, we remove the element from the back and decrement the back index. However, consider what happens if, for example, we continually push one element at the front, then pop one from the back, then push another, and pop another, and so on: the size of the deque doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:</div></td></tr>
</table>Brianhttps://wcipeg.com/wiki/index.php?title=Deque&diff=452&oldid=prevBrian at 17:52, 30 August 20102010-08-30T17:52:05Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:52, 30 August 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L21" >Line 21:</td>
<td colspan="2" class="diff-lineno">Line 21:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>In an array implementation of a deque, the contents of the deque are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop from the front, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. The same applies if we want to push at the front; all elements currently in the deque would have to be shifted over to make room for the new element. These operations can both take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the deque. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped, and we insert a pushed element at the index just before the current front element. That is, we maintain two indices into the array: one to the front and one to the back. When we push at the front, we add an element to the front and decrement the front index; when we push at the back, we add an element to the back and increment the back index; when we pop from the front, we remove the element from the front and increment the front index; when we pop from the back, we remove the element from the back and decrement the back index. However, consider what happens if, for example, we continually push one element at the front, then pop one from the back, then push another, and pop another, and so on: the size of the deque doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>In an array implementation of a deque, the contents of the deque are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop from the front, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. The same applies if we want to push at the front; all elements currently in the deque would have to be shifted over to make room for the new element. These operations can both take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the deque. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped, and we insert a pushed element at the index just before the current front element. That is, we maintain two indices into the array: one to the front and one to the back. When we push at the front, we add an element to the front and decrement the front index; when we push at the back, we add an element to the back and increment the back index; when we pop from the front, we remove the element from the front and increment the front index; when we pop from the back, we remove the element from the back and decrement the back index. However, consider what happens if, for example, we continually push one element at the front, then pop one from the back, then push another, and pop another, and so on: the size of the deque doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><pre></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><pre></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>object <del class="diffchange diffchange-inline">queue</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>object <ins class="diffchange diffchange-inline">deque</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct(max_size)</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct(max_size)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           let A be an array that can hold at least max_size+1 elements</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           let A be an array that can hold at least max_size+1 elements</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="L54" >Line 54:</td>
<td colspan="2" class="diff-lineno">Line 54:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The circular array implementation will almost always be appropriate. However, for rare instances in which a contiguous block of memory of the required size cannot be found, a linked list can be used instead. Details of the list implementation are omitted below:</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The circular array implementation will almost always be appropriate. However, for rare instances in which a contiguous block of memory of the required size cannot be found, a linked list can be used instead. Details of the list implementation are omitted below:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><pre></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><pre></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>object <del class="diffchange diffchange-inline">queue</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>object <ins class="diffchange diffchange-inline">deque</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           let L be an empty linked list</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           let L be an empty linked list</div></td></tr>
</table>Brianhttps://wcipeg.com/wiki/index.php?title=Deque&diff=194&oldid=prevJargon: categorize2009-12-23T17:19:11Z<p>categorize</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:19, 23 December 2009</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L91" >Line 91:</td>
<td colspan="2" class="diff-lineno">Line 91:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Note that the pop operations defined by this container are not identical to our own; they only remove the element and do not return its value. To do both, call <code>front</code> or <code>back</code> followed by <code>pop_front</code> or <code>pop_back</code>.<br/></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Note that the pop operations defined by this container are not identical to our own; they only remove the element and do not return its value. To do both, call <code>front</code> or <code>back</code> followed by <code>pop_front</code> or <code>pop_back</code>.<br/></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The STL <code>stack</code> and <code>queue</code> containers, except when this behavior is overridden by the corresponding template argument, are mere containers over STL <code>deque</code>s; since the deque's behavior is a superset of the behaviors of the stack and queue, either can be obtained simply by manipulating a deque with a restricted set of operations.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The STL <code>stack</code> and <code>queue</code> containers, except when this behavior is overridden by the corresponding template argument, are mere containers over STL <code>deque</code>s; since the deque's behavior is a superset of the behaviors of the stack and queue, either can be obtained simply by manipulating a deque with a restricted set of operations.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Data structures]]</ins></div></td></tr>
</table>Jargonhttps://wcipeg.com/wiki/index.php?title=Deque&diff=177&oldid=prevBrian: /* C++ STL deque class */2009-12-20T05:51:41Z<p><span dir="auto"><span class="autocomment">C++ STL deque class</span></span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 05:51, 20 December 2009</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L82" >Line 82:</td>
<td colspan="2" class="diff-lineno">Line 82:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>void pop_front()</code>: pops from the front of the deque.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>void pop_front()</code>: pops from the front of the deque.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>void pop_back()</code>: pops from the back of the deque.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>void pop_back()</code>: pops from the back of the deque.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* <code>T& front()</code>: returns the element at the front of the <del class="diffchange diffchange-inline">deqeue</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <code>T& front()</code>: returns the element at the front of the <ins class="diffchange diffchange-inline">deque</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>T& back()</code>: returns the element at the back of the deque</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>T& back()</code>: returns the element at the back of the deque</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>size_type size()</code>: returns the number of elements currently in the deque</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* <code>size_type size()</code>: returns the number of elements currently in the deque</div></td></tr>
</table>Brianhttps://wcipeg.com/wiki/index.php?title=Deque&diff=176&oldid=prevBrian: Created page with 'A '''deque''' is a data structure containing zero or more items, all of the same type, which may be thought to represent the items lined up in single file with a front and a back…'2009-12-20T05:48:11Z<p>Created page with 'A '''deque''' is a data structure containing zero or more items, all of the same type, which may be thought to represent the items lined up in single file with a front and a back…'</p>
<p><b>New page</b></p><div>A '''deque''' is a data structure containing zero or more items, all of the same type, which may be thought to represent the items lined up in single file with a front and a back. It supports four basic operations:<br />
* ''Push'' an element into the ''front'' of the deque.<br />
* ''Push'' an element into the ''back'' of the deque.<br />
* ''Pop'' an element from the ''front'' of the deque, returning its value in the process.<br />
* ''Pop'' an element from the ''back'' of the deque, returning its value in the process.<br />
In practice, we might choose to include the following operations as well:<br />
* ''Construct'' an empty deque.<br />
* ''Copy'' the contents of one deque to another.<br />
* ''Peek'' at the ''front'' element in the deque, without removing it.<br />
* ''Peek'' at the ''back'' element in the deque, without removing it.<br />
* ''Empty'' an already existing deque.<br />
* ''Find size'' of a deque.<br />
* ''Test if empty''.<br />
These peek operations are not really necessary; ''peek front'' is the same as ''pop front'' followed by ''push front'', if the popped element is copied and then pushed back on; ''peek back'' can be defined analogously. And the ''test if empty'' operation is really a test of whether the result of the ''find size'' operation is zero.<br />
<br />
=Terminology=<br />
The term ''deque'' is a shortened form of ''double-ended queue''. It is said to be double-ended because pushes and pops from both ends are possible; here the term ''queue'' is the name of a general class of data structures which allow insertion and removal of elements (but not search). The ''first'' element is the one at the front of the deque, and the ''last'' is the one at the back of the deque. An element can be described as ''before'' another if the former is closer to the front than the latter; the latter is referred to as being ''after'' the former. To ''push'' means to add an element, and to ''pop'' means to remove an element. Note that the front and the back of the deque are fully equivalent; we could interchange the terms ''front'' and ''back'' throughout our algorithms and they would work exactly as they did before.<br />
<br />
=Implementation=<br />
===Array implementation===<br />
In an array implementation of a deque, the contents of the deque are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop from the front, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. The same applies if we want to push at the front; all elements currently in the deque would have to be shifted over to make room for the new element. These operations can both take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the deque. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped, and we insert a pushed element at the index just before the current front element. That is, we maintain two indices into the array: one to the front and one to the back. When we push at the front, we add an element to the front and decrement the front index; when we push at the back, we add an element to the back and increment the back index; when we pop from the front, we remove the element from the front and increment the front index; when we pop from the back, we remove the element from the back and decrement the back index. However, consider what happens if, for example, we continually push one element at the front, then pop one from the back, then push another, and pop another, and so on: the size of the deque doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:<br />
<pre><br />
object queue<br />
function construct(max_size)<br />
let A be an array that can hold at least max_size+1 elements<br />
let N = max_size+1<br />
let first = 0<br />
let last = 0<br />
function push_front(x)<br />
first = (first - 1) mod N<br />
A[first] = x<br />
function push_back(x)<br />
A[last] = x<br />
last = (last + 1) mod N<br />
function pop_front<br />
return_val = A[first]<br />
first = (first + 1) mod N<br />
return return_val<br />
function pop_back(x)<br />
last = (last - 1) mod N<br />
return A[last]<br />
function peek_front<br />
return A[first]<br />
function peek_back<br />
return A[(last-1) mod N]<br />
function size<br />
return (last-first) mod N<br />
function make_empty<br />
last = first<br />
</pre><br />
Notice that if the deque becomes full and we attempt to push more elements, then the apparent size will wrap to zero and some elements will be overwritten. Also, if we attempt to pop from an empty deque, the apparent size will wrap to the largest possible value. Error-checking code is fairly simple to add but, like the ''test if empty'' and ''copy'' operations, it has been omitted for the sake of brevity.<br />
<br />
===Linked list implementation===<br />
The circular array implementation will almost always be appropriate. However, for rare instances in which a contiguous block of memory of the required size cannot be found, a linked list can be used instead. Details of the list implementation are omitted below:<br />
<pre><br />
object queue<br />
function construct<br />
let L be an empty linked list<br />
function push_front(x)<br />
insert x before head of L<br />
function push_back(x)<br />
insert x after tail of L<br />
function pop_front<br />
remove head of L, returning its data element<br />
function pop_back<br />
remove tail of L, returning its data element<br />
function peek_front<br />
return data element at head of L<br />
function peek_back<br />
return data element at tail of L<br />
function size<br />
return size of L<br />
function make_empty<br />
empty L<br />
</pre><br />
As one can easily see, the deque is merely a container over the operations supported by the list itself. (Here we assume that the list maintains its own size; if this is not so then we can add a <code>size</code> field to the deque object.)<br />
<br />
===C++ STL deque class===<br />
In the C++ STL, <code>std::deque</code>, found in the <code>&lt;deque&gt;</code> header, is a template container capable of holding items of any (fixed) type, the type being supplied as a template argument. Hence, for example, <code>deque&lt;char&gt;</code> is a deque of characters. The container supplies the following member functions (note that <code>T</code> is the type of the elements of the deque):<br />
* <code>void push_front(const T& x)</code>: pushes <code>x</code> into the front of the deque.<br />
* <code>void push_back(const T& x)</code>: pushes <code>x</code> into the back of the deque.<br />
* <code>void pop_front()</code>: pops from the front of the deque.<br />
* <code>void pop_back()</code>: pops from the back of the deque.<br />
* <code>T& front()</code>: returns the element at the front of the deqeue<br />
* <code>T& back()</code>: returns the element at the back of the deque<br />
* <code>size_type size()</code>: returns the number of elements currently in the deque<br />
* <code>bool empty()</code>: returns <code>true</code> if the deque is empty, <code>false</code> otherwise.<br />
* <code>void clear()</code>: removes all elements in the deque, leaving it empty.<br />
Additionally, unlike the STL <code>stack</code> and <code>queue</code> containers, the <code>deque</code> container allows random-access iteration over its elements: hence <code>D[0]</code> is a reference to the element at the front of deque <code>D</code>, and so on.<br/><br />
The <code>deque</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own deque. You are highly unlikely to encounter an application for which the STL <code>deque</code> is too slow.<br/><br />
Note that the pop operations defined by this container are not identical to our own; they only remove the element and do not return its value. To do both, call <code>front</code> or <code>back</code> followed by <code>pop_front</code> or <code>pop_back</code>.<br/><br />
The STL <code>stack</code> and <code>queue</code> containers, except when this behavior is overridden by the corresponding template argument, are mere containers over STL <code>deque</code>s; since the deque's behavior is a superset of the behaviors of the stack and queue, either can be obtained simply by manipulating a deque with a restricted set of operations.</div>Brian