- ECE Home
- Undergraduate Studies
- Douglas Wilhelm Harder
- Algorithms and Data Structures Home
- Abstract Data Types
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.
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.
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.