There are three files listed here:
Here is the file SortPQ.java:
//***************************************************************************
//********************** class SortPQ ***************************************
//
// This is the main class for Lab 2. It uses the priority queue
// sorting algorithm to sort an array of strings. The number of strings
// and the strings themselves are obtained interactively from the user.
//
//***************************************************************************
import java.io.*;
class SortPQ {
// --------------------------------------------------------------------------
// ------------------------ method main -------------------------------------
public static void main (String[] argv) throws IOException {
String[] A = getStrings(); // will hold the strings to be sorted
int n = A.length;
PriorityQueue pq = new PriorityQueue();
for (int i = 0; i < n; i++) pq.insert(A[i]);
for (int i = n-1; i >= 0; i--) A[i] = pq.remove();
for (int i = 0; i < n; i++) System.out.println(A[i]);
}
// --------------------------------------------------------------------------
// ------------------------ method getStrings -------------------------------
public static String[] getStrings() throws IOException {
BufferedReader stdin = new BufferedReader (
new InputStreamReader ( System.in ) );
System.out.print("Enter number of strings: ");
int n = Integer.parseInt(stdin.readLine());
String[] A = new String[n]; // allocate the array of strings
for (int i = 0; i < n; i++) {
System.out.print("Enter string " + i + ": ");
A[i] = stdin.readLine();
}
return A;
}
}
Here is the file PriorityQueue.java, using an unsorted linked list:
//***************************************************************************
//********************** class StringNode ***********************************
//
// Combines a string with a link, for use in a linked list of strings.
//
//***************************************************************************
class StringNode {
String key;
StringNode link;
StringNode(String s) { // constructor
key = s;
}
}
//***************************************************************************
//********************** class PriorityQueue ********************************
//
// Implements a priority queue (of strings) using an unsorted linked list.
//
//***************************************************************************
class PriorityQueue {
private StringNode first = null;
// --------------------------------------------------------------------------
// ----------------- method PriorityQueue (constructor) ---------------------
//
// Just sets first pointer to null.
//
// --------------------------------------------------------------------------
PriorityQueue() { // constructor
first = null;
}
// --------------------------------------------------------------------------
// ------------------------- method insert ----------------------------------
//
// Makes a new node for the input argument and inserts it at the beginning
// of the list.
//
// --------------------------------------------------------------------------
public void insert(String s) { // don't need to check for overflow
StringNode node = new StringNode(s); // make a node containing data s
node.link = first; // insert at beginning of list
first = node;
}
// --------------------------------------------------------------------------
// ------------------------- method remove ----------------------------------
//
// Searches through the list for the (alphabetically) largest key
// (string), removes that node and returns the key.
//
// ASSUMPTION: never called when the list is empty.
//
// --------------------------------------------------------------------------
public String remove() { // not checking for empty list...
if (first.link == null) { // one-node list
String max = first.key;
first = null;
return max;
} // at least two nodes in the list
String max = first.key;
StringNode maxLoc = first;
StringNode maxPrev = null; // so node with max key can be removed
StringNode cur = first;
StringNode prev = null;
while (cur != null) { // scan for max key
if (max.compareTo(cur.key) < 0) { // found a key larger than cur
max = cur.key; // remember the key
maxLoc = cur; // remember its node
maxPrev = prev; // remember previous node
}
prev = cur; // continue the scan
cur = cur.link;
}
if (maxPrev == null) // node w/ max key is first node
first = first.link; // remove first node
else
maxPrev.link = maxLoc.link; // splice out node with max key
return max;
}
}
Here is the file PriorityQueue.java, using a sorted array:
//***************************************************************************
//********************** class PriorityQueue ********************************
//
// Implements a priority queue (of strings) using a sorted array.
//
//***************************************************************************
class PriorityQueue {
private String[] data; // holds the keys
private int next; // holds the index of the next free location
// in the array data
// --------------------------------------------------------------------------
// ----------------- method PriorityQueue (constructor) ---------------------
//
// Allocates a big array to hold the data and initializes next counter
// to indicate that it is currently empty.
//
// --------------------------------------------------------------------------
PriorityQueue() { // constructor
data = new String[100];
next = 0;
}
// --------------------------------------------------------------------------
// ------------------------- method insert ----------------------------------
//
// Scanning backwards from index next, shift down the array elements
// until finding the correct location for the argument key.
//
// ASSUMPTION: will not be called if the array is full (next = 100).
//
// --------------------------------------------------------------------------
public void insert(String s) { // not checking for overflow...
int i = next-1;
while ((i >= 0) && (s.compareTo(data[i]) < 0)) {
data[i+1] = data[i]; // shifting down
i--;
}
data[i+1] = s; // insert new data
next++;
}
// --------------------------------------------------------------------------
// ------------------------- method remove ----------------------------------
//
// Returns the last item in the array; correct thing to do since array
// is sorted. next is decremented to indicate that number of items
// has decreased.
//
// ASSUMPTION: will not be called if array is empty (next = 0).
//
// --------------------------------------------------------------------------
public String remove() {
next--;
return data[next];
}
}