Relation: explicitly defined linear ordering

The Abstract Deque defined on objects which are linearly ordered by the programmer. A new object placed into the deque may be explicitly placed at either the front or the back the back of the deque and a removal may also occur at either the front or the back of the deque.

Critical Operations for Abstract Deques

• Insert a new object at the front of the deque
  void push_front( Type ) const;
• Examine the front of the deque
  Type front() const
• Remove the object from the front of the deque
  void pop_front()
• Insert a new object at the back of the deque
  void push_back( Type ) const;
• Examine the back of the deque
  Type back() const
• Remove the object from the back of the deque
  void pop_back()

The functions are also referred to as void enqueue_head( Type ), Type head() const, void dequeue_head(), void enqueue_tail( Type ), Type tail() const, and void dequeue_tail(), respectively.

By restricting the relevant operations as compared to a general Abstract List, it is possible to make significant improvements in the run times.

Example Data Structures

The most common data structure for implementing deques are cyclic dynamic arrays and doubly linked lists. All operations are O(1); however, some operations on for dynamic arrays are amortized O(1).

The requirements of the STL, however, requires a hybrid structure as is shown in Figure 1: A doubly linked list requires too many allocations and deallocations of memory and accessing an object in the middle of a deque requires O(n) time; a dynamic array has the occasional operations which run in O(n) time.

Figure 1. Hybrid implementation of the Abstract Deque.

A good discussion of the STL deque data structure is Walter Storm's An In-Depth Study of the STL Deque Container.