Editing Deque

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
A '''deque''' (pronounced /dɛk/ or /dik/) 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:
+
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:
 
* ''Push'' an element into the ''front'' of the deque.
 
* ''Push'' an element into the ''front'' of the deque.
 
* ''Push'' an element into the ''back'' of the deque.
 
* ''Push'' an element into the ''back'' of the deque.
Line 14: Line 14:
 
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.
 
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.
  
==Terminology==
+
=Terminology=
 
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.
 
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.
  
==Implementation==
+
=Implementation=
 
===Array implementation===
 
===Array implementation===
 
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:
 
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:
 
<pre>
 
<pre>
object deque
+
object queue
 
     function construct(max_size)
 
     function construct(max_size)
 
           let A be an array that can hold at least max_size+1 elements
 
           let A be an array that can hold at least max_size+1 elements
Line 37: Line 37:
 
           first = (first + 1) mod N
 
           first = (first + 1) mod N
 
           return return_val
 
           return return_val
     function pop_back
+
     function pop_back(x)
 
           last = (last - 1) mod N
 
           last = (last - 1) mod N
 
           return A[last]
 
           return A[last]
Line 54: Line 54:
 
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:
 
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:
 
<pre>
 
<pre>
object deque
+
object queue
 
     function construct
 
     function construct
 
           let L be an empty linked list
 
           let L be an empty linked list
Line 82: Line 82:
 
* <code>void pop_front()</code>: pops from the front of the deque.
 
* <code>void pop_front()</code>: pops from the front of the deque.
 
* <code>void pop_back()</code>: pops from the back of the deque.
 
* <code>void pop_back()</code>: pops from the back of the deque.
* <code>T& front()</code>: returns the element at the front of the deque
+
* <code>T& front()</code>: returns the element at the front of the deqeue
 
* <code>T& back()</code>: returns the element at the back of the deque
 
* <code>T& back()</code>: returns the element at the back of the deque
 
* <code>size_type size()</code>: returns the number of elements currently in the deque
 
* <code>size_type size()</code>: returns the number of elements currently in the deque
Line 91: Line 91:
 
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/>
 
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/>
 
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.
 
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.
 
[[Category:Data structures]]
 

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)
Retrieved from "http://wcipeg.com/wiki/Deque"