Editing Double-ended queue (section)

== 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.

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 [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>

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.