CS230 Lab


Queue Implementations and Queue Applications



Set up

Start by downloading the lab8 folder from the cs server. This folder contains a (subset of the)javafoundations classes.


Task 0: recursion

On paper, write a recursive solution for the following problems, from the codingbat page:

A. array11()

B. countPairs()

Task 1: Radix Sort Algorithm

Here is a link to your lecture notes on Radix Sort. Please make sure to review this code, and try it on paper to sort 4 numbers, 3 digit-long each. This way you will be in a good position to start the implementation of this algorithm!


Task 2: LinkedQueue Implementation

Finish up the implementation of LinkedQueue class. Make sure you use your notebook and pencil(s) to draw your pictures! Have your questions ready!

Task 3: RadixSort Implementation

task 3A: Set up the RadixSort class, instance variables

Set up the following instance variables:

   private final int NUMBERLENGTH = 3; //the length of each number in the input.
   //Notice that, in this version, all input numbers have to have the same length.

   private final int BASE = 10; //number system we are working on

   private Vector<Integer> input, output; //to hold the input (unsorted) and output (sorted) numbers

task 3B Constructor

In the constructor, initialize the instance variables.

  • Fill in the input vector with some integers. Each one should have length 3 (NUMBERLENGTH).
  • Copy the input vector into the output vector. You will be working on the output vector, while maintaining the input unchanged. (for printing purposes at the end).

task 3C: toString() and main()

Write a public method toString() to print the input and output. At this point you should be able to test your code, although no sorting has happened yet. Write a main() method to do so.

task3D: processOnePosition()

This part may not be difficult to understand, but it is a bit hairy to write in java. We encourage you to check the following methods in the java API. Make a note of them in your notebook:

  • valueOf(), in the String class.
  • charAt(), in the String class. (You have used this method in the past).
  • getNumericValue(), in the Character class.

Write a private method, processOnePosition(int pos), which does exactly that: For each number in the output vector, it looks at its digit at position pos, and adds the number to the corresponding queue. For example, if the first input number is 763, and pos is 0, it adds the number 763 to the 3rd queue, since the number's digit at position 0 is 3.
You will need a number of Queues, here. Use a Vector to hold those Queues. As for a Queue implementation, you can either use the ArrayQueue one in the javafoundations folder you downloaded earlier, or the LinkedQueue from today's Task 2.

Once all numbers are added to the right queue, according to the Radix Sort algorithm, get them out of the queues, into the output vector.

task 3E: processAll()

Write a public method processAll(), which processes all the positions in the numbers, one after the other. This method should call the previous one, and be only a couple of lines long.

Lastly, test your code thoroughly.

If you have any extra time, think about how you would change your code to work on numbers of varying lengths.