32. Queue


General Description

This is the only true computer science program in the book. It simulates how a 'queue' operates in the computer's memory. To remind you: there are two commonly used short-term storage methods you use in computer memories. By far the most common is the 'stack', which acts like a pile of books. The last book placed on the pile is the first book taken off the pile. It is fairly easy to keep track of what constitutes an empty pile. The 'queue', which is like a bus queue in some respects, works on the basis that the first into the queue is the first out of the queue.
Consider the queue below:
 
(Bus stop) 7
   When the bus comes number 1 joints the bus (only one seat free!). Numbers 8 & 9 join the queue, which if the queue does NOT shuffle forward, looks like this.
 
(Bus stop)  9
   Another bus comes and this time numbers 2 & 3 join the bus (not the rush hour). If the queue does not shuffle forward it will now look like this.
 
(Bus stop)    9
   Effectively, as people join the queue and catch the bus, the queue moves backwards down the street. This can happen in computer memory and can be avoided by 'shuffling forward' which in a long queue is very time consuming, or by keeping a 'notice board' of where the next free piece of pavement in the queue is and who is next on the bus, even if they do not 'seem' to be nearest the bus stop. Anyway, run the program and watch. To make the simulation more realistic the queue has been limited. Obviously it is a little inconvenient if a queue can grow so large in memory that it would over-write the program servicing it.
   This program runs on a Model 'A'.

Detailed Description

   Lines 10-310 Initialise variables and disable cursor and auto repeat. Enter Mode 7. Initialise queue contents to 0,0 and locate random start point.
   320-390 Main structure of program - lines 340-370 - clears the buffer and waits for character.
   470-630 PROCqueue displays updated queue with its pointers in double characters and prints the value of pointers.
   680-990 PROCadd. If queue full prints overflow message. If not expects hexadecimal number. Sound bleep if number out of range. Head of queue printer is updated. Messages and use data deleted from screen.
   1040-1180 PROCdelete. If queue empty, underflow message displayed. If not, display register pointing to tail of queue. Clear old pointer.
   1240-1290 Deals with overflow or underflow. Clears error message after eight seconds.

Educational Notes

For the good O-level candidates and A-level candidates this is a very clear graphical demonstration. It assumes a knowledge of hexadecimal, as the values to be entered into the queue should be in 'hex'. The 'output register' always contains the value of the last item taken out of the queue, even if for several goes you then add to the queue. The coloured arrows indicate the head and tail pointers, and the current position of the pointers is also given numerically. Ten minutes experimenting with the simulation has drummed into some of the A-level candidates what a lesson of teaching failed to do.