Re: What is a queue?

[mfb@mbunix.mitre.org (Michael F Brenner)]

It is sometimes hard to find answers to questions in a particular
field. In computer science, a queue is an abstract data type
(sometimes called a class) which can be implemented by,
for example, an Ada package, in this case. The package would
have a type statement like the following:

     type queues is limited private;

and a bunch of methods for that type, such as the following:

     procedure add_to_left (object: objects; to: queues);
     procedure add_to_right (object: objects; to: queues);
     function take_from_left (queue: queues);
     function take_from_right (queue: queues);
     function image(queue: queues);
     no_more_objects_in_queue: exception;

as well as the constructors and destructors:

    procedure initialize (queue: in out queues);
    procedure finalize (queue: in out queues);
    procedure copy (queue: queues; target: in out queues);
    procedure "&" (left, right: queues) return queues;

As you can see, the basic methods permit you to add and things
to the left and right of the queue, and to take things from 
the left and right of the queue. If you attempt to take something
that does not have anything left, then you get a fatal error
that tells you there are no more objects in the queue.

Queues are used to handle situations where two processes are
going at different speeds. Then the queue acts like a buffer 
between the two processes. The faster process can put stuff on
the queue and the slower processor can take it off the queue
at its own rate. 

The word queue derives from the British cultural tradition of 
people lining up to get some service. The service is represented
mathematically by a giant circle, and the people lining up look
like a straight or curly line. Thus, the two together look like a
giant letter Q, which was then spelt queue to make it sound 
difficult to spell, which it is. Some Americans believe in
queueing up, also. However, there are sometimes advantages
to chaos, so do not use type queues for every situation you
program!

There is an interesting mathematical discipline of partial
differential equations called queuing theory that looks at
interesting effects on various queue configurations at 
different rates of arrivals and departures of the elements
of the queues, building up, in the discrete case to something
very interesting called finite state machines and their
enhancements called Colored Petri Nets.

But for your initial assignment, you need to implement a body
for the package queue_management. In this body, you will 
code the procedures whose interfaces are given above. In addition,
you will need to have some sort of heap management tool, such
as an unlimited sized vector (a modification of the in-RAM
array structures built into the Ada language, but extended
so that your doubly linked list has no upper limit, but 
overflows to virtual storage). 

Programming these things are fun, and will get you into
interesting things in dataflow control of distributed processes
and the mathematics of shape theory before you know it.

Good luck and enjoy queueing up.