The C++ standard library deque is a double-ended queue that supports adding and removing items efficiently at either the front or the back.

Inside STL: The deque, design

By Raymond Chen

From the article:

All three of the major implementations of the C++ standard library use the same basic structure for a deque, but they vary in both policy and implementation details.

First, let’s design a simple version of a deque that stores its elements in an array.

template<typename T>
struct simple_deque
{
    T* elements;
    T* first;
    T* last;
    size_t capacity;
};

For example, a deque of three integers might look like this:

capacity = 8

size = last − first = 3

 

The elements points to an array whose length is given by the capacity member’s value of 8. In that array, the first three elements are not in use, but which could be used in the future. We’ll call them spares. Next come three elements holding the values 1, 2, and 3, followed by two more spares. The first element in use (1) is pointed to by first, and one past the last element in use is pointed to by last.