/** * * Class to implement priority queue with arrays - exception-throwing 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) throws QueueFullException        {        // check that the queue is not full        if (isFull())	    throw new QueueFullException("'insert' in full queue") ;	        // 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] = 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() throws QueueEmptyException        {        if (isEmpty())	    throw new QueueEmptyException("'first' on empty queue") ;        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() throws QueueEmptyException        {        // check for empty queue        if (isEmpty())	    throw new QueueEmptyException("'remove' from empty queue") ;        // 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() ;	    try {                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 ;                    } // end of switch		} // end of try block	    catch (QueueFullException e)		{		System.out.println("no more room in the queue") ;		}		    catch (QueueEmptyException e)		{		System.out.println("no elements in the queue") ;		}	            if (continueLoop)	        {      	        BasicIo.prompt("press RETURN to continue ") ;                response = BasicIo.readString() ;                }            } // end of loop        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