Lab 4 - Linked Queues and the Radix Sort

CSCI 151
Spring, 2018
Due:  11:59 pm, Sunday, March 10

In this week's lab you will be implementing your own version of the Queue data structure using a linked list, then use it to implement a sorting method called the Radix Sort.  You can get started by creating a lab4 directory and downloading the startup code in the file .

The purpose of the lab is to:

Part one:  Writing the LinkedQueue class

Write a class called LinkedQueue that implements the QueueADT interface found in the file.  Your implementation should be similar to the LinkedStack class in the examples folder.  You need to do the following in
  1. The header line of the class must say implements QueueADT<T>
  2. Define an inner class called QNode.
  3. Define two private instance variables of type QNode called front and rear, which are references to the front and rear nodes in the queue. 
  4. Write a no-argument constructor which instantiates an empty LinkedQueue.  In an empty LinkedQueue, both front and rear are null.
  5. Write implementations of the methods enqueue, dequeue, isEmpty, and clear.  All of these methods should be O(1).
  6. Write an additional method (not found in QueueADT), void append(LinkedQueue other), which appends the contents of other to this queue.  This method should operate by attaching the front node of other to the rear node of this.  It should also be O(1), which means that it should not loop through either list.  Make sure that you can handle the cases where either this or other (or both) is an empty queue.

Part two:  Testing

Write a JUnit test class for your LinkedQueue class.  Try creating LinkedQueues of both Integers and Strings, enqueueing and dequeueing some elements from each, and then checking the results.

Part three:   Implementing the radix sort

Radix sort is a sorting method which works by testing the characters of a set of strings, one at a time, from right to left.  Several passes are made over the data, one for each character position.  On the first pass, the strings are thrown into bins according to the final (i.e., rightmost) character of the string.  (For strings using the English alphabet, there would be 26 bins.)  After the all the strings are distributed into the bins, the contents of the bins are combined into a single list.  The process is then repeated by sorting this list into bins according to the next-to-last character, etc., until a final pass based on the first character.  When the final pass is completed, the entire list is in ascending lexicographic order.

For the algorithm to work correctly, it's necessary that the bins are maintained in FIFO order.  Because of this, each bin will be implemented with a Queue.  And because there will be 26 bins, our implementation will use an array (or ArrayList) of 26 LinkedQueues.

Write an application called which does the following:  (This is the main method in
  1. Create an array (or ArrayList) of 26 bins, one for each letter of the alphabet.  Each bin is represented by a LinkedQueue.  You need to first instantiate the array, then instantiate 26 LinkedQueues to put into the 26 array slots.
  2. Use a Scanner to read a series of 7-letter words, one per line, from  Enqueue them in a Master queue, represented by another LinkedQueue.
  3. For each character position p from 6 down to 0, do the following:
  4. At this point, the Master queue should contain all of the original words in alphabetical order.  Repeatedly dequeue them and write them to System.out, one word per line (that is, in the same format as the input file).

Programming notes: 

1.  You may assume that all of the strings consist of lower case English letters (a-z).  You can convert such a character to an index in the range 0-25 by subtracting 'a', as in

char c = s.charAt(i); // get the ith character from the string s
int index = c-'a';

2.  You may edit and compile your program using Eclipse.  To run your program, go to a terminal window, and enter the command as follows:

To read from the keyboard and write to the screen:

java RadixSort

To read from a file called filename and write to the screen:

java RadixSort < filename

To read from file1 and write to file2:

java RadixSort < file1 > file2

3.  The file contains two test input files, one short and one long, along with sorted versions of each one.  You can compare your output with the test output using the diff command in a terminal window:
diff file1 file2
If the files are identical, there will be no output.  If there are any discrepancies, diff will display the non-matching lines.  (diff is a unix command also found in macOS.  There is a comparable command caled fc on windows.)


The directory you submit through handin should include all of your Java files (including , and a README file.  Look through each of the files you've written or modified and make sure you've included your name at the top of all of them.  The README should include a statement of any known problems in your code.  If you adhered to the honor code in this assignment, add the following statement as a comment at the top of your README file:

I have adhered to the Honor Code in this assignment.

You now just need to electronically handin all your files using handin.  The assignment number is 4.

Don't forget to run lshand to verify that you've handed in something.