Double Ended Queue

A queue that allows items to be added or removed from either the front or the back of the queue. Often written as Deque and pronounced like "deck" to avoid confusing with DequeueOperation??. A DoubleEndedQueue is usually implemented using DoubleLinkedList.

The C++ StandardTemplateLibrary deque<T> isn't implemented in that way at all; it's implemented as a balanced array-of-arrays. Using rather clever allocation strategies; it has amortized O(1) performance for insertion/deletion at both front and rear, as well as for retrieval of an element. (However the "constant factors" for a deque are higher than for a vector<T>).

What are double ended queues used for?

And what's the 'clever' allocation strategy of the STL version?

Deques are useful (in C++ at least) when you need both O(1) random access, and ability to delete/insert at the ends. (You still cannot delete/insert in the middle in O(1) time; that requires O(n) time still).

Deques work by maintaining a two-tier structure. The top tier is an array of pointers to fragments of equal size, except possibly at the ends; each fragment contains an array of elements contained. Random access is done by looking up the index in the toplevel array (since each fragment contains an equal number of elements, excluding the ends, this can be done in O(1) time), going to that fragment, and lookup up correct element (a modulo operation, also O(1)).

I cannot recall exactly the details of how insertion/deletion work in a deque. Like vector, amortized O(1) performance at the tail is achieved with a) keeping additional buffer space so reallocation is rare, and b) doubling the size of the buffer each time a realloc is needed. Somebody more knowledgeable than I will have to fill in the rest of the details.

For most applications, you're better off with vector<T> if you need fast random access, or list<T> if you need fast insertion/deletion. deque<T> is a compromise - I don't recall ever having to use it.

-- ScottJohnson

They're useful when a professor tells you to implement a solution using a Deque on a final exam. (I didn't want to insert the above answer until someone gave you a real one, thank you Scott.)

CategoryDataStructure