Homework 5
Two Implementations of Queues

Due: Tuesday, December 4, 2012 at 5pm

Abstract

Outcomes

• Program an implementation of an existing interface
• Build a queue from a linked list to implement this interface
• Build a queue from a fixed array to implement this interface
• Study existing code and understand how to use it
• Design a program that can accept command-line arguments

Before Starting

The Assignment

Your programs should comprise multiple files, and you will build them by running make (the makefile will be provided). Download and unzip the zip file at the following URL:

http://www.cs.wpi.edu/~cs2301/b12/hw5-files.zip

Your directory should now contain the files Simulation.h, Simulation.c, Statistics.h, Statistics.c, Queue.h, Queue-array.c, Queue-list.c, main.c, and makefile. (Note that you will be making changes only to the files Queue-array.c and Queue-list.c.)

These files contain the code that simulates the arrival of customers in the queue. Customers arrive at random intervals. If the bank teller is 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:

./PA5 simTime meanArrivalInterval meanServiceTime seed verbose

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 files Queue-array.c and Queue-list.c contain 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 the queue functions not once, but twice, using two different approaches. These approaches are:

• A queue based on a linked list. In this model, Queue-list.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.

  The pointers to the head and tail of the queue (and anything else needed to maintain the queue) may be defined globally in the file Queue-list.c, and thus are accessible to all of the queue functions defined in that file.

• A fixed array for a bounded queue. This model is typical of the environment encountered in some embedded systems. In the model, Queue-array.c defines an array in which the elements are structs representing customers. 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-array.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 indices for the head and the tail of the queue (and anything else needed to maintain the queue) may be defined globally in the file Queue-array.c, and thus are accessible to all of the queue functions defined in that file.

The existing simulation does not do any error checking to see if the queue is full. This will 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 you allow the linked list queue to grow to an unbounded size. You must add error checking and take appropriate action in the case that the queue is full.

Using the makefile

Deliverables

• A README.txt file decribing the principal files, functions, and data structures of your program, including a summary of the results of your testing
• Your two queue implementation files, Queue-array.c and Queue-list.c
• 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)

Grading

• Successful compilation of both versions without warnings via the given makefile - 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 (queue full, queue empty, etc.) 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