A queue is a chronologically ordered list; the only difference between a stack and a queue is that, in a stack, elements are added and removed at the same end (the top), whereas in a queue, values are added at one end (the rear) and removed from the other end (the front). The order of elements in a queue, therefore, perfectly reflects the order in which they were added: the first element added will be the first one removed (so queues are called FIFO - ``first in first out''), and the last one added will be the last one removed.
In everyday life, we encounter queues everywhere - a line of people waiting to buy a ticket or waiting to be served in a bank; all such lines of people are queues. The first person in line is the next one served, and when another person arrives, he/she joins the queue at the rear.
The specification of a queue is almost identical to that of a stack; rather than giving a full specification, I will only sketch the main points.
For all these operations to be constant-time, it is necessary to have constant-time access to both ends of the data structure representing the queue. We have seen several ways of doing this: circular lists, for example, or ordinary lists with pointers to both the first and last nodes.
For example, the queue containing 9-1-5 could be represented this way:
If we now did a SERVE operation, the value 9 would be returned and Q would be:
If we ENQUEUE 7 onto this queue, we get:
There are two main uses of queues in computing.