11. The QUEUE

The QUEUE is another extremely common type of list data structure.

A queue is a First-In, First-Out list.

A queue maintains two pointers

1. A 'front of queue' pointer
2. An 'end of queue' pointer.

Uses of a queue

A queue data structure is used whenever there are a number of items waiting for a resource to become available. If you had three items added to a queue in this order 1. Dog 2.Cat 3. Horse the queue would look like this

The start pointer locates 'Dog' and the Rear pointer locates 'Horse'

The operations that are associated with a queue are

Example 1 - Printer queue

A printer queue will contain a number of jobs waiting to be processed, the next one to be processed is the first one that went into the queue.

Example 2 - Process queue

Another very common use of a queue is to handle processes running on the CPU. Only one process can run on the CPU at any given time, but there will be many processes wanting to run. So the operating system will add each process to a queue and allow the one at the front of the queue to get the next turn at running within the CPU.

Example 3 - A simulation queue

The first two examples are a normal part of an operating system. But the software programmer can also make use of the queue data structure to handle events within his application.

For example, if he was writing a traffic light simulator, a queue could be used to hold the states of the traffic light sequence. Each state could then be removed from the queue, one by one, to simulate traffic lights changing colours.