/** * * Class to implement priority queue with arrays - System.exit version * * written by : R. G. Garside * * first written : 10/July/96 * last rewritten : 30/July/97 * */ import java.io.* ; import java.lancs.* ; public class PriorityQueue { private static final int MAX_BUFFER_SIZE = 100 ; private int queueLength ; private QueueElement[] buffer = new QueueElement[MAX_BUFFER_SIZE] ; /** * constructor */ public PriorityQueue() { queueLength = 0 ; // System.out.println("array implementation") ; } // end of constructor method /** * initialize - initializes a PriorityQueue to empty */ public void initialize() { queueLength = 0 ; } // end of method initialize /** * insert - insert in the priority queue a QueueElement "d". The * program halts if there is no room */ public void insert(QueueElement d) { // check that the queue is not full if (isFull()) { System.out.println("queue overflow") ; System.exit(1) ; } // search for the correct insertion position "i" int i = 0 ; while ((i < queueLength) && (buffer[i].getPriority() <= d.getPriority())) i++ ; // shuffle the data up (if necessary) for (int j = queueLength ; j > i ; j--) buffer[j] = buffer[j - 1] ; // insert the item // buffer[i] = d ; buffer[i] = new QueueElement(d.getPriority(), d.getData()) ; // adjust queue length queueLength++ ; } // end of method insert /** * first - return the QueueElement which is the first item in the * priority queue, without removing it; the program halts if * the queue is empty */ public QueueElement first() { if (isEmpty()) { System.out.println("queue underflow") ; System.exit(1) ; } // return buffer[0] ; return new QueueElement(buffer[0].getPriority(), buffer[0].getData()) ; } // end of method first /** * remove - remove the first item from the priority queue "q", * returning the priority "p" and data "d"; the program halts * if there are no items in the queue */ public QueueElement remove() { // check for empty queue if (isEmpty()) { System.out.println("queue underflow") ; System.exit(1) ; } // remember the first item QueueElement temp = buffer[0] ; // shuffle everything else up for (int i = 0 ; i < queueLength - 1 ; i++) buffer[i] = buffer[i + 1] ; // adjust the length queueLength-- ; // return the first item return temp ; } // end of method remove /** * length - returns the number of items in the priority queue "q" */ public int length() { return queueLength ; } // end of method length /** * isFull - returns TRUE if the PriorityQueue "q" is full, otherwise * returns FALSE. */ public boolean isFull() { return queueLength == MAX_BUFFER_SIZE ; } // end of method isFull /** * isEmpty - returns TRUE if the PriorityQueue "q" is empty, * otherwise returns FALSE. */ public boolean isEmpty() { return queueLength == 0 ; } // end of method isEmpty /** * main */ public static void main(String[] args) throws IOException { int priority ; String data ; String response ; boolean continueLoop = true ; PriorityQueue q = new PriorityQueue() ; QueueElement temp = new QueueElement() ; while (continueLoop) { displayMenu() ; response = BasicIo.readString().toLowerCase() ; if (response.length() == 0) response = "x" ; switch (response.charAt(0)) { case '1' : q.initialize() ; System.out.println("queue initialized") ; break ; case '2' : BasicIo.prompt("priority? ") ; priority = BasicIo.readInteger() ; BasicIo.prompt("string to insert? ") ; data = BasicIo.readString() ; temp.setPriority(priority) ; temp.setData(data) ; q.insert(temp) ; System.out.print("'" + data) ; System.out.print("' inserted in queue with priority ") ; System.out.println(priority) ; break ; case '3' : temp = q.first() ; System.out.print("'" + temp.getData()) ; System.out.print("' at head of queue with priority ") ; System.out.println(temp.getPriority()) ; break ; case '4' : temp = q.remove() ; System.out.print("'" + temp.getData()) ; System.out.print("' removed from queue with priority ") ; System.out.println(temp.getPriority()) ; break ; case '5' : System.out.print("there are " + q.length()) ; System.out.println(" items in the queue") ; break ; case '6' : System.out.print("the queue is ") ; if (!q.isFull()) System.out.print("not ") ; System.out.println("full") ; break ; case '7' : System.out.print("the queue is ") ; if (!q.isEmpty()) System.out.print("not ") ; System.out.println("empty") ; break ; case '8' : while (true) { BasicIo.prompt("priority (0 to terminate)? ") ; priority = BasicIo.readInteger() ; if (priority == 0) break ; BasicIo.prompt("string to insert? ") ; data = BasicIo.readString() ; temp.setPriority(priority) ; temp.setData(data) ; q.insert(temp) ; } break ; case '9' : while (!q.isEmpty()) { temp = q.remove() ; System.out.print("'" + temp.getData()) ; System.out.print("' with priority ") ; System.out.println(temp.getPriority()) ; } System.out.println("**end of queue**") ; break ; case 'a' : q.print() ; break ; case 'q' : continueLoop = false ; break ; default : System.out.println("invalid response") ; break ; } if (continueLoop) { BasicIo.prompt("press RETURN to continue ") ; response = BasicIo.readString() ; } } System.out.println("program terminating") ; } // end of method main /** * displayMenu */ private static void displayMenu() { System.out.println() ; System.out.println("Options to Exercise the Priority Queue") ; System.out.println() ; System.out.println("1 : initialise") ; System.out.println("2 : insert") ; System.out.println("3 : first") ; System.out.println("4 : remove") ; System.out.println("5 : length") ; System.out.println("6 : is full") ; System.out.println("7 : is empty") ; System.out.println() ; System.out.println("8 : multiple item insert") ; System.out.println("9 : scan and empty queue") ; System.out.println("a : print queue contents") ; System.out.println() ; System.out.println("q : quit") ; } // end of method displayMenu /** * print */ private void print() { System.out.println("the queue is (highest priority first)") ; for (int i = 0 ; i < queueLength ; i++) { System.out.print(i) ; System.out.print(": priority = " + buffer[i].getPriority()) ; System.out.print(": data = '" + buffer[i].getData()) ; System.out.println("'") ; } } // end of method print } // end of class PriorityQueue