Queue |
A queue is defined to be a list in which all additions to the list are at end of the queue (tail) and all deletions are at the other end (front). Queues are also called first-in-first-out lists or FIFO lists.
Applications of queues are if anything more common than stacks. Within a computer system there are many queues (E.g. waiting in line for a printer, waiting access to disk storage, waiting time to access the CPU, the keyboard buffer).
Adding to a queue is called entering, deleting from the queue is called leaving.
Because entry is from the rear and leaving is from the front, a front and rear pointer is required.
Application areas |
An airport has planes arriving to land, and waiting to take off. Planes land in the
order they arrive and take off in the order they line up on the runway. Hence managing the
two queues is easily achieved using the queue data structure.
In the airports case it would make sense that the landing queue has priority over the take
off queue. (Planes in the air continue to use fuel!!).
One trick used to maintain queues in an array is to maintain a "head pointer" and a "tail pointer". As planes are added to the queue the tail is increased by one, and as planes are taken off the queue the "head pointer" is increased by one. In a computer an array usually has a finite size so we go circular, that is when we reach the end of the array instead of adding 1 to the head we reset the head back to the start of the array. This can cause problems if the head and the tail collide (the array becomes full).
Using the pointer method this problem does not arise.
In simulation and modelling where real world occurrences are modelled, queues are used extensively.
Working out the most efficient number of checkout in a supermarket, the customers form queues at each checkout.
When a job is sent to a network printer it is placed in the print queue. Unless overridden by an operator the first job into the queue is the first one printed.
|
A popular game written by trainee programmers is worm. Here a worm snakes around the screen in search of food. When it eats the food the worm grows in length. This is an ideal queue application, with the body locations maintained in an array with a queue structure. |
