Lab 4 - Linked Queues and the Radix Sort
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 lab4.zip .
Due: 11:59 pm, Sunday, March 10
The purpose of the lab is to:
- learn how to implement a queue
- learn how to implement a linked data structure
- learn how to implement the radix sort
Part one: Writing the LinkedQueue class
Write a class called LinkedQueue that implements the
QueueADT interface found in the lab4.zip file. Your
implementation should be similar to the LinkedStack class
in the examples folder. You need to do the following in
- The header line of the class must say implements
- Define an inner class called QNode.
- Define two private instance variables of type QNode called front
and rear, which are references to the front and rear
nodes in the queue.
- Write a no-argument constructor which instantiates an empty
LinkedQueue. In an empty LinkedQueue, both front and rear
- Write implementations of the methods enqueue, dequeue,
isEmpty, and clear. All of these methods should be O(1).
- 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
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
Write an application called RadixSort.java which does the
following: (This is the main method in RadixSort.java.)
- 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.
- Use a Scanner to read a series of 7-letter words, one per
line, from System.in. Enqueue them in a Master queue,
represented by another LinkedQueue.
- For each character position p from 6 down to 0, do the
- Clear each of the 26 bins.
- Dequeue each name from the Master queue and enqueue it on a
bin according to the pth letter of the word. (See note 1
- Combine all the bins (from A to Z) into a single
LinkedQueue, by repeatedly calling append. The combined queue becomes the
new Master queue.
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).
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
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
To read from the keyboard and write
to the screen:
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 lab4.zip 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:
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
The directory you submit through handin should include all of
your Java files (including QueueADT.java) , 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