Homework 5
Two Implementations of Queues
Due: Tuesday, December 6, 2011 at 5pm
Abstract
Write two different queue implementations for the same interface. Show that
both of them work in a simulation of a queue of customers in a supermarket
or bank.
Outcomes
After successfully completing this assignment, you will
be able to...
- Program an implementation of an existing interface
- Build a queue from linked lists to implement this interface
- Build a queue from a fixed array to implement this interface
- Study existing code and adapt it
- Build a multi-file application in C
- Use makefiles to correctly build, rebuild, and clean your working directory
Before Starting
Re-read section 7.8.5 of Kernighan and Ritchie regarding malloc() and
free(), and review your lecture notes on linked lists. Also read
section 5.11 on command-line arguments.
The Assignment
Your programs should comprise multiple files, and you will build them by
creating makefiles and running make. Create two directories - one will
hold all the files for your linked-list queue implementation, and one
will hold all the files for your fixed-length array queue implementation.
You need to copy all the Homework 5 starter files into each directory.
To do the copying, use the Linux cd command to change to one of your
directories, and then copy the files using this command:
cp /cs/cs2301-b11/HW5_files/*.* .
Your directory should now contain the files Simulation.h, Simulation.c,
Statistics.h, Statistics.c, Queue.h, Queue.c, main.c. Repeat the copying
process for your second directory.
These files contain the code that simulates the arrival of customers at a
bank teller window or supermarket checkout line. Customers arrive at
random intervals. If the teller or or checkout clerk are free,
service begins immediately. Otherwise, the customer waits in the queue.
The time it takes to serve a customer is also random. When the teller
finishes with one customer, he/she begins serving the next customer in
the queue, if any, or waits patiently for a new arrival. The simulation
runs for a specified amount of time. At the end of that time, no new
arrivals are accepted, but all waiting customers are served.
The simulation outputs the average time from when a customer arrives to
when service is completed, along with the standard deviation, the maximum
waiting time of any customer, and the maximum number of customers in the
queue.
The simulation can be run with the following command:
HW5 simTime meanArrivalInterval meanServiceTime seed verbose
where
HW5 is the name of the executable file created by make. The first
three arguments may be integers or floats. The seed must be an
integer. If the word "verbose" is included, the simulation prints
out a lot of detail. Any of the operands may be defaulted, and if so,
all subsequent operands are also defaulted. The default values are
720 minutes of simulation time, an average of 2.0 minutes between
arrivals, an average service time of 2.0 minutes, a random number
seed of 1, and non-verbose operation.
Study the given code carefully. There may be one or more
questions about it on Exam 3.
You will notice that the simulation is fully implemented except for
one part - the queue model. The interface Queue.h contains
the functions needed by the simulation, but the file Queue.c
contains only stubs for these functions. If you were to build and
run this simulation, it would stop at the first queue operation with
an error message.
This is the essence of this assignment. You need to implement
Queue.c not once, but twice, using two different approaches.
These approaches are:
- A queue based on a linked list. In this standard C-programming model, Queue.c
defines a struct representing a node of a linked list. The data stored in
each node is a representation of a customer that has arrived. In addition,
each node has a link to the next node representing the next customer in the
queue. Finally, there are two pointers, one to the head of the queue and
one to the tail. New arrivals are added to the tail end of the queue and
waiting customers are served from the head of the queue. Each node is
obtained from malloc() when the customer arrives, and is released with
free() when the customer is served.
- A fixed array for a bounded queue. This model is typical of
the environment encountered in some embedded systems. In the model,
Queue.c defines an array in which the elements are structs
representing customers (as described above). Neither malloc() nor
free() are used. Instead, the size of the array is defined at compile time
to be large enough to handle the expected maximum number of customers in
the queue. Queue.c maintains two pointers or indices, one indicating
which element is currently the head of the queue and which element is the
tail of the queue. A new customer is copied at the location of the tail,
and the tail pointer or index is incremented to point to the next one,
with wrap-around occurring when the end of the array is encountered.
Likewise, waiting customers are copied from the location of the head,
and the head is also incremented in wrap-around fashion.
The existing simulation does not do any error checking to see if the queue
is
full. This is guaranteed to be a problem if the fixed size queue is not
large
enough to accomodate the maximum size needed by the program. It can also
be a problem if ou allow the linked list queue to grow to an unbounded size.
You must add this error checking and take appropriate action in the
case that the queue is full.
Deliverables
You will need to create two makefiles, one for each version of your program.
Each version of your program will be in a separate directory, as described
above. You must create a zip file for each version, consisting of the .c and .h files
and the makefile. Don't wait until the last minute to create and submit
your zip files. If you don't know how to create a zip file, get help well
before the due date of the assignment.
Here is what you should submit for the assignment:
- A README.txt file decribing the principal files, functions, and data
structures of your program, including a summary of the results of your
testing
- The two zip files as described above, one for each version of your program
- A listing of the verbose output from one non-trivial run using each
queue implementation using the same command line arguments (you may use
redirected output to obtain the listing)
Submit your files using the turnin command:
/cs/bin/turnin submit cs2301 PROJECT5 filenames
where filenames are the names of the README, zip files, and listing file.
Grading
This assignment is worth 50 points:
- Successful compilation of each version - 5 points
- README file as described - 5 points
- Correct linked list implementation of queue - 10 points
- Correct fixed-size array implementation of queue - 10 points
- Correct error checking for both types of queues - 10 points
- Two sample output files, one from each queue implementation
with the same command line arguments - 5 points
- Correct execution with the graders' test cases - 5 points
Programs must build successfully using your submitted make files
in order to receive any credit for functionality.
Programs submitted after 5pm on December 6 will be tagged as late,
and will be subject to the late homework
policy.