Double-ended queue: Difference between revisions

{{redirect-distinguish2|Deque|dequeueing, a [[queue (abstract data type)|queue]] operation}}

{{tooshort|date=April 2022}}

In [[computer science]], a '''double-ended queue''' (abbreviated to '''deque''', {{IPAc-en|d|ɛ|k}} {{Respell|DEK}}<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>) is an [[abstract data type]] that generalizes a [[queue (data structure)|queue]], for which elements can be added to or removed from either the front (head) or back (tail).<ref>[[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 1: ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89683-4}}. Section 2.2.1: Stacks, Queues, and Deques, pp. 238&ndash;243.</ref> It is also often called a '''head-tail linked list''', though properly this refers to a specific [[data structure]] ''[[#Implementations|implementation]]'' of a deque (see below).

''Deque'' is sometimes written ''dequeue'', but this use is generally deprecated in technical literature or technical writing because ''dequeue'' is also a verb meaning "to remove from a queue". Nevertheless, several [[Library (computing)|libraries]] and some writers, such as [[Alfred Aho|Aho]], [[John Hopcroft|Hopcroft]], and [[Jeffrey Ullman|Ullman]] in their textbook ''Data Structures and Algorithms'', spell it ''dequeue''. [[John C. Mitchell|John Mitchell]], author of ''Concepts in Programming Languages,'' also uses this terminology.

==Distinctions and sub-types==

This differs from the queue abstract data type or ''first in first out'' list ([[FIFO (computing and electronics)|FIFO]]), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:

*An input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.

*An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.

Both the basic and most common list types in computing, [[queue (data structure)|queue]]s and [[stack (data structure)|stack]]s can be considered specializations of deques, and can be implemented using deques. A deque is a data structure that allows users to perform push and pop operations at both ends, providing flexibility in managing the order of elements.

The basic operations on a deque are ''enqueue'' and ''dequeue'' on either end. Also generally implemented are ''[[Peek (data type operation)|peek]]'' operations, which return the value at that end without dequeuing it.

Names vary between languages; major implementations include:

{| class="wikitable"

! operation !! common name(s) !! [[Ada (programming language)|Ada]] !! [[C++]]!![[Java (programming language)|Java]] !! [[Perl]] !! [[PHP]] !! [[Python (programming language)|Python]] !! [[Ruby (programming language)|Ruby]]

![[Rust (programming language)|Rust]]

| insert element at back || inject, snoc, push ||<code>Append</code> || <code>push_back</code> || <code>offerLast</code> || <code>push</code> || <code>array_push</code> || <code>append</code> || <code>push</code>  

|<code>push_back</code>||<code>push</code>

| insert element at front || push, cons || <code>Prepend</code> || <code>push_front</code> || <code>offerFirst</code> || <code>unshift</code> || <code>array_unshift</code> || <code>appendleft</code> || <code>unshift</code>

|<code>push_front</code>||<code>unshift</code>

| remove last element || eject || <code>Delete_Last</code> || <code>pop_back</code> || <code>pollLast</code> || <code>pop</code> || <code>array_pop</code> || <code>pop</code> || <code>pop</code>

| remove first element || pop || <code>Delete_First</code> || <code>pop_front</code> || <code>pollFirst</code> || <code>shift</code> || <code>array_shift</code> || <code>popleft</code> || <code>shift</code>

| examine last element || peek

| <code>Last_Element</code> || <code>back</code> || <code>peekLast</code> || <code>$array[-1]</code> || <code>end</code> || <code><obj>[-1]</code> || <code>last</code>  

|<code>back</code>||<code><obj>.at(-1)</code>

| examine first element || || <code>First_Element</code> || <code>front</code> || <code>peekFirst</code> || <code>$array[0]</code> || <code>reset</code> || <code><obj>[0]</code> || <code>first</code>  

|<code>front</code>||<code><obj>[0]</code>

== Implementations ==

There are at least two common ways to efficiently implement a deque: with a modified [[dynamic array]] or with a [[doubly linked list]].

The dynamic array approach uses a variant of a [[dynamic array]] that can grow from both ends, sometimes called '''array deques'''. These array deques have all the properties of a dynamic array, such as constant-time [[random access]], good [[locality of reference]], and inefficient insertion/removal in the middle, with the addition of amortized constant-time insertion/removal at both ends, instead of just one end. Three common implementations include:

* Storing deque contents in a [[circular buffer]], and only resizing when the buffer becomes full. This decreases the frequency of resizings.

* Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.

* Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

===Purely functional implementation===

Double-ended queues can also be implemented as a [[purely functional data structure]].<ref name="functional">{{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|115}} Two versions of the implementation exist. The first one, called '''real-time deque'', is presented below. It allows the queue to be [[persistent data structure|persistent]] with operations in {{math|''O''(1)}} worst-case time, but requires [[lazy evaluation|lazy]] lists with [[memoization]]. The second one, with no lazy lists nor memoization is presented at the end of the sections. Its [[amortized analysis|amortized]] time is {{math|''O''(1)}} if the persistency is not used; but the worst-time complexity of an operation is {{math|''O''(''n'')}} where {{mvar|n}} is the number of elements in the double-ended queue.

Let us recall that, for a list <code>l</code>, <code>|l|</code> denotes its length, that <code>NIL</code> represents an empty list and <code>CONS(h, t)</code> represents the list whose head is <code>h</code> and whose tail is <code>t</code>. The functions <code>drop(i, l)</code> and <code>take(i, l)</code> return the list <code>l</code> without its first <code>i</code> elements, and the first <code>i</code> elements of <code>l</code>, respectively. Or, if <code>|l| < i</code>, they return the empty list and <code>l</code> respectively.

A double-ended queue is represented as a sextuple <code>(len_front, front, tail_front, len_rear, rear, tail_rear)</code> where <code>front</code> is a [[linked list]] which contains the front of the queue of length <code>len_front</code>. Similarly, <code>rear</code> is a linked list which represents the reverse of the rear of the queue, of length <code>len_rear</code>. Furthermore, it is assured that <code>|front| ≤ 2|rear|+1</code> and <code>|rear| ≤ 2|front|+1</code> - intuitively, it means that both the front and the rear contains between a third minus one and two thirds plus one of the elements. Finally, <code>tail_front</code> and <code>tail_rear</code> are tails of <code>front</code> and of <code>rear</code>, they allow scheduling the moment where some lazy operations are forced. Note that, when a double-ended queue contains <code>n</code> elements in the front list and <code>n</code> elements in the rear list, then the inequality invariant remains satisfied after <code>i</code> insertions and <code>d</code> deletions when <code>(i+d) &leq; n/2</code>. That is, at most <code>n/2</code> operations can happen between each rebalancing.

Let us first give an implementation of the various operations that affect the front of the deque - cons, head and tail. Those implementations do not necessarily respect the invariant. In a second time we'll explain how to modify a deque which does not satisfy the invariant into one which satisfies it. However, they use the invariant, in that if the front is empty then the rear has at most one element. The operations affecting the rear of the list are defined similarly by symmetry.  

<syntaxhighlight lang="sml">

empty = (0, NIL, NIL, 0, NIL, NIL)

fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =

  (len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))

fun head((_, CONS(h, _), _, _, _, _)) = h

fun head((_, NIL, _, _, CONS(h, NIL), _)) = h

fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =

  (len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))

fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty 

It remains to explain how to define a method <code>balance</code> that rebalance the deque if <code>insert'</code> or <code>tail</code> broke the invariant. The method <code>insert</code> and <code>tail</code> can be defined by first applying <code>insert'</code> and <code>tail'</code> and then applying <code>balance</code>.

    let val front' = take(ceil_half_len, front)

        val rear' = rotateDrop(rear, floor_half_len, front)

    in (ceil_half_len, front', front', floor_half_len, rear', rear')

    let val rear' = take(floor_half_len, rear)

        val front' = rotateDrop(front, ceil_half_len, rear)

    in (ceil_half_len, front', front', floor_half_len, rear', rear')

where <code>rotateDrop(front, i, rear))</code> return the concatenation of <code>front</code> and of <code>drop(i, rear)</code>. That is<code>front' = rotateDrop(front, ceil_half_len, rear)</code> put into <code>front'</code> the content of <code>front</code> and the content of <code>rear</code> that is not already in <code>rear'</code>. Since dropping <code>n</code> elements takes <math>O(n)</math> time, we use laziness to ensure that elements are dropped two by two, with two drops being done during each <code>tail'</code> and each <code>insert'</code> operation.  

<syntaxhighlight lang="sml">

fun rotateDrop(front, i, rear) =

  if i < 2 then rotateRev(front, drop(i, rear), NIL)

  else let CONS(x, front') = front in

    CONS(x, rotateDrop(front', j-2, drop(2, rear)))

</syntaxhighlight>

where <code>rotateRev(front, middle, rear)</code> is a function that returns the front, followed by the middle reversed, followed by the rear. This function is also defined using laziness to ensure that it can be computed step by step, with one step executed during each <code>insert'</code> and <code>tail'</code> and taking a constant time. This function uses the invariant that <code>|rear|-2|front|</code> is 2 or 3.

fun rotateRev(NIL, rear, a) =

  reverse(rear)++a

fun rotateRev(CONS(x, front), rear, a) =

  CONS(x, rotateRev(front, drop(2, rear), reverse(take(2, rear))++a))

where <code>++</code> is the function concatenating two lists.

==== Implementation without laziness ====

Note that, without the lazy part of the implementation, this would be a non-persistent implementation of queue in {{math|''O''(1)}} [[amortized analysis|amortized time]]. In this case, the lists <code>tail_front</code> and <code>tail_rear</code> could be removed from the representation of the double-ended queue.

== Language support ==

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.

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.

[[Glasgow Haskell Compiler|GHC]]'s [http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html Data.Sequence] module implements an efficient, functional deque structure in [[Haskell (programming language)|Haskell]]. The implementation uses [[2–3 tree|2–3 finger trees]] annotated with sizes. There are other (fast) possibilities to implement purely functional (thus also [[persistent data structure|persistent]]) double queues (most using heavily [[lazy evaluation]]).<ref name="functional"/><ref>Adam L. Buchsbaum and Robert E. Tarjan. Confluently persistent deques via data structural bootstrapping. Journal of Algorithms, 18(3):513–547, May 1995. (pp. 58, 101, 125)</ref> Kaplan and Tarjan were the first to implement optimal confluently persistent catenable deques.<ref>Haim Kaplan and Robert E. Tarjan. Purely functional representations of catenable sorted lists. In ACM Symposium on Theory of Computing, pages 202–211, May  1996. (pp. 4, 82, 84, 124)</ref> Their implementation was strictly purely functional in the sense that it did not use lazy evaluation. Okasaki simplified the data structure by using lazy evaluation with a bootstrapped data structure and degrading the performance bounds from worst-case to amortized.<ref>Chris Okasaki (Aug. 1997), [https://dl.acm.org/doi/10.1145/258949.258956 Catenable double-ended queues], ACM SIGPLAN Notices Volume 32 Issue 8</ref> Kaplan, Okasaki, and Tarjan produced a simpler, non-bootstrapped, amortized version that can be implemented either using lazy evaluation or more efficiently using mutation in a broader but still restricted fashion.<ref> Haim Kaplan, Chris Okasaki, and Robert E. Tarjan (2000), [https://epubs.siam.org/doi/10.1137/S0097539798339430 Simple Confluently Persistent Catenable Lists], SIAM Journal on Computing Vol. 30, Iss. 3</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.<ref>Radu Mihaescu and Robert Tarjan (Aug. 2003), [https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20Catenable%20Deques.doc Notes on Catenable Deques in Pure Lisp], Princetown University, COS 528, Fall 03</ref>

== Complexity ==

* 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|O(1)]]. Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).

* In a growing array, the [[Amortized analysis|amortized]] time complexity of all deque operations is [[Big O notation|O(1)]]. Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is [[Big O notation|O(n)]].

== Applications ==

[[File:Back button history (Ecosia browser - Google Pixel 4a) - Google Android 12 (cropped).png|thumb|A double-ended queue can be used to store the [[Web browsing history|browsing history]]: new websites are added to the end of the queue, while the oldest entries will be deleted when the history is too large. When a user asks to clear the browsing history for the past hour, the most recently added entries are removed.]]

One example where a deque can be used is 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 |url=http://supertech.csail.mit.edu/papers/ft_gateway.pdf |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.