CMIS 242

Queues.

A queue data structure is similar to a real-life queue (or "line" as
it's also called) of people at a cashier or theater box office.
There's a front of the queue and a rear.  An item (e.g. a "person"
object) joins the queue (i.e. "enqueues") at the rear ("tail") and makes its
way to the front ("head") of the queue as items closer to the front get removed
(i.e. "dequeued"); when the item becomes the item at the front of the
queue it will be the one dequeued.  The item at the head of the queue
is the one that's been in the queue the longest, the first one in is
the first one out (a queue is a FIFO list).  It's a seniority system,
with position determined solely by length of time in the queue.  No
cutting in line, no moving ahead of anyone, no dropping out of line.

Like a stack, a queue is a restricted kind of list.
Stack: access at one end ("top") of the list only for both add and remove.
Queue: access to add at one end ("tail"), access to remove at the other end ("head").
Like with a stack, there are situations where we want to access the data in this
resticted way, so it is better (i.e. safer, more reliable code and clearer 
to understand what's happening) to use this restricted list.

Queues are used many places in a computer system, where they are often
called buffers.  Basically wherever there's a speed mismatch between
two processes, one supplying data to another, if the "producer" can
generate data faster than the "consumer" can input it then the data
has to enqueued in a buffer (you wouldn't want the producer to have to
slow down to the speed of the consumer, it would be idling when it
could be doing other work).  An example is printing.  The OS (acting
on the behalf of users) can create print jobs much faster than the
printer can print them, so the jobs are placed in a queue where the
printer can get them as it is able. Other examples are the queue of
ready proccess waiting for their turn to execute in the CPU, packets
queued up in a router awaiting their turn to be routed onward to the
next hop in their journey through a network, queued pending disk read
and write operations.  These queues grow and shrink unpredictably.

With a queue, the data is processed in the same order as which it is
generated (the opposite of a stack, where the data is processed in the
reverse order of its creation or input).

Queues are also used in simulation software.  The simulated events
occur (or are generated) and if they can't be handled or serviced
immediately (e.g. speed mismatch problem) they are put into a queue
for future servicing when the server becomes free.  Often it's
important that the events are processed in the order in which they happen.

There can be multiple queues and/or multiple servers.  Grocery stores
have multiple servers, each with its own queue.  Banks typically have
multiple servers (the tellers), but with one common queue (this
minimizes the average waiting time of clients (the customers).  A one
server-multiple queues system would be six lanes of traffic funneling
into one tollgate (this maximizes the average road rage of clients).


A queue can be, and is recommended to be, implemented by the
LinkedList class of the Java Collections Framework.  You would only
rarely have to make your own queue class.

LinkedList is almost the same as ArrayList.  The difference is that it
is implemented by a linked list instead of an array like ArrayList and
so compared to ArrayList it is: 
--faster insert/delete (if location to insert or delete is already
known),
--insert/delete at either end is very fast and so the LinkedList is good
for a stack or queue.
--much slower random access (using an index).

Methods are the same as ArrayList.  It has some additional ones for
inserting and deleting at the beginning and end of the list:
--addLast() can be the enqueue operation (end of the LinkedList is the
tail of the queue).
--removeFirst() can be the dequeue operation (front of the LinkedList is
the head of the queue).

LinkedListTest.java demonstrates use of the LinkedList class.  It's
the same program as ArrayListTest.java except every "ArrayList" was
replaced by "LinkedList".


QueueTest.java is a basic demo of a queue implemented by a LinkedList.
The user can enqueue strings and dequeue the string at the head of the
queue.  A queue is typically of some maximum size (i.e. only so much
memory will be allocated to it) and so if the queue is full it can not
be enqueued onto.  Trying to dequeue from an empty queue is not
possible.  Both situations need to be dealt with somehow by client
code (the demo program just reports the attempt and disallows the
operation).  The LinkedList is essentially unbounded (can grow wtihout
limit) and so can implement a queue that is unbounded in size.  The
demo program allows both types of queue.

QueueTestRandom.java randomly enqueues and dequeues dummy objects onto
a queue and graphically shows the size of the queue at each
operation.  It can give you an image of how a typical queue grows and
shrinks.