View source for Double-ended queue

{{Short description|Abstract data type}}
{{redirect-distinguish-text|Deque|dequeueing, a [[queue (abstract data type)|queue]] operation}}
{{Distinguish|Double-ended priority queue}}
{{Distinguish|text=the concept used in [[Queueing theory]], also known as ''matched queues''}}
{{technical|date=April 2022}}

{{image frame |caption=Double-ended queue as a pipe
|content=
{{image label begin |image=Deque-01.svg |width=250 |float=right
  |text=Representation of a double-ended queue as a pipe
 }}
<div style="color:blue">
<div style="position:absolute;top:24%;left:18%;">Input</div>
<div style="position:absolute;top:67%;right:18%;">Input</div>
</div>
<div style="color:red">
<div style="position:absolute;top:24%;right:16%;">Output</div>
<div style="position:absolute;top:67%;left:15%;">Output</div>
</div>
<div style="text-align:right">
<div style="position:absolute;top:6%;right:4%;font-size:110%">''as a queue''</div>
<div style="position:absolute;bottom:6.5%;right:68%;font-size:110%">''as a stack''</div>
</div>
{{image label end}}
}}

In [[computer science]], a '''double-ended queue''' (abbreviated to '''deque''' — {{IPAc-en|d|ɛ|k}} {{Respell|DEK}}),  is an [[abstract data type]] that serves as a [[Container (abstract data type)|container]], with a restricted access to the stored items. As a [[generalization]] of both the [[Stack (abstract data type)|stack]] and the [[Queue (abstract data type)|queue]], the deque may have similar functions as a [[Data buffer|data buffer]]: it can be use both as a ''[[Data buffer|retainer]]'' (queue), or for [[backtracking]] (stack). However it offers greater flexibility in managing the order of elements and some algorithms are based on its functionalities.

==Description==
The double-ended queue is most often presented as a generalized queue, which gives its name. It is a queue that "allows insertions and deletions at both ends". The deque is also described as a generalization of the [[Stack (abstract data type)|stack]] abstract data structure, as "two stacks joined together at the base", with a shared bottom item, or as a combination of both the stack and the queue.<ref name="lewis">
{{cite book |last1=Lewis |first1=T. G. (Theodore Gyle)
|title=Applying data structures |date=1976 
|publisher=Houghton Mifflin |isbn=9780395240601 |page=56}}
</ref>
{{efn |"Why it is not called a double stack is a mystery, since that is at least as accurate a description", <ref name=amsbury>
{{cite book
 |title=Data structures : from arrays to priority queues
 | last=Amsbury |first=Wayne
 |publisher=Wadsworth |isbn= 9780534045906}}
</ref>{{rp|131}} }}
{{Efn|The deque can then be seen "as either a superqueue or a superstack".<ref name=lewis />}} And then conversely the queue and the stack are restricted forms of the deque.

Different analogies with real-world objects are used to described the deque. It is compared to a "deck of cards" with which the structure shares some properties and the pronunciation.<ref>
{{Cite book |last=Thomas |first=Pete |last2=Robinson |first2=Hugh |last3=Emms |first3=Judy 
|title=Abstract data types: their specification, representation, and use 
|date=1988 |publisher=Clarendon Press ; Oxford University Press |isbn=978-0-19-859663-9
|series=Oxford applied mathematics and computing science series 
|location=Oxford : New York |pages=142}}
</ref><ref name="knuth" />{{rp|239}}<ref>Jesse Liberty; Siddhartha Rao; Bradley Jones. ''C++ in One Hour a Day, Sams Teach Yourself'', Sixth Edition. Sams Publishing, 2009. {{ISBN|0-672-32941-7}}. Lesson 18: STL Dynamic Array Classes, pp. 486.</ref> The deque is also likened to a "necklace with beads that can be added and/or removed at either end". Like the queue, it is depicted as a set of items lined up in a pipe open at both ends ; unlike the queue, the items can move in both direction in the pipe. The "railroad model" introduced by Knuth (after [[Shunting yard algorithm|"Dijkstra's shunting yard"]]){{r|knuth|p=240}} focus on the similarity with the queue, with one input and one output, and switches to select the side of the deque to be accessed.<ref name=smith>
{{cite book |last=Smith |first=Harry F.|title=Data structures : form and function
|year=1987 |publisher=Harcourt Brace Jovanovich |isbn=9780155168206}}
</ref>{{rp|p=175}}[[File:Deque-railroad.svg|center|thumb|500x500px|Railroad model of a deque]]

