A queue is a linked list in which insertion is restricted to one end and deletion to the other. A queue works on a First In First Out (FIFO) basis.  In general, items are added to the end of a queue, in the same way as we join at the end of a queue for a bus, and items are removed from the front of a queue – the people at the front of the queue for the bus can get on the bus first. As with bus queues, adding to the middle of a queue is discouraged!

We can represent this graphically as follows:


We assume that the name of the queue gives access to the last node as well as the first node.

Next: Binary Trees