CMPE 250 – DATA STRUCTURES & ALGORITHMS

Project #3

Due: 06.08.2006 Sunday at 24:00

Simulation of a Real Queue

This project asks you to implement the QUEUE ADT and the several operations that act on it (enqueue, dequeue, etc.). Your program must read an input file whose name is specified by the user and produce an output file named “output.txt”. Your objective is to simulate a queue that you are likely to encounter in the real life such as a bank queue or a bus queue. Let us start by stating that each customer in the queue gets his service in 10 time units when it is his turn (when he becomes the leader of the queue). The arrival of each customer to the queue is a random process which is not modeled but will be specified in the input file.

At each line of the input file, the index of the customer (starting with 1 and proceeding with one more at each new arrival) and the time at which she arrives will be written. The arrival of the first customer will be at time 0 and the arrivals are in chronological order. Both customer indices and arrival times will be integer quantities.

The format for input files (“my_input.txt”):

1 0          /* Customer 1 arrives at time 0 */

2 5          /* Customer 2 arrives at time 5 */

3 16        /* Customer 3 arrives at time 16 */

4 23        /* Customer 4 arrives at time 23 */

5 35        /* Customer 5 arrives at time 35 */

6 37        /* Customer 6 arrives at time 37 */

7 40        /* Customer 7 arrives at time 40 */

The operation of your program must be like the following:

1) The program starts by asking the name of the input file. The .txt extension will be input by the user (i.e. “my_input.txt”).

2) As dictated by the input, each customer is enqueued to the queue when he arrives and each customer is dequeued from the queue when she is the head of the queue and as soon as she has taken her service.

3) Your program must produce one output file “output.txt”. In this file, the operations that you perform during the lifetime of the queue will be output in chronological order. There are two operation types: enqueue and dequeue.

The format for output files

The customer index Operation type Time instant

The customer index Operation type Time instant

The customer index Operation type Time instant

.

.

.

Here is an example for the given input file (my_input.txt):

1 enqueue 0

2 enqueue 5

1 dequeue 10

3 enqueue 16

2 dequeue 20

4 enqueue 23

3 dequeue 30

5 enqueue 35

6 enqueue 37

4 dequeue 40

7 enqueue 40

5 dequeue 50

6 dequeue 60

7 dequeue 70

Project Notes

•  dequeue operations have priority over enqueue operations. That is, if they are to happen at the same instant, dequeue happens first.

• Arrivals at the same instant must be processed as in the order dictated by the input file.

• While reading input from the user via the keyboard, you can use Java dialogues (i.e. javax.swing.*).

Implementation Details

• Try to use object-oriented concepts as much as possible.
• Make sure your code compiles with JDK 5.0.

NOTES:

• Source code should be cleverly commented (Do not exaggerate!).
• For each project you should write a report explaining design and implementation issues as well as anything a person may need to know while testing your program.
• The document format may be like the one linked via the course’s web site. But you are not restricted to that format. You may cancel irrelevant sections, include sections of your own, etc.

• For projects, you need to submit your .java files, .class files and your document. The instructions on how to do and submit your projects are at the course web site. The instructions leave no questions to be answered.

• Late giving policy may be strict, so try to finish on time.
• Do not cheat!