The Queue ADT (Chapter 4) Continued

• Based on the Lab 4 assignment problem, implement an additional queue interface, QueueInterfacePeek. This interface will include new methods that have the ability to peek into both the front and rear of the queue: peekFront() and peekRear(). (See p.249-250 for reference.) Modify your test driver (demo program) to also include several test cases based on these (new) additional methods with respect to queueing operations. Note: your code should try and implement two interfaces: QueueInterface and QueueInterfacePeek.
• Include a (brief) analysis of your algorithm in terms of how peeking works.

LAB 4

TDArrayBoundedQueue.java import java.util.*; public class ITDArrayBoundedQueue { public static void main(String[] args) { QueueInterface test = new ArrayBoundedQueue(); Scanner scan = new Scanner(System.in); String skip; // skip end of line after reading an integer boolean keepGoing; // flag for "choose operation" loop int constructor; // indicates user's choice of constructor int operation; // indicates user's choice of operation String enqueueString = "", dequeueString = ""; // used by operations // Handle test name System.out.println("What is the name of this test?"); String testName = scan.nextLine(); System.out.println(" This is test " + testName + " "); // Handle constructor System.out.println("Choose a constructor:"); System.out.println("1: ArrayBoundedQueue( )"); System.out.println("2: ArrayBoundedQueue(int maxSize)"); if (scan.hasNextInt()) constructor = scan.nextInt(); else { System.out.println("Error: you must enter an integer."); System.out.println("Terminating test."); return; } skip = scan.nextLine(); switch (constructor) { case 1: test = new ArrayBoundedQueue(); break; case 2: System.out.println("Enter a maximum size:"); int maxSize; if (scan.hasNextInt()) maxSize = scan.nextInt(); else { System.out.println("Error: you must enter an integer."); System.out.println("Terminating test."); return; } skip = scan.nextLine(); test = new ArrayBoundedQueue(maxSize); break; default: System.out.println("Error in constructor choice. Terminating test."); return; } // Handle test cases keepGoing = true; while (keepGoing) { System.out.println(" Choose an operation:"); System.out.println("1: enqueue(element)"); System.out.println("2: String dequeue()"); System.out.println("3: boolean isFull()"); System.out.println("4: boolean isEmpty()"); System.out.println("5: int size()"); System.out.println("6: stop Testing"); if (scan.hasNextInt()) operation = scan.nextInt(); else { System.out.println("Error: you must enter an integer."); System.out.println("Terminating test."); return; } skip = scan.nextLine(); switch (operation) { case 1: // enqueue System.out.println("Enter string to enqueue:"); enqueueString = scan.nextLine(); System.out.println("enqueue(\"" + enqueueString + "\")"); try { test.enqueue(enqueueString); } catch (QueueOverflowException QOFException) { System.out.println("Overflow Exception: " + QOFException.getMessage()); } break; case 2: // dequeue System.out.println("dequeue()"); try { dequeueString = test.dequeue(); } catch (QueueUnderflowException QUFException) { System.out.println("Underflow Exception: " + QUFException.getMessage()); break; } System.out.println("Result: " + dequeueString + " was returned."); break; case 3: // isFull System.out.println("isFull()"); System.out.println("Result: " + test.isFull()); break; case 4: // isEmpty System.out.println("isEmpty()"); System.out.println("Result: " + test.isEmpty()); break; case 5: // size System.out.println("size()"); System.out.println("Result: " + test.size()); break; case 6: // stop testing keepGoing = false; break; default: System.out.println("Error in operation choice. Terminating test."); return; } } System.out.println("End of Interactive Test Driver"); } } ================================================================================================ QueueInterface.java public interface QueueInterface { void enqueue(T element) throws QueueOverflowException; // Throws QueueOverflowException if this queue is full; // otherwise, adds element to the rear of this queue. T dequeue() throws QueueUnderflowException; // Throws QueueUnderflowException if this queue is empty; // otherwise, removes front element from this queue and returns it. boolean isFull(); // Returns true if this queue is full; otherwise, returns false. boolean isEmpty(); // Returns true if this queue is empty; otherwise, returns false. int size(); // Returns the number of elements in this queue. } ============================================================================================== QueueOverflowException.java public class QueueOverflowException extends RuntimeException { public QueueOverflowException() { super(); } public QueueOverflowException(String message) { super(message); } } ============================================================================================================ QueueUnderflowException.java public class QueueUnderflowException extends RuntimeException { public QueueUnderflowException() { super(); } public QueueUnderflowException(String message) { super(message); } } ============================================================================================================ ArrayBoundedQueue.java public class ArrayBoundedQueue implements QueueInterface { protected final int DEFCAP = 100; // default capacity protected T[] elements; // array that holds queue elements protected int numElements = 0; // number of elements in this queue protected int front = 0; // index of front of queue protected int rear; // index of rear of queue public ArrayBoundedQueue() { elements = (T[]) new Object[DEFCAP]; rear = DEFCAP - 1; } public ArrayBoundedQueue(int maxSize) { elements = (T[]) new Object[maxSize]; rear = maxSize - 1; } public void enqueue(T element) // Throws QueueOverflowException if this queue is full; // otherwise, adds element to the rear of this queue. { if (isFull()) throw new QueueOverflowException("Enqueue attempted on a full queue."); else { rear = (rear + 1) % elements.length; elements[rear] = element; numElements = numElements + 1; } } public T dequeue() // Throws QueueUnderflowException if this queue is empty; // otherwise, removes front element from this queue and returns it. { if (isEmpty()) throw new QueueUnderflowException("Dequeue attempted on empty queue."); else { T toReturn = elements[front]; elements[front] = null; front = (front + 1) % elements.length; numElements = numElements - 1; return toReturn; } } public boolean isEmpty() // Returns true if this queue is empty; otherwise, returns false. { return (numElements == 0); } public boolean isFull() // Returns true if this queue is full; otherwise, returns false. { return (numElements == elements.length); } public int size() // Returns the number of elements in this queue. { return numElements; } }

page 249 to 250

package ch04. queues: public interface GlassQueue Interface extends Queue Interface { public T peekFront(): // If the queue is empty. returns null. 1/ Otherwise, returns the element at the front of this queue. public T peekRear(): // If the queue is empty. returns null // Otherwise, returns the element at the rear of this queue. ] 1/ elements without removing them. package ch04.queues: public class LinkedGlassQueue extends LinkedQueue implements GlassQueue Interface { public LinkedGlassQueue () { super(); 1 public T peekFront() // If the queue is empty. returns null. // Otherwise returns the element at the front of this queue. [ if (isEmpty()) return null; else return front.getInfo(): } public T peekRear() // If the queue is empty, returns null. // Otherwise returns the element at the rear of this queue. [ if (isEmpty()) return null; else return rear.getInfo(): } package ch04. queues: public interface GlassQueue Interface extends Queue Interface { public T peekFront(): // If the queue is empty. returns null. 1/ Otherwise, returns the element at the front of this queue. public T peekRear(): // If the queue is empty. returns null // Otherwise, returns the element at the rear of this queue. ] 1/ elements without removing them. package ch04.queues: public class LinkedGlassQueue extends LinkedQueue implements GlassQueue Interface { public LinkedGlassQueue () { super(); 1 public T peekFront() // If the queue is empty. returns null. // Otherwise returns the element at the front of this queue. [ if (isEmpty()) return null; else return front.getInfo(): } public T peekRear() // If the queue is empty, returns null. // Otherwise returns the element at the rear of this queue. [ if (isEmpty()) return null; else return rear.getInfo(): }