 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
| Double-ended queue | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 Input Input Output Output as a queue as a stack Representation of a double-ended queue | |||||||||||||||||||||
| |||||||||||||||||||||
Incomputer science, adouble-ended queue (abbreviated todeque), is anabstract data type that serves as an orderedcollection of entities.It generalizes both aqueue and astack : elements can be added (enqueue) to or removed (dequeue) from either end.[1] It provides similar services incomputer science,transport, andoperations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the deque performs the function of abuffer. The additional flexibility in managing the order of elements or the properties of some implementations may allow the improvement and optimization of certain algorithms.
As a general data class, the deque has some possible sub-types:
Despite their limitations these sub-types have manyapplications and their implementations may be simpler.
The termdeque (/dɛk/DEK) is used as anacronym and in analogy to adeck of cards with which the structure shares some properties and the pronunciation.[1]: 239 [2]Dequeue is sometimes used but can be confusing as the term is also used for the operation of removing an element of the deque.A deque may also be called ahead-tail linked list, though properly this refers to aspecific implementation.
An input-restricted deque is often called asteque (for stack-ended queue).[1]: 240 [3]: 53
There is no standard vocabulary associated with deques. The termsenqueue anddequeue, borrowed from the queue structure, generally denote the basic operations on a deque, on either end. But papers and actual implementations often use different names.The names of the operations vary depending on the context, the author, the implementation or the programming language:
Unlike the associated data structures the deque is symmetrical. Its sides may be freely named according to the context:
The full name of an operation may be a combination of the name of the basic operation and the name of the side: e.g.push_front andpop_back. Terms from different analogies may be associated in a single context:append andpop,push andshift, orfront andtail. Finally some programming languages use even different names based on the underlying data structure.
Also generally implemented are"peek" operations, which return the value at one end without dequeuing it. It is often named after the target side: e.g.top is the value of the element at the top of the deque. In the context of the functional programming, thedequeue operation (that returns two values: the removed element and the new deque) is not used. It is replaced by apeek function (i.e.head andlast) and a function that returns the deque minus the end, i.e.tail andinit.
There are at least two common ways to efficiently implement a deque,that are often pitted against one another: with a doubly linked list or with a modified dynamic array. There are many variations and actual implementations are often hybrid solutions.Additionally, severalpurely functional implementations of the double-ended queue exist.
While a simple list may implement a deque, adoubly-linked list is more adequate for its symmetry to achieve a fast access to both ends of the list (head andtail, hence the namehead-tail linked list). The obvious solution is to manage two references; alternatively the deque can be built as a circular list.
In a doubly-linked list implementation, and assuming no allocation/deallocation overhead, thetime complexity of all deque operations isO(1). Additionally, insertion or deletion in the middle, given an iterator, can also be achieved in constant time; however, the time taken for random access by index isO(n). Similarly, finding a specific element normallyrequiresO(n) time. Linked data structures generally have poor locality of reference.
In this case as well, while adynamic array can be used to implement a deque, a variant that can grow from both ends is more appropriate. This is sometimes calledarray deques. This can be achieved in various ways, e.g.:
Theamortized time complexity of all deque operations with anarray deque isO(1), thanks to the geometric expansion of the back-end buffer. Additionally, random access by index takes constant time ; but the average time taken for insertion or deletion in the middle areO(n). Thank to the fast random access, finding an element in an ordered array is timeO(log n) (binary search).Each time the array is resized, the whole content is moved: the memory usage is then momentarily doubled (or more), and all direct (external) references to the content of the array are lost.
Doubly linked lists cannot be used asimmutable data structures. And an immutable array would be highly inefficient (an array is often simulated bya tree). A purely functional implementation of the deque can be based on stack, that is easily implemented with asingly linked list as an immutable andpersistent structure.
There are several works in the literature dealing with this problem. All of these use two key ideas. The first is that a deque can be represented by a pair of stacks, one representing the front part of the deque and the other representing the reversal of the rear part. When one side becomes empty because of too manypop oreject operations, the deque, now all on one stack, is copied into two stacks each containing half of the deque elements. This fifty-fifty split guarantees that such copying, even though expensive, happens infrequently. A simple amortization argument shows that this gives a linear-time simulation of a deque by a constant number of stacks:k deque operations starting from an empty deque are simulated by O(k) stack operations.
[…]
The second idea is to use incremental copying to convert this linear-time simulation into a real-time simulation: as soon as the two stack become sufficiently unbalanced, recopying to create two balanced stacks begins.
— Kaplan, Haim;Tarjan, Robert E. (1995). "Persistent lists with catenation via recursive slow-down".Proc. of the 27th annual ACM symposium on Theory of computing. Las Vegas, Nevada. pp. 93–102.doi:10.1145/225058.225090.(preliminary version of[4])
This last process could be rather complicated as it needs to be executed concurrently with other operations and completed before the next one, to achieve an amortized real-time complexity. The next step is to support the operations inO(1)worst-case time. Another challenge is the real-time catenation of deques.Okasaki gives a simple solution that useslazy lists combined withmemoization. The stack to stack balancing is then partially automatic by means of a precise scheduling of incremental functions.[3]: 52−59 : 115 However some authors deem such algorithm as not purely functional since memoization is considered as aside effect.[4]: 581 Kaplan and Tarjan gives their own version of the purely functional deque (non-catenable), based on three ideas:[4]
2 digit stands for a suspended carry: the sub-deque contains pairs of elements from the parent deque, and the propagation of the balancing process to the sub-deque is delayed like is the carry propagation after the increment or decrement of a RBR number;[3]: 105 1 digits, that can be skipped to access the next2, i.e. a suspended carry.In this paper Kaplan and Tarjan also present an even more complex version that achieves catenation in real-time. However this description is mostly textual. J. Viennot, A. Wendling, A. Guéneau, and F. Pottier publish a verified implementation of this data structure (inOCaml andRocq), alongside a formal description and detailed analysis of the algorithm.[5]
More generally, real-time catenation requires a deque is a tuple consisting mainly in two sub-structures, that themselves contain deques or compounds of deques. The linear spine of the non-catenable deque is then replaced by abinary skeleton.
Kaplan, Okasaki, and Tarjan produced a simpler, amortized version that can be implemented either using lazy evaluation or more efficiently using mutation in a broader but still restricted fashion.[6]Mihaescu and Tarjan created a simpler (but still highly complex) strictly purely functional implementation of catenable deques, and also a much simpler implementation of strictly purely functional non catenable deques, both of which have optimal worst-case bounds (not officially published).[7]
Ada's containers provides the generic packagesAda.Containers.Vectors andAda.Containers.Doubly_Linked_Lists, for the dynamic array and linked list implementations, respectively.
C++'sStandard Template Library provides the class templatesstd::deque andstd::list, for the multiple array and linked list implementations, respectively.
As of Java 6, Java's Collections Framework provides a newDeque interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such asArrayDeque (also new in Java 6) andLinkedList, providing the dynamic array and linked list implementations, respectively. However, theArrayDeque, contrary to its name, does not support random access.
Javascript'sArray prototype &Perl's arrays have native support for both removing (shift andpop) and adding (unshift andpush) elements on both ends.
Python 2.4 introduced thecollections module with support fordeque objects. It is implemented using a doubly linked list of fixed-length subarrays.
As of PHP 5.3, PHP's SPL extension contains the 'SplDoublyLinkedList' class that can be used to implement Deque datastructures. Previously to make a Deque structure the array functions array_shift/unshift/pop/push had to be used instead.
GHC'sData.Sequence module implements an efficient, functional deque structure inHaskell. The implementation uses2–3 finger trees annotated with sizes.
Rust'sstd::collections includesVecDeque which implements a double-ended queue using a growable ring buffer.
A double-ended queue can always be substituted for a queue or a stack structure. Thus real-world applications of the deque are often extended versions of stack- or queue-based algorithms. Actually many applications only need an output- or (more rarely) input-restricted deque. Only real-world applications that are optimally based on strict deque, i.e. witch only need access to the elements at both ends and one by one, are listed here.
An input-restricted deque can be used to build amonotonic queue, i.e. asub-sequence whom elements are in given order, either increasing or decreasing. Given a sequence, the algorithm only keeps elements in the desired order and discards the other ones. The order of the elements is preserved.To build an increasing (resp. decreasing) monotonic sequence, only stack operations are used :
std::deque<int>increasing_monotonic_queue(std::vector<int>&seq[]){std::deque<int>q;for(std::size_ti=0;i<seq.size();i++){while(!q.empty()&&q.back()>seq[i])q.pop_back();q.push_back(seq[i]);}returnq;}
The elements of the monotonic sequence can then be dequeued from the other side (hence the usage of a deque).
A monotonic queue can be used to find the minimum or maximum value in a sliding window over a sequence in a linear time complexity.[8] The complexity of a naive solution isO(n.k) time andO(1) space, wheren is the length of the input sequence andk the size of the window. A solution that use some kind of search method isO(n.log n) time andO(n) space.
In the following code, the monotonic queue stores references to the elements of the sequence.
#include<vector>#include<deque>typedefstd::vector<int>::const_iteratorseq_iterator;typedefstd::deque<seq_iterator>monotonic_queue;monotonic_queue&decreasing_monotonic_queue_push(monotonic_queue&q,seq_iteratori){while(!q.empty()&&*q.back()<*i)q.pop_back();q.push_back(i);returnq;}std::vector<int>max_of_subarrays(std::vector<int>&seq,std::size_twin_sz){std::vector<int>max_of_sub;monotonic_queuedecreasing;seq_iteratori=seq.begin();// scan the 1st windowfor(size_twin_i=0;i<seq.end()&&win_i<win_sz;i++,win_i++)decreasing_monotonic_queue_push(decreasing,i);max_of_sub.push_back(*decreasing.front());// scan the rest of the sequencefor(/*keep i*/;i<seq.end();i++){if(decreasing.front()<=i-win_sz)decreasing.pop_front();// fall out of scopedecreasing_monotonic_queue_push(decreasing,i);max_of_sub.push_back(*decreasing.front());}returnmax_of_sub;}
Each element of the input sequence is pushed and popped at most once resulting in2.n operations. The time complexity is thenO(n). The space complexity isO(k), the maximum size of the deque.
In a similar way a monotonic queue allows the optimization of somedynamic programming cases equivalent to theleast-weight sub-sequence problem :shortest path problem for a weighted directed graph,paragraph breaking, etc. These problems are said to beconvex orconcave, and thenmonotonic. The time complexity is then reduced fromO(n2) toO(n.log n), andO(n) in conducive situations.[9][10]
An other direct application of the monotonic queue is theminimum queue orminqueue. In this case the count of items in the window varies. The minqueue is a data structure with aqueue interface that additionally gives a direct access to the minimum stored item. The key operations are thenenqueue,dequeue andfind min. Despite the name alludes to the(min/max-) heap, the min/max-queue is not apriority queue: the order of the items is maintained from the enter to the exit (FIFO policy). A simple version of a min-queue withO(1) amortized time is a normal queue combined with an auxiliary increasing monotonic queue, that gives the minimum item on its front. The addition of an item applies to both queues, and when the minimum item is dequeued from the normal queue (i.e. same front item), it is also dequeued from the monotonic queue.[11]
Melkman's algorithm computes the convex hull of asimple polygonal chain (or asimple polygon) in linear time. The main difference with other similar algorithm is that Melkman requires vertices to be added on removed on both ends of the forming hull chain. Hence the use of a deque. The algorithm computes the position of each new vertex relative to the first and last segments (two vertices each) of the hull chain (stored in the deque). The vertex is either ignored or added (enqueued) to both sides of the deque (the hull is a loop), after removing (dequeueing) some previous vertices that are now on the inner side of the hull.[12][13][14]
fromcollectionsimportdequedefposition(A,B,C):det=(B.X-A.X)*(C.Y-A.Y)-(B.Y-A.Y)*(C.X-A.X)ifdet>0:return1# C is on the left of the line ABelifdet<0:return0# C is on the right of the line ABelse:return-1# A B and C are colineardefmelkman(path):ifposition(path[0],path[1],path[2])==1:hull=deque([path[2],path[0],path[1],path[2]])else:hull=deque([path[2],path[1],path[0],path[2]])forvinpath[3:]:ifposition(hull[0],hull[1],v)==1andposition(hull[-2],hull[-1],v)==1:continuewhileposition(hull[0],hull[1],v)<=0:hull.popleft()hull.appendleft(0,v)whileposition(hull[-2],hull[-1],v)<=0:hull.pop()hull.append(v)returnhull
Stacks and queues can be seen as a particular kinds ofpriority queues, with the priority determined by the order in which the elements are inserted. Similarly a deque can implement a priority queue with two levels of priority: high priority elements are added to the front side of the deque while low priority ones are added to the rear.[15] Unless an element could be canceled or stolen and then ejected from the bottom, an output-restricted deque is adequate.
Thus it's possible to modify the standardDijkstra's algorithm to findsingle source shortest path in a graph with 0-cost and 1-cost edges. A deque substitutes themin-priority queue. 0-cost elements are enqueued in front of the deque (high-priority) and then are always processed before the higher cost elements (low-priority) that are enqueued at the rear end.
A deque is used in thework stealing algorithm.[16] This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it. The work stealing algorithm is used by Intel's Threading Building Blocks (TBB) library for parallel programming.
ADeque automaton (DA) is a finite-state machine equipped with a deque auxiliary memory. It generalizesPushdown automaton (PDA) (stack automaton) andQueue automaton (Pull up automaton, PUA). As such it is equivalent to aTuring machine, and therefore it can process the same class offormal languages. But unlike the PDA and the PUA which impose serialization, a deque automaton permits parallel or interleaved execution of some operations.[17]
{{citation}}: CS1 maint: publisher location (link)