CMIS 240  DE

Week 7

Queues.

A queue data structure is similar to a real-life queue (or "line" as
we Americans call it) 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 and makes its
way to the front 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 front 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.

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.

Queues are also used in simulation software.  Events occur and if they
can't be handled or serviced immediately (speed mismatch problem) they
are put into a queue for future servicing when the server becomes
free.  There can be multiple queues and/or multiple servers.  Grocery
stores have multiple servers, each with its own queue.  Banks
typically have multiple servers, but with one common queue (this
minimizes the average waiting time of customers ("clients")).  A one
server-multiple queues system would be six lanes of traffic funneling
into one tollgate (this maximizes the average road rage of clients).

Download, install, experiment with, and understand the example queue
program in Chapter4/QueType/ directory on the class web site.  It's
three files:
queuedr.cpp
QueType.h           
QueType.cpp
It uses the circular wrap-around array implementation described on
pages 228-233.
It also uses the ansiscreen.h screen control macros to show the queue,
so download that too.  If you don't have a computer with ANSI standard
screen control, comment out the call to the View member function in
main, or change the View function by removing the ansiscreen function
calls.  Regretably, Microsoft doesn't support this standard in 2000
and XP.