The next data structure we will consider is the queue. Queues are very similar to stacks in their simplicity, and support O(1) insertion, deletion and element access at one end. As you might expect they are structured exactly like a physical queue of people waiting in line. When somebody joins the queue, they join from the back, but when somebody leaves the queue, they leave from the front. Queues are therefore FIFO data structures; the First element In is the First element Out. This causes them to be similar to—but fundamentally different from—a stack. Both have single end push/pop operations, but in a stack all operations are performed on one end, whereas in a queue they are performed on a mixture of both.

These are then our requirements for a queue:

• O(1) insertion at one end
• O(1) deletion at the other end
• O(1) element access at both ends
• High space efficiency (ideally)

Could we use a vector this time? In fact we can’t, as vectors support O(1) insertion and deletion at one end, but not both. This means we’re stuck with either a doubly-linked list, or a singly-linked list with a tail pointer. The list implementation from a few tutorials back already supports a queue, so I won’t rewrite the code here. Instead just imagine that we have a queue class with push, pop, front, and back operations.
STL provides a queue implementation, the queue class, which uses a list (or a deque) to store the queue. It’s usage is identical in format to every other STL container: