Double-ended queue
[2] It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque (see below).
Nevertheless, several libraries and some writers, such as Aho, Hopcroft, and Ullman in their textbook Data Structures and Algorithms, spell it dequeue.
This differs from the queue abstract data type or first in first out list (FIFO), where elements can only be added to one end and removed from the other.
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.
It allows the queue to be persistent with operations in O(1) worst-case time, but requires lazy lists with memoization.
Its amortized time is O(1) if the persistency is not used; but the worst-time complexity of an operation is O(n) where n is the number of elements in the double-ended queue.
Finally, tail_front and tail_rear are tails of front and of rear, they allow scheduling the moment where some lazy operations are forced.
It remains to explain how to define a method balance that rebalance the deque if insert' or tail broke the invariant.
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.
There are other (fast) possibilities to implement purely functional (thus also persistent) double queues (most using heavily lazy evaluation).
[6] 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.
[7] 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.
[8] Rust's std::collections includes VecDeque which implements a double-ended queue using a growable ring buffer.
The work stealing algorithm is used by Intel's Threading Building Blocks (TBB) library for parallel programming.
