Welcome to Programming and Data Structures

The standard library provides implementations of stacks and queues in the std::stack and std::queue classes. Both are templated classes that are declared much like a vector or a list, by specifying the type of item they will hold. For example, to declare queues of int and Person, you would write:

queue<int> intQueue;
queue<Person> registrationLine;

The std::queue<T> provides .push(T) to add an item to the back of the queue, and .pop() to remove an item from the front of the queue. It also provides .front() to look at the item at the front of the queue without removing it, and .back() to look at the item at the back of the queue without removing it. All of these operations are \(O(1)\text{.}\)

We used std::stack (without discussing it much) in Section 29.2. It provides .push(T) to add an item to the top of the stack, .pop() to remove an item from the top of the stack, and .top() to look at the item at the top of the stack without removing it. These operations are all \(O(1)\text{.}\)

Both of these classes are defined as container adapters. They provide a wrapper around an underlying container (like std::list) to provide the stack or queue interface. (They “adapt” the container to provide a specific interface. We can see this in the full prototype for std::stack:

template<
    class T,
    class Container = std::deque<T>
> class queue;

There are two types we can specify while making a std::stack. The first is the type of item the stack will store T. The other is the kind of underlying Container it will use to store those items. For example, to declare a stack of strings that uses a std::vector as the underlying container, you would write:

stack<string, vector<string>> stringStack;

The same is true for std::queue. We could specify that we want to use a std::list as the underlying container for a queue of integers like this:

queue<int, list<int>> intQueue;

The container adapter classes require that the underlying container support certain operations. For both stacks and queues, the underlying container must support adding and removing items from the back of the container. For queues, the underlying container must also support accessing the front item.

If you do not specify an underlying container type when declaring a stack or queue, the default container will be used. The default underlying container for both std::stack and std::queue is std::deque. So what is a std::deque?

A deque (pronounced “deck”) is a “double-ended queue”. It is a sequence container that tries to provide some of the advantages of both linked lists and array based lists. It allows adding and removing items from both the front and the back of the container efficiently (\(O(1)\)) and allows for efficient random access to elements (.at() is also \(O(1)\)).

Because it supports efficient addition and removal at both ends, it can be used as the underlying container for both stacks and queues. But it can also be used directly as a double-ended queue data structure. A std::deque provides .push_front() and .pop_front() methods to add and remove items from the front of the deque, in addition to the usual .push_back() and .pop_back() methods to add and remove items from the back.

The implementation of a std::deque typically involves storing items in fixed-size blocks, with the deque maintaining a map of pointers to these blocks:

This block-based structure allows the deque to efficiently add and remove items from both ends. When items are added or removed, they are added to the block closest to the end being modified. If a block becomes full or empty, the deque can allocate or deallocate blocks as needed.

If we ever reach the limits of the current map of blocks, the deque can create a new, larger map and copy the pointers to the existing blocks into the new map. This resize only requires copying pointers, not the actual data items, so it is relatively efficient. It also means that the actual data items in the blocks remain in the same place in memory, so any existing references or pointers to those items remain valid.

Note that in this structure you can figure out the exact location of any logical index within the deque by calculating which block it belongs to and the index within that block. For example, if we know that the blocks have a size of 3, and the first block in use is at index 2 in the map, and the first index in use in that block is 1, then we can calculate that logical index 0 is at block 2, index 1; logical index 1 is at block 2, index 2; logical index 2 is at block 3, index 0; logical index 3 is at block 3, index 1; and so on.