Language Support
Ada's containers provides the generic packages Ada.Containers.Vectors and Ada.Containers.Doubly_Linked_Lists, for the dynamic array and linked list implementations, respectively.
C++'s Standard Template Library provides the class templates std::deque and std::list, for the multiple array and linked list implementations, respectively.
As of Java 6, Java's Collections Framework provides a new Deque interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such as ArrayDeque (also new in Java 6) and LinkedList, providing the dynamic array and linked list implementations, respectively. However, the ArrayDeque, contrary to its name, does not support random access.
Python 2.4 introduced the collections module with support for deque objects.
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's Data.Sequence module implements an efficient, functional deque structure in Haskell. The implementation uses 2-3 finger trees annotated with sizes. There are other (fast) possibilities to implement purely functional (thus also persistent) double queues (most using heavily lazy evaluation). Kaplan and Tarjan were the first to implement optimal confluently persistent catenable deques. 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. 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. Mihaesau 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.
Read more about this topic: Double-ended Queue
Famous quotes containing the words language and/or support:
“Our language has wisely sensed these two sides of man’s being alone. It has created the word “loneliness” to express the pain of being alone. And it has created the word “solitude” to express the glory of being alone. Although, in daily life, we do not always distinguish these words, we should do so consistently and thus deepen our understanding of our human predicament.”
—Paul Tillich (1886–1965)
“I concluded that I was skilled, however poorly, at only one thing: marriage. And so I set about the business of selling myself and two children to some unsuspecting man who might think me a desirable second-hand mate, a man of good means and disposition willing to support another man’s children in some semblance of the style to which they were accustomed. My heart was not in the chase, but I was tired and there was no alternative. I could not afford freedom.”
—Barbara Howar (b. 1934)