CS112 Homework 7

Reading for the week:

Chapter 8.

Homework 7a, due Monday October 27, 1997.

Write a FIFO queue class using lists, as shown in class. Also write a tester program for it. (Your tester should be comparable to the stacktest.java stack tester that I wrote last week.

The methods for the queue are

       public queue (); // Effect: Make a new queue.
       public static int number_of_queues (); // Effect: How many queues have been made so far?
       public void enqueue (int v);  // Effect: Add v to the queue.
       public int dequeue ();        // Effect: Remove and return the oldest value from the queue.  Requires: the queue is nonempty.
       public boolean isempty ();
       

Be sure to document your program properly.

Call your tester queuetest.java. Submit your queue tester, and your queue, the list .java and .class files.

Homework 7b, due Wednesday October 29, 1997.

Add the following method to your queue class.

       public int length (); // Effect: Return the number of values in the queue. 
       

Note that after creating your first queue, you might want to not mess it up while working on your second one. You can do this by creating a new directory and working there.

       % mkdir 6b
       % cp *.java 6b
       % cd 6b
       

That will (1) make a new directory, (2) copy all java files to the new directory, and (3) connect you to the new directory so you can work on the new code without modifying the old code.

Homework 7c, due Friday October 31, 1997.

Write a program that takes lines from the standard input and prints them out in a different order, as specified here: Print the even-numbered lines in reverse order, followed by all of the odd-numbered lines. (The first line is line number 0, and is an even numbered line.)

Thus your program should do the following:

       % cat foo.data
       a
       b
       c
       d
       e
       % java backfor < foo.data
       e
       c
       a
       b
       d
       

The lines a, c, and e are the even-numbered lines and should be printed in reverse order. The lines b and d are the odd-numbered lines and should be printed in forward order.

(Remember what the greater-than sign means in Unix? It means take standard input from the file.)

Hint 1: Use a stack to hold the lines that should be reversed, and a queue to hold the lines that should not be reversed.

Hint 2: Take your reverselines program that you wrote with the stack. Next put in a test that only pushes the even numbered lines into the stack. Now you have a program that will print lines e, c, and a. Get that working properly before proceeding. Next add a queue to your program and put the odd numbered lines in there, and print that. Now you will have done the whole program.