Homework 9


Assigned Thursday, March 26, 1998
Due Friday, April 3, 1998 at midnight
30 points


PART A
You will need to fully implement the following classes:

CircularList class
Stack class
Queue class

You might want to give the Stack class and Queue class main methods during the testing phase of your work. These main methods might prompt the user for integers, then put them into the Stack or Queue, then print out the Stack or Queue. Also test your functions that remove elements from the Stack or Queue. This would be a good way to test the functionality of the classes.

PART B
You are writing the code for an air traffic control system; specifically, a way to organize planes before takeoff. Each plane has a takeoff number (integer) assigned to it. However, the planes are not necessarily lined up in order of increasing takeoff numbers. This is your job. Here is a sketch of the runway system from the air (planes are represented by their takeoff ids:
				|
				| ^
				| | to takeoff (B)
	  unused runway 	|
	------------------------|
               (A)          \   |
                    	    |   3
                    one-way |   5
	    	    runway  |   2  Line of planes 
                      (D)   |   1        (C)
                            |   4
                            \___|
                                |
                                |  
                                |
Here's the plan: (C) is a queue of planes, (B) is another queue (the final, in-order one), and (A) is a stack. (A) is a stack because the unused runway is too narrow for planes to pass each other on it, thus the planes must leave this runway in the reverse order that they came (First-In, Last-Out). Use the following strategy: 1. In the hw09 class (main function) create two queues and one stack. One of the queues should be holding the original line of planes (C) in the order shown in the picture (the waiting queue). The other queue is the takeoff queue.
1) A plane can be taken off the C runway, and placed in either the A runway or the B runway.
2) Likewise, a plane can be taken off the A runway, and placed in either the B or C runways.
3) You determine (on paper) the sequence of such plane movements that will get the planes into runway B in the correct takeoff order. Then code that sequence of movements into your 'main' function. Your 'main' function does not ascertain the sequence of plane movements; if it does, you have done the extra credit problem. Below is a smaller example to show you what your screen output should look like. In this example, the original contents of (C) (the waiting queue) is: 2 3 1.
>javac example.java   
>java example        (you will just enter: java hw09)

Time to order some planes!
Removing a 2 from the waiting queue.
Pushing a 2 onto the stack.
Removing a 3 from the waiting queue.
Pushing a 3 onto the stack.
Removing a 1 from the waiting queue.
Adding a 1 to the takeoff queue.
Popping a 3 from the stack.
Adding a 3 to the waiting queue.
Popping a 2 from the stack. 
Adding a 2 to the waiting queue.
Removing a 3 from the waiting queue.
Pushing a 3 onto the stack.
Removing a 2 from the waiting queue.
Adding a 2 to the takeoff queue.
Popping a 3 from the stack.
Adding a 3 to the waiting queue.
Removing a 3 from the waiting queue.
Adding a 3 to the takeoff queue.
Planes ready for takeoff!

>

Notice that the above example does not check to see if an element that has just been popped from the stack is next in line for the takeoff queue. You can implement this check or not, your choice.
Also notice that you do not prompt the user for any input. You code the plane's order in the waiting queue (from the picture above) directly in your hw09 class main function.

EXTRA CREDIT (10 points)
In this homework you assumed an initial ordering of the five planes in the waiting queue. For extra credit, write a class called hw09ec that takes as input from the user two things. The first should be a number representing how many planes there are. The second thing is N numbers, ranging from 1 to N, with each number from 1 to N represented once (the ids). These numbers, in the order that they are entered, represent the ordering of the planes in the waiting queue. Your program should order the planes properly in the takeoff queue, using the same type of output format as above. When it is done with this task, it should ask the user whether there are more planes to be ordered (loop) and repeat the task until the user chooses to quit. NOTE: Do not ask consultants, TA's, or the professor any specific implementation questions for this extra credit problem. Questions which involve clarification of the problem are fine, but we will not give hints on how to implement this part.


Include the CircularList, Stack, Queue, and hw09 classes in a file called hw09.java. Submit this, with a README, as usual. If you are attempting the extra credit, put it in a file called hw09ec.java and include it in your hw09 directory when you submit.
If you code the extra credit first, you do not have to submit a separate hw09 class, since your hw09ec class will be able to solve the hw09 problem. If you are just submitting the hw09ec class, make SURE the program you are submitting works for the case given above (3 5 2 1 4), because if it doesn't, not only will you not get extra credit points, but you will probably also lose a significant amount of the base hw09 points!