Queues

The order of elements in a queue reflects the order in which they were added.

First added will be first removed (FIFO).

Last added will be last removed.

For these operations to be constant-time, we need constant-time access to both ends of the data structure representing the queue.

We could use circular lists, or ordinary lists with pointers to both the first and last nodes.