The main operations on a deque are said to act on either ''side'' (or ''end'') of the structure: addition of an item into the collection (''enqueue''), removal of an item ''(dequeue''), and reading of an item (''peek''). At at a given point in time only two items can be accessed, from either side of the deque, based on the history of the structure. The designated item on one side is either the latest one that has been inserted on this side ([[LIFO (computing)|LIFO]] behavior), or, — if there is none&nbsp;—, the oldest one that has been inserted on the other side ([[FIFO (computing and electronics)|FIFO]] behavior). This [[Queueing theory#Service disciplines|service policy]] gives the structure more flexibility and versatility, but it is also more difficult to fathom and use.{{efn|"If two nodes are inserted at one end and removed from the other, they will exit in queue order. If they are both removed from the entry end, then they exit in  stack order. If they are removed from opposite ends, then their exit order is whimsical." {{r|amsbury|p=131}} }}

The six main operations on a deque may be described in two ways, based on the queue (or stack) operations: either by duplicating them, on each end of the structure (<code>add_left</code>, <code>add_right</code>, etc.), or by generalizing them with a parameter that indicates the location on which an operation is performed (<code>add(left,...)</code>, <code>add(right,...)</code>, etc.). Each approach has its merits: the first one allows the overloading of the operations but needs to have different names on each sides, while the second one simplifies the interface by halving the number of operations and allows to make use of the symmetry of the structure.<ref>
{{Cite book |last=Booch |first=Grady 
|title=Software components with Ada: structures, tools, and subsystems 
|date=1987 |publisher=Benjamin/Cummings Pub. Co |isbn=978-0-8053-0610-1 
|location=Menlo Park, Calif |at=Chapter 7}}
</ref> '''In what follows, we will go with the second option to avoid needless repetition.'''

The deque has two other possible sub-types (more restricted forms are useless) :
*An ''input-restricted deque'' is one where deletion can be made from either end, but insertion can be made at one end only. It is a queue with a back output, or a stack with a bottom output.
*An ''output-restricted deque'' is one where insertion can be made at either end, but deletion can be made from one end only. It is a queue with a front input, or a stack with bottom input.
Despite their limitations these sub-types have many [[#Applications|applications]] and some of their implementations may be simpler.

{{stack begin |margin=true}}
{{Table alignment}}
{|class="col1left defaultcenter" style="border-spacing:0 2px"
|+ ''Example of operations on a deque''<br><small>from an empty deque</small>
! style="width:8em;border-bottom:1px solid" |Operations
! colspan=7 style="border-bottom:1px solid" |Content
|- 
| ''add''(left,<code>DE</code>) ||{{deque|>>>|DE}}
|-
| ''add''(right,<code>CK</code>) ||{{deque|>>>|DE|CK}}
|-
| ''remove''(left) ||{{deque|>>>>|CK}}
|-
| ''add''(left,<code>STA</code>) ||{{deque|>>>|STA|CK}}
|-
| ''add''(right,<code>QUE</code>) ||{{deque|>>>|STA|CK|QUE}}
|-
| ''add''(right,<code>UE</code>) ||{{deque|>>>|STA|CK|QUE|UE}}
|-
| ''remove''(left) ||{{deque|>>>>|CK|QUE|UE}}
|-
| ''remove''(left) ||{{deque|>>>>>|QUE|UE}}
|-
| ''add''(left,<code>DE</code>) ||{{deque|>>>>|DE|QUE|UE}}
|-
| ''remove''(right) ||{{deque|>>>>|DE|QUE}}
|}
{{stack end}}
After Knuth,<ref name="knuth">{{cite book
 |last=Knuth |first=Donald Ervin |author-link=Donald Knuth
 |title=The Art of Computer Programming
 |title-link=The Art of Computer Programming
 |publisher=Addison-Wesley |publication-place=Reading, Mass |date=1997 
 |isbn=0-201-89683-4
 |volume=1: ''Fundamental Algorithms''
 |edition=3rd
 |at=Section 2.2.1: Stacks, Queues, and Deques
 }}</ref> these structures are often described as different forms of restricted ''linear lists'' , or [[sequence|sequences]]. They maintain the contained elements in a given order while only allow access to some of them: the first one and/or the last one in the sequence. However other authors object that they "hide their internal dynamism from the user"{{r|amsbury|p=139}} and only the common [[#Implementations|implementations]] are linear. They consider these ''restricted-access data structures'' are either:
*''semi-structured'': they have "a special or designated item but no logical relationship among the rest of the items", and "the operation that deletes an item takes no item as a parameter";<ref name="dale96">
{{Cite book
 |isbn = 978-0-66940000-7
 |title = Abstract Data Types: Specifications, Implementations, and Applications
 |last1 = Dale |first1 = Nell | author-link1=Nell_B._Dale
 |last2 = Walker |first2 = Henry M.
 |year = 1996 |publisher = Jones & Bartlett Learning }}</ref>{{rp|xiii,189}}
*or ''point structures'' "because only two points of a queue exist for the outside world"{{r|amsbury|p=129}}: the stack is then a one-point structure, while the queue and the deque are two-point structures.

For example, a deque can be implemented with a [[min-max heap]], or with a [[Set (abstract data type)|set]]: before an item is inserted, it is tagged with a [[integer]] used as its value in the heap, and that depends on the history of the container.{{R|name=dale96|location=A1}} The stored elements in a heap are not ordered and their locations depend on the internal state of the structure. Another common restricted access structure is the [[priority queue]], which is not a linear structure.

The deque can be generalized by the addition of some operations: a deque with heap order, or ''mindeque'', allows the ''find-min'' operation. Fast or even optimal catenation is also possible.<ref name=brass>
{{Cite book
 |last=Brass |first=Peter
 |title=Advanced data structures
 |date=2008 |publisher=Cambridge University Press
 |isbn=978-1-108-73551-3 |pages=272 |language=en}}
</ref>{{rp|p=276}}<ref>
{{cite journal | last1=Gajewska | first1=Hania | last2=Tarjan | first2=Robert E. | title=Deques with heap order | journal=Information Processing Letters | volume=22 | issue=4 | date=1986 | doi=10.1016/0020-0190(86)90028-1 | pages=197–200 | url=https://linkinghub.elsevier.com/retrieve/pii/0020019086900281 | access-date=2026-02-28| url-access=subscription }}
</ref><ref>
{{cite journal | last1=Buchsbaum | first1=Adam L. | last2=Sundar | first2=Rajamani | last3=Tarjan | first3=Robert E. | title=Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues | journal=SIAM Journal on Computing | volume=24 | issue=6 | date=1995 | issn=0097-5397 | doi=10.1137/S0097539792242144 | pages=1190–1206 | url=http://epubs.siam.org/doi/10.1137/S0097539792242144 | access-date=2026-02-28| url-access=subscription }}
</ref>

Some authors consider the deque structure as being of little use, less useful than its restricted forms, especially the stack and the queue.<ref name=lewis /><ref name=amsbury /><ref name=brass />{{Efn|"a data structure looking for an application!", cited by Roy S. Ellzey in 1989.<ref>{{Cite book |last=Ellzey |first=Roy S. |title=Data structures for computer information systems |date=1991 |publisher=Macmillan |isbn=978-0-574-18740-6 |edition=2nd |location=New York}}</ref>}}

{{notes}}

==Specification==
The deque is here considered as unbounded: it can contain an unlimited (and undefined) number of items. A bounded deque is possible, and requires a slightly different specification, but when an overflow occurs the behavior depends on the implementation: error value, exception, deletion, etc. 

Let a deque {{math|<var>d</var> &isin; D}}, an item {{math|<var>x</var> &isin; X}}, and a side (end) {{math|1=<var>e</var> &isin; E = {left,right<nowiki>}</nowiki> }} with {{math|1=&not; left = right}}

{{in5}}'''Key operations:''' with {{math|1=D<sup>*</sup> = D \ {Λ} }}
{{block indent|text={{unbulleted list 
|1={{math|1=''add'': E × X × D → D<sup>*</sup>}}
|2={{math|1=''remove'': E × D<sup>*</sup> → D}}
|3={{math|1=''read'': E × D<sup>*</sup> → X}}
|4={{math|1=''empty'': D → {&top;,&perp;} }}
}} }} 
As a linear structure, the deque can be specified in terms of catenation (noted "{{math|~}}") of sequences and singleton sequences (noted "{{math|< ... >}}").
{{block indent|text={{unbulleted list 
|1=Empty sequence: {{math|1=Λ = < >}}
|2={{math|1=''read''(left, <var>d</var>) = <var>x</var> &hArr; &exist; <var>d'</var> {{!}} <var>d</var> = < <var>x</var> > ~ <var>d'</var>}}
|3={{math|1=''read''(right, <var>d</var>) = <var>x</var> &hArr; &exist; <var>d'</var> {{!}} <var>d</var> = <var>d'</var> ~ < <var>x</var> >}}
|4={{math|1=''add''(left, <var>x</var>, <var>d</var>) = < <var>x</var> > ~ <var>d</var>}}
|5={{math|1=''add''(right, <var>x</var>, <var>d</var>) = <var>d</var> ~ < <var>x</var> >}}
|6={{math|1=''remove''(left, <var>d</var>) = <var>d'</var> &hArr; &exist; <var>x</var> {{!}} <var>d</var> = < <var>x</var> > ~ <var>d'</var>}}
|7={{math|1=''remove''(right, <var>d</var>) = <var>d'</var> &hArr; &exist; <var>x</var> {{!}} <var>d</var> = <var>d'</var> ~ < <var>x</var> >}}
}} }}

An [[Abstract data type#Axiomatic semantics|axiomatic specification]] (or [[Algebraic specification|algebraic]]) of the deque can be obtained by extending and merging those of the stack and the queue.<ref>{{Cite book |last=Defense Technical Information Center |url=http://archive.org/details/DTIC_ADA218855 |title=DTIC ADA218855: Automatic Runtime Consistency Checking and Debugging of Formally Specified Programs |date=1989-08-01 |language=english|pp=6-7}}</ref><ref>{{Cite book |last=Defense Technical Information Center |url=http://archive.org/details/DTIC_ADA311117 |title=DTIC ADA311117: Anna Package Specification: Case Studies. |date=1991-10-01 |page=41 |language=english}}</ref><ref>{{Cite book |last=Louden |first=Kenneth C. |title=Programming languages: principles and practice |date=1995 |publisher=PWS |isbn=978-0-534-93277-0 |edition=3. [print] |series=PWS-KENT series in computer science |location=Boston, MA}}</ref> (see Nguyen thesis for an alternative formulation<ref>{{Cite thesis |last=Nguyen |first=Doan Han |title=An architectural model for software component search |date=December 1995 |publisher=Monterey, California. Naval Postgraduate School |url=https://hdl.handle.net/10945/31350 |language=en-US|pp=108-109}}</ref>).

{{in5}}'''Axiomatic constraints:'''
{{col-float}}
{{block indent|text={{unbulleted list 
|1={{math|1=''empty''(Λ) = [[Truth value|&top;]]}}
|2={{math|1=''empty''(''add''(<var>e</var>, <var>x</var>, <var>d</var>)) = [[Truth value|&perp;]]}}
}}
*as a stack:{{unbulleted list |list_style=width:285pt;margin-left:0.8em
|1={{math|1=''read''(<var>e</var>, ''add''(<var>e</var>, <var>d</var>, <var>x</var>)) = <var>x</var>}}
|2={{NumBlk| |{{math|1=''remove''(<var>e</var>, ''add''(<var>e</var>, <var>x</var>, <var>d</var>)) = <var>d</var>}}|{{EquationRef|1}}}}
}} }}
{{col-float-break}}
{{block indent|text=<span></span><!-- needed for the next bullet to appear -->
*as a queue, {{math|1=&forall; <var>d</var> &ne; Λ}}:{{unbulleted list |list_style=width:285pt;margin-left:0.8em
|1={{math|1=''read''(&not;<var>e</var>, ''add''(<var>e</var>, <var>x</var>, Λ)) = <var>x</var> }}
|2={{math|1=''read''(&not;<var>e</var>, ''add''(<var>e</var>, <var>x</var>, <var>d</var>)) = ''read''(&not;<var>e</var>, <var>d</var>) }}
|3={{NumBlk| |{{math|1=''remove''(&not;<var>e</var>, ''add''(<var>e</var>, <var>x</var>, Λ)) = Λ}}|{{EquationRef|2}}}}
|4={{NumBlk| |{{math|1=''remove''(&not;<var>e</var>, ''add''(<var>e</var>, <var>x</var>, <var>d</var>)) = ''add''(<var>e</var>, <var>x</var>, ''remove''(&not;<var>e</var>, <var>d</var>))}}|{{EquationRef|3}}}}
}} }}
{{col-float-end}}

The sequence of operations in the previous example results in the following expression:

{{math|1=''d'' = ''remove''( right, ''add''(left, <code>DE</code>, ''remove''( left, ''remove''( left, ''add''(right, <code>UE</code>, ''add''(right, <code>QUE</code>, ''add''(left, <code>STA</code>, ''remove''(left, ''add''(right, <code>CK</code>, ''add''(left,<code>DE</code>,Λ) )))))))))}}

This can be simplified with the axioms {{EqNote|1}}, {{EqNote|2}} and {{EqNote|3}}. In order of application, from the empty deque :
{|style="margin-left:1.6em;white-space: nowrap;"
|colspan=3 {{CellCategory|4}}''add''(left,<code>DE</code>)||rowspan=2|{{rdelim}}{{su|p=(1)|b=→}} ''id''
|-
|{{CellCategory|2}}''add''(right,<code>CK</code>)||rowspan=2|{{rdelim}}{{su|p=(3)|b=→}}{{ldelim}}||{{CellCategory|3}}''remove''(left)
|-
|{{CellCategory|1}}''remove''(left)||colspan=5 {{CellCategory|4}}''add''(right,<code>CK</code>)||rowspan=4 width=5em|{{rdelim|round|5}}{{su|p=(2)|b=→}} ''id''
|-
|colspan=5 {{CellCategory|4}}''add''(left,<code>STA</code>)||rowspan=2|{{rdelim}}{{su|p=(1)|b=→}} ''id''
|-
|colspan=3 {{CellCategory|2}}''add''(right,<code>QUE</code>)||rowspan=2|{{rdelim}}{{su|p=(3)|b=→}}{{ldelim}} ||{{CellCategory|3}}''remove''(left)
|-
|{{CellCategory|2}}''add''(right,<code>UE</code>)||rowspan=2|{{rdelim}}{{su|p=(3)|b=→}}{{ldelim}}||{{CellCategory|1}}''remove''(left)||{{CellCategory|2}}''add''(right,<code>QUE</code>)||rowspan=2|{{rdelim}}{{su|p=(3)|b=→}}{{ldelim}}||{{CellCategory|3}}''remove''(left)
|-
|{{CellCategory|1}}''remove''(left)||{{CellCategory|2}}''add''(right,<code>UE</code>) ||rowspan=2|{{rdelim}}{{su|p=(3)|b=→}}{{ldelim}}||{{CellCategory|1}}''remove''(left)  ||{{CellCategory|6}}''add''(right,<code>QUE</code>)||rowspan=4|
{|style="border-collapse:separate;border-spacing:0 2px;"
|rowspan=3|{{rdelim|round|5}}→
|{{space}}
|-
|{{deque|DE|QUE}}
|-
|{{space}}
|}
|-
|colspan=3 {{CellCategory|1}}''remove''(left)||{{CellCategory|4}}''add''(right,<code>UE</code>))||rowspan=2 |{{rdelim}}{{su|p=(1)|b=→}} ''id''
|-
|{{CellCategory|2}}''add''(left,<code>DE</code>)||rowspan=2|{{rdelim}}{{su|p=(3)|b=→}}{{ldelim}}||colspan=3 {{CellCategory|3}}''remove''(right
|-
|{{CellCategory|1}}''remove''(right)||colspan=5 {{CellCategory|5}}''add''(left,<code>DE</code>)
|}
This results in the following expression:
:{{math|1=''d'' = ''add''(left,<code>DE</code>,''add''(right,<code>QUE</code>,Λ))}}
As a transformation from an empty sequence :
:{{math|1=< > {{overset|''add''(right,<code>QUE</code>)|&xmap;}} < <code>QUE</code> > {{overset|''add''(left,<code>DE</code>)|&xmap;}} < <code>DE</code>,<code>QUE</code> >}}

Conversely the stack and the queue can be specified axiomatically in terms of the deque.
{{Hidden|Inherited specification of the stack |
{{in5}}Let a stack {{math|<var>s</var> &isin; S &sub; D}}
{{col-float}}
{{block indent|text=Operations:{{unbulleted list |list_style=margin-left:1.6em
|1={{math|1=''top''(<var>s</var>) = ''read''(''left'',<var>s</var>), &forall; <var>s</var>&ne;Λ}}
|2={{math|1=''push''(<var>x</var>,<var>s</var>) = ''add''(''left'',<var>x</var>,<var>s</var>)}}
|3={{math|1=''pop''(<var>s</var>) = ''remove''(''left'',<var>s</var>), &forall; <var>s</var>&ne;Λ}}
}} }}
{{col-float-break|gap=2em}}
{{block indent|text=Axioms:{{unbulleted list |list_style=margin-left:1.6em
|1={{math|1=''top''(''push''(<var>x</var>,<var>s</var>)) = <var>x</var>}}
|2={{math|1=''pop''(''push''(<var>x</var>,<var>s</var>)) = <var>s</var>}}
}} }}
{{col-float-end}}
}}
{{Hidden|Inherited specification of the queue| 
{{in5}}Let a queue {{math|<var>q</var> &isin; Q &sub; D}}
{{col-float}}
{{block indent|text=Operations:{{unbulleted list |list_style=margin-left:1.6em
|1={{math|1=''front''(<var>q</var>) = ''read''(''left'',<var>q</var>), &forall; <var>q</var>&ne;Λ}}
|2={{math|1=''enqueue''(<var>x</var>,<var>q</var>) = ''add''(''right'',<var>x</var>,<var>q</var>)}}
|3={{math|1=''dequeue''(<var>q</var>) = ''remove''(''left'',<var>q</var>), &forall; q&ne;Λ}}
}} }}
{{col-float-break}}
{{block indent|text=Axioms:{{unbulleted list |list_style=margin-left:1.6em
|1={{math|1=''front''(''enqueue''(<var>x</var>,Λ)) = <var>x</var>}}
|2={{math|1=''front''(''enqueue''(<var>x</var>,<var>q</var>)) = ''front''(<var>q</var>), &forall; <var>q</var>&ne;Λ}}
|3={{math|1=''dequeue''(''enqueue''(<var>x</var>,Λ)) = Λ}}
|4={{math|1=''dequeue''(''enqueue''(<var>x</var>,<var>q</var>)) = ''enqueue''(<var>x</var>,''dequeue''(<var>q</var>)), &forall; <var>q</var>&ne;Λ}}
}} }}
{{col-float-end}}
}}

==Terminology==
The term ''deque'' ({{IPAc-en|d|ɛ|k}} {{Respell|DEK}}) is used as an [[abbreviation]] of <u>D</u>ouble-<u>E</u>nded <u>QUE</u>ue. ''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 a ''head-tail linked list'', though properly this refers to a [[#Implementations|specific implementation]].<br>An output-restricted deque may be designated as ''steque'' (for stack-ended queue).<ref name=okasaki_PFDS>{{cite thesis |url=https://www.cs.cmu.edu/~rwh/students/okasaki.pdf |first=Chris |last=Okasaki |title=Purely Functional Data Structures |type=Ph.D. thesis |date=September 1996 |publisher=Carnegie Mellon University |id=CMU-CS-96-177}}</ref>{{rp|53}}

There is no standard vocabulary associated with deques. The terms ''enqueue'' and ''dequeue'', 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:
*in analogy to a queue: ''enqueue'' and ''dequeue'', or ''push'' and ''pull'';
*in analogy to a stack: ''push'' and ''pop'' on one side, and possibly ''inject'' and ''eject'' on the other side;
*in analogy to a list: ''cons'' and ''uncons'' on one side, ''snoc'' and ''unsnoc'' on the other side; 
*in analogy to an array: ''append'' on one side, ''prepend'' on the other side, or ''shift'' and ''unshift''.
Unlike the associated data structures the deque is symmetrical. Its sides may be freely named according to the context:
*in analogy to a queue: ''front'' and ''back'';
*in analogy to a stack: ''top'' and ''bottom'';
*in analogy to a list: ''head'' or ''last'';
*in analogy to an array: ''first'' and ''end'', or ''first'' and ''last'';
*finally ''left'' and ''right'' preserves the original symmetry of the structure.
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'' and ''pop_back''. Terms from different analogies may be associated in a single context: ''append'' and ''pop'', ''push'' and ''shift'', or ''front'' and ''tail''. 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, the ''dequeue'' operation (that returns two values: the removed element and the new deque) is not used. It is replaced by a ''peek'' function (i.e. ''head'' and ''last'') and a function that returns the deque minus the end, i.e. ''tail'' and ''init''.

==Implementations==
There are at least two common ways to efficiently implement a deque, [[Linked list#Linked lists vs. dynamic arrays|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, several [[Purely functional data structure|purely functional]] implementations of the double-ended queue exist.

===Doubly linked list===
While a simple list may implement a deque, a [[doubly-linked list]] is more adequate for its symmetry to achieve a fast access to both ends of the list (''head'' and ''tail'', hence the name ''head-tail linked list''). The obvious solution is to manage two references; alternatively the deque can be built as a circular list.
[[File:doubly-linked-list.svg|frame|none|alt=A doubly linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.|A doubly linked list whose nodes contain three fields: the link to the previous node, an element value, and the link to the next node.]]
In a doubly-linked list implementation, and assuming no allocation/deallocation overhead, the [[Computational complexity theory|time complexity]] of all deque operations is [[Big O notation|{{math|O(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 is {{math|O(n)}}. Similarly, finding a specific element normally [[Linked list#Speeding up search|requires {{math|O(n)}} time]]. Linked data structures generally have poor locality of reference.

===Dynamic array===
[[File:Dynamic array.svg|thumb|Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast ([[constant time]]), while some are slow due to the need for [[Memory management|reallocation]] ({{math|Θ(''n'')}} time, labelled with turtles).]]In this case as well, while a [[dynamic array]] can be used to implement a deque, a variant that can grow from both ends is more appropriate. This is sometimes called ''array deques''. This can be achieved in various ways, e.g.:
*by offsetting the position of the first element of the array in the reserved memory: the unused space is distributed on both side of the data;
*with a [[Circular buffer|circular array]].

The ''[[Dynamic array#Geometric expansion and amortized cost|amortized]]'' time complexity of all deque operations with an ''array deque'' is [[Big O notation|{{math|O(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 are {{math|O(n)}}. Thank to the fast random access, finding an element in an ordered array is time {{math|O(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.

===Functional and persistent implementations===
Doubly linked lists cannot be used as [[Immutable_object|immutable data structures]]. And an immutable array would be highly inefficient (an array is often simulated by [[Tree_(abstract_data_type)|a tree]]). A purely functional implementation of the deque can be based on stack, that is easily implemented with a [[Linked lists#Doubly linked vs. singly linked|singly linked list]] as an immutable and [[Persistent data structure|persistent structure]].
{{Blockquote
|text=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 many ''pop'' or ''eject'' 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.
<br>[...]<br>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.
|style=font-style:italic;
|source=
{{cite conference | first1=Haim |last1=Kaplan |first2=Robert E. |last2=Tarjan |author-link2=Robert Tarjan |title=Persistent lists with catenation via recursive slow-down |book-title=Proc. of the 27th annual ACM symposium on Theory of computing |pages=93–102 |date=1995 |location=Las Vegas, Nevada |doi=10.1145/225058.225090 }}
(preliminary version of <ref name=KT1999/>)}}
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 in {{math|O(1)}} ''worst-case'' time. Another challenge is the real-time catenation of deques.
[[Chris Okasaki|Okasaki]] gives a simple solution that uses [[lazy evaluation|lazy lists]] combined with [[memoization]]. The stack to stack balancing is then partially automatic by means of a precise scheduling of incremental functions. <ref name=okasaki_PFDS/>{{rp|52−59}}{{rp|115}} However some authors deem such algorithm as not purely functional since memoization is considered as a [[Side effect (computer science)|side effect]].<ref name=KT1999/>{{rp|581}} Kaplan and Tarjan gives their own version of the purely functional deque (non-catenable), based on three ideas:<ref name=KT1999>{{cite journal |first1=Haim |last1=Kaplan |first2=Robert E. |last2=Tarjan |author-link2=Robert Tarjan |title=Purely Functional, Real-Time Deques with Catenation |journal=Journal of the ACM |volume=46 |issue=5 |year=1999 |pages=577–603 |url=https://dl.acm.org/doi/pdf/10.1145/324133.324139 |doi=10.1145/324133.324139 }}</ref>
*''data-structural bootstrapping'', resulting in a recursive structure that foresees the [[finger tree]]: a deque is a triple consisting of a sub-deque flanked by two size-bounded buffers. ''Enqueue'' and ''dequeue'' basically operate on the buffers (in real-time because of the bounded size), and move forward one step in the balancing process;
*''recursive slow down'', inspired by [[Redundant binary representation]] (RBR), where an additional <code>2</code> 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;<ref name=okasaki_PFDS/>{{rp|105}}
*and a modification of the spine of the finger tree-like structure (a stack) into a stack of stacks that can be thought of as a 2-level [[skip list]]. This allows a real-time access to the unbalanced sub-deques. In analogy to a RBR, the sub-stacks stand for contiguous blocks of <code>1</code> digits, that can be skipped to access the next <code>2</code>, 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 (in [[OCaml]] and [[Rocq]]), alongside a formal description and detailed analysis of the algorithm.<ref>{{cite arXiv|first1=Jules |last1=Viennot |first2=Arthur |last2=Wendling |first3=Armaël |last3=Guéneau |first4=François |last4=Pottier |date=2025-05-12 |title=Verified Purely Functional Catenable Real-Time Deques |class=cs.PL |eprint=2505.07681 }}</ref>

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 a ''binary 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.<ref>{{cite journal |first1=Haim |last1=Kaplan |first2=Chris |last2=Okasaki |first3=Robert E. |last3=Tarjan
|date=2000 |url=https://epubs.siam.org/doi/10.1137/S0097539798339430 |title=Simple Confluently Persistent Catenable Lists
|journal=SIAM Journal on Computing |volume=30 |issue=3 |pages=965–977 |doi=10.1137/S0097539798339430 |url-access=subscription | archive-url=https://web.archive.org/web/20100925041059/http://www.math.tau.ac.il/~haimk/adv-ds-2000/okasaki-kaplan-tarjan-sicomp.ps | archive-format=PS | archive-date=2010-09-25 }}</ref>
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).<ref name=MT2003>{{citation 
|last1=Mihaescu |first1=Radu |last2=Tarjan |first2=Robert 
|date=August 2003 
|title=Computer Science 528 Data Structures and Graph Algorithms 
|chapter=Notes on Catenable Deques in Pure Lisp |type=course handout 
|publisher=Princeton University |department=Computer science 
|url=https://www.cs.princeton.edu/courses/archive/fall03/cs528/ 
|chapter-url=https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20Catenable%20Deques.doc 
|chapter-format=DOC |archive-url=https://web.archive.org/web/20060917064618/https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20Catenable%20Deques.doc |archive-date=2006-09-17 }}</ref>

==Language support==
[[Ada (programming language)|Ada]]'s containers provides the generic packages <code>Ada.Containers.Vectors</code> and <code>Ada.Containers.Doubly_Linked_Lists</code>, for the dynamic array and linked list implementations, respectively.

[[File:UML deque.svg|right|UML class diagram of a double-ended queue]]C++'s [[Standard Template Library]] provides the class templates <code>std::deque</code> and <code>std::list</code>, for the multiple array and linked list implementations, respectively.

As of Java 6, Java's Collections Framework provides a new {{Javadoc:SE|java/util|Deque}} interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such as {{Javadoc:SE|java/util|ArrayDeque}} (also new in Java 6) and {{Javadoc:SE|java/util|LinkedList}}, providing the dynamic array and linked list implementations, respectively. However, the <code>ArrayDeque</code>, contrary to its name, does not support random access.

JavaScript's [https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array Array prototype] & [[Perl]]'s arrays have native support for both removing ([http://perldoc.perl.org/functions/shift.html shift] and [http://perldoc.perl.org/functions/pop.html pop]) and adding ([http://perldoc.perl.org/functions/unshift.html unshift] and [http://perldoc.perl.org/functions/push.html push]) elements on both ends.

Python 2.4 introduced the <code>collections</code> module with support for [https://docs.python.org/3/library/collections.html#deque-objects deque 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.

[[Glasgow Haskell Compiler|GHC]]'s [https://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html Data.Sequence] module implements an efficient, functional deque structure in [[Haskell]]. The implementation uses [[2–3 tree|2–3 finger trees]] annotated with sizes.

Rust's <code>std::collections</code> includes [https://doc.rust-lang.org/std/collections/struct.VecDeque.html VecDeque] which implements a double-ended queue using a growable ring buffer.

==Applications==
{{Floated box |width=32em
|1=<pre style="padding:0.3em;margin:0;margin-bottom:0.5em;background-color:">
R DELQUE.(J) - DELETES USER J FROM QUEUES
R ENDQUE.(J) - PLACES USER J AT END OF QUEUE LEVEL(J) 
R BEGQUE.(J) - PLACES USER J AT BEG OF QUEUE LEVEL(J)
</pre>
In 1965, before even the ''deque'' is named, a code excerpt from the ''[[Compatible Time-Sharing System|CTSS]] Technical notes'' describes three subroutines that manipulate the queues of "users". Only the first two subroutines are actually executed but the idea of a less restricted queue is there and coded in a library.<ref name="ctss">{{cite web | last=Saltzer | first=Jerome H. | title=CTSS Technical Notes |date=1965-03-15 |website=DSpace@MIT Home |url=https://dspace.mit.edu/handle/1721.1/149338 | access-date=2026-02-28 |pages=40-41}}</ref>
}}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. which only need access to the elements at both ends and one by one, are listed here.

===Monotonic queue===
An input-restricted deque can be used to build a ''monotonic queue'', i.e. a [[Sequence#Increasing_and_decreasing|sub-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 :
* Start with an empty deque,
* For each element in the input sequence:
** while the last element of the deque is greater (resp. smaller) than the current element, pop it out,
** push the current element into the deque.
<syntaxhighlight lang="c++">
std::deque<int> increasing_monotonic_queue(std::vector<int> &seq[])
{
  std::deque<int> q;
  for (std::size_t i = 0; i < seq.size(); i++) {
    while (!q.empty() && q.back() > seq[i])
      q.pop_back();
    q.push_back(seq[i]);
  }
  return q;
}
</syntaxhighlight>
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.<ref>{{cite web |title=Sliding Window Maximum  |website=GeeksForGeeks |date=27 May 2011 |url=https://www.geeksforgeeks.org/dsa/sliding-window-maximum-maximum-of-all-subarrays-of-size-k |archive-url=https://web.archive.org/web/20250803180020/https://www.geeksforgeeks.org/dsa/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/ |archive-date=August 3, 2025 }}</ref> The complexity of a naive solution is {{math|O(n.k)}} time and {{math|O(1)}} space, where ''n'' is the length of the input sequence and ''k'' the size of the window. A solution that uses some kind of search method is {{math|O(n.log n)}} time and {{math|O(n)}} space.

In the following code, the monotonic queue stores references to the elements of the sequence.
<syntaxhighlight lang="c++">
#include <vector>
#include <deque>

typedef std::vector<int>::const_iterator seq_iterator;
typedef std::deque<seq_iterator> monotonic_queue;

monotonic_queue & decreasing_monotonic_queue_push
( monotonic_queue &q, seq_iterator i )
{
  while (!q.empty() && *q.back() < *i)
    q.pop_back();
  q.push_back(i);
  return q;
}

std::vector<int> max_of_subarrays(std::vector<int> &seq, std::size_t win_sz )
{
  std::vector<int> max_of_sub;
  monotonic_queue decreasing;
  seq_iterator i = seq.begin();
  // scan the 1st window
  for ( size_t win_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 sequence
  for ( /*keep i*/; i < seq.end(); i++ )
    {
      if ( decreasing.front() <= i - win_sz )
        decreasing.pop_front(); // fall out of scope
      decreasing_monotonic_queue_push( decreasing, i );
      max_of_sub.push_back( *decreasing.front() );
    }
  return max_of_sub;
}
</syntaxhighlight>
Each element of the input sequence is pushed and popped at most once resulting in {{math|2.n}} operations. The time complexity is then {{math|O(n)}}. The space complexity is {{math|O(k)}}, the maximum size of the deque.

In a similar way a monotonic queue allows the optimization of some [[dynamic programming]] cases equivalent to the [[least-weight sub-sequence problem|''least-weight sub-sequence'' problem]] : [[shortest path problem]] for a weighted directed graph, [[Wrapping (text)|paragraph breaking]], etc. These problems are said to be ''convex'' or ''concave'', and then ''monotonic''. The time complexity is then reduced from {{math|O(n<sup>2</sup>)}} to {{math|O(n.log n)}}, and {{math|O(n)}} in conducive situations.
<ref>{{cite web |last=Yi |first=Richard |title=1D1D DP: A Dynamic Programming Optimization |url=https://richardyi.ca/blog/1d1d/index.html |archive-url=https://web.archive.org/web/20240116201110/https://richardyi.ca/blog/1d1d/index.html |archive-date= January 16, 2024}}</ref>
<ref>{{Citation |first1=Daniel S. |last1=Hirschberg |first2=Lawrence L. |last2=Larmore |title=The Least Weight Subsequence Problem |date=1985 |publisher=UC Irvine: Donald Bren School of Information and Computer Sciences |url=https://escholarship.org/uc/item/3b6710dc }}</ref>

An other direct application of the monotonic queue is the '''minimum queue''' or '''minqueue'''. In this case the count of items in the window varies. The minqueue is a data structure with a {{em|queue}} interface that additionally gives a direct access to the minimum stored item. The key operations are then ''enqueue'', ''dequeue'' and ''find min''. Despite the name alludes to the [[Heap (data structure)|(min/max-) heap]], the min/max-queue is not a [[priority queue]]: the order of the items is maintained from the enter to the exit (FIFO policy). A simple version of a min-queue with {{math|O(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.<ref name=brass />

===Convex hull of a simple polyline===
Melkman's algorithm computes the convex hull of a [[simple polygonal chain]] (or a [[simple 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.<ref>
{{cite journal
 | last = Melkman | first = Avraham A.
 | title = On-line construction of the convex hull of a simple polyline
 | doi = 10.1016/0020-0190(87)90086-X
 | journal = [[Information Processing Letters]] | volume = 25 | issue = 1
 | mr = 896397
 | pages = 11–12
 | year = 1987
 | url=https://linkinghub.elsevier.com/retrieve/pii/002001908790086X | url-access = subscription
 }}
</ref><ref>
{{cite book
 | last1=Li | first1=Fajie | last2=Klette | first2=Reinhard
 | title=Euclidean Shortest Paths | chapter=Convex Hulls in the Plane
 | publisher=Springer London | publication-place=London | date=2011
 | isbn=978-1-4471-2255-5 | doi=10.1007/978-1-4471-2256-2_4
 | url=http://link.springer.com/10.1007/978-1-4471-2256-2_4 | access-date=2026-02-10}}
</ref><ref>
{{cite web 
 | last1=Aloupis |first1=Greg
 | title=A History of Linear-time Convex Hull Algorithms for Simple Polygons
 | url=https://cgm.cs.mcgill.ca/~athens/cs601/Melkman.html 
 | website=The Computational Geometry Lab at McGill 
 | publisher=McGill University |access-date=10 February 2026 }}
</ref>
<syntaxhighlight lang="python">
from collections import deque

def position(A,B,C):  
	det=(B.X-A.X)*(C.Y-A.Y)-(B.Y-A.Y)*(C.X-A.X)
	if det>0:
		return 1 # C is on the left of the line AB
	elif det<0 :
		return 0 # C is on the right of the line AB
	else:
		return -1 # A B and C are colinear

def melkman(path):
	if position(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]])
	for v in path[3:] :
		if position(hull[0], hull[1], v) == 1 and position(hull[-2], hull[-1], v) == 1 : 
			continue
		while position(hull[0], hull[1], v) <= 0 :
			hull.popleft()
		hull.appendleft(0,v)
		while position(hull[-2], hull[-1], v) <=0 :
			hull.pop()
		hull.append(v)
    return hull
</syntaxhighlight>

===Simple priority queue===
Stacks and queues can be seen as a particular kinds of [[priority queue]]s, 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.<ref name=lewis /> 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 standard [[Dijkstra's algorithm]] to find [[Shortest_path_problem#Single-source shortest paths|single source shortest path]] in a graph with 0-cost and 1-cost edges. A deque substitutes the [[Priority_queue#Min-priority_queue|min-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 the [[Work stealing|work stealing algorithm]].<ref name="jacm">{{cite journal |last1=Blumofe |first1=Robert D. |first2=Charles E. |last2=Leiserson |author-link2=Charles E. Leiserson |title=Scheduling multithreaded computations by work stealing |journal=J ACM |volume=46 |issue=5 |year=1999 |pages=720–748 |doi=10.1145/324133.324234|s2cid=5428476 }}</ref> 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.

===Deque automaton===
A [[Deque automaton]] (DA) is a finite-state machine equipped with a deque auxiliary memory. It generalizes [[Pushdown automaton]] (PDA) (stack automaton) and [[Queue automaton]] (Pull up automaton,  PUA). As such it is equivalent to a [[Turing machine]], and therefore it can process the same class of [[formal languages]]. But unlike the PDA and the PUA which impose serialization, a deque automaton permits parallel or interleaved execution of some operations.<ref>{{cite journal |last1=Crespi-Reghizzi |first1=Stefano |last2=San Pietro |first2=Pierluigi |title=Deque automata, languages, and planar graph representations |journal=Theoretical Computer Science |volume=834 |year=2020 |pages=43–59 |doi=10.1016/j.tcs.2020.02.029 }}</ref>

== See also ==
*[[Pipeline (Unix)#pipe character|Pipe]]
*[[Priority queue]]

== References ==
{{reflist}}

== External links ==
* [http://ccodearchive.net/info/deque.html Type-safe open source deque implementation at Comprehensive C Archive Network]
* [http://www.sgi.com/tech/stl/Deque.html SGI STL Documentation: deque<T, Alloc>]
* [http://www.codeproject.com/KB/stl/vector_vs_deque.aspx Code Project: An In-Depth Study of the STL Deque Container]
* [http://www.martinbroadhurst.com/articles/deque.html Deque implementation in C] {{Webarchive|url=https://web.archive.org/web/20140306145414/http://www.martinbroadhurst.com/articles/deque.html |date=2014-03-06 }}
* [https://web.archive.org/web/20110714000645/http://www.ludvikjerabek.com/downloads.html VBScript implementation of stack, queue, deque, and Red-Black Tree]
* [https://code.google.com/p/deques/source/browse/ Multiple implementations of non-catenable deques in Haskell]

{{Data structures}}

[[Category:Abstract data types]]