class EmptyQueue E extends Exception {} abstract class Queue { abstract void enqueue (E elem); abstract void dequeue () throws EmptyQueueE; abstract E getFront () throws EmptyQueueE; } class SlowQueue extends Queue { // Our queue is represented by an object of our Stack class in Stack.java // So, for clarification, whenever the method docs ask to "modify our queue", // we are actually modifying this object. // Read Stack.java please:) private Stack stack; * This initializes our private var "stack" to be a new Emptys (see -Stack.java-) SlowQueue () { stack = new Emptys>(); } * Although the method itself does not return anything, enqueue modifies our queue by adding given element to the * end. Hint: look in -Stack.java- * * @param elem a generic element to be added to the queue */ void enqueue (E elem) { // TODO } * This method should remove the first element of our queue. Hint: look in -Stack.java-. * * athrows ????? (throws what and why) */ void dequeuel) throws EmptyQueue { // TODO } * getFront returns an element of **generic type**. * This method returns the first element of our queue by using -Stack.java-'s getFront) * @return the removed first element of out queue, E * @throws ????? (throws what and why) E getFront() throws EmptyQueue { try { return stack.getTop(); } catch (EmptyStacke e) { throw new EmptyQueueE(); } } > class AmortizedQueue extends Queue { private Stack front, back; // enqueue in front; dequeue from back * This method initializes our private vars "front" and "back" to be * a new Emptys (see - Stack.java-) */ AmortizedQueue () { front = new Emptys(); back = new Emptys(); } * Although the method itself does not return anything, enqueue modifies our queue by calling on * -Stack.java-'s push() on our front stack. * @param elem a generic element to be added to the queue. We do this on front because we are enqueueing */ void enqueue (E elem) { front = front.push(elem); } * This method should remove the first element of our queue. What we mean by "first" here is based off of the * queue's FIFO (first-in-first-out) structure. * That is: we cannot simply just remove from our enqueued "front". Why? * In order to complete this method, transfer everything from our front to our back whenever back DOES NOT * contain any elements. Then, dequeue (remove). * * Think about what would happen if we moved everything from front to back on every dequeue call. Would this process * still be considered amortized? Would this process still be correct? * Use methods in -Stack.java- to help you deal with front and back. * @throws ????? (throws what and why) void dequeue() throws EmptyQueue { // TODO } * Returns the first element in our queue. Similar to dequeue with maintaining the * 2 stacks; the only thing that changes here is that we are not removing the top, but instead returning the element * @return the removed first element of out queue, E * @throws ????? (throws what and why) */ E getFront() throws EmptyQueue { // TODO return null; } public String toString() { return; } } class NonEmptyS extends Stack { private final e top: private final Stack rest; private final int size; NonEmptys (E top, Stack rest) { this. top = top; this.rest = rest; this.size = rest.size() + 1; } boolean isEmpty() { return false; } int size() { return size; } Stack push(E elem) { return new NonEmptyS>(elem, this); } Stack pop() { return rest; } E getTop() { return top; } Stack add Last(E elem) { return new NonEmptys (top, rest.addLast (elem)); } E getLast() throws EmptyStacke { if (rest.isEmpty()) { return top: } else { return rest.getLast(); } } public String toString() { return; } } class NonEmptyS extends Stack { private final e top: private final Stack rest; private final int size; NonEmptys (E top, Stack rest) { this. top = top; this.rest = rest; this.size = rest.size() + 1; } boolean isEmpty() { return false; } int size() { return size; } Stack push(E elem) { return new NonEmptyS>(elem, this); } Stack pop() { return rest; } E getTop() { return top; } Stack add Last(E elem) { return new NonEmptys (top, rest.addLast (elem)); } E getLast() throws EmptyStacke { if (rest.isEmpty()) { return top: } else { return rest.getLast(); } } public String toString() { return String.format("&s; %s", top, rest.toString(); } } class EmptyQueue E extends Exception {} abstract class Queue { abstract void enqueue (E elem); abstract void dequeue () throws EmptyQueueE; abstract E getFront () throws EmptyQueueE; } class SlowQueue extends Queue { // Our queue is represented by an object of our Stack class in Stack.java // So, for clarification, whenever the method docs ask to "modify our queue", // we are actually modifying this object. // Read Stack.java please:) private Stack stack; * This initializes our private var "stack" to be a new Emptys (see -Stack.java-) SlowQueue () { stack = new Emptys>(); } * Although the method itself does not return anything, enqueue modifies our queue by adding given element to the * end. Hint: look in -Stack.java- * * @param elem a generic element to be added to the queue */ void enqueue (E elem) { // TODO } * This method should remove the first element of our queue. Hint: look in -Stack.java-. * * athrows ????? (throws what and why) */ void dequeuel) throws EmptyQueue { // TODO } * getFront returns an element of **generic type**. * This method returns the first element of our queue by using -Stack.java-'s getFront) * @return the removed first element of out queue, E * @throws ????? (throws what and why) E getFront() throws EmptyQueue { try { return stack.getTop(); } catch (EmptyStacke e) { throw new EmptyQueueE(); } } > class AmortizedQueue extends Queue { private Stack front, back; // enqueue in front; dequeue from back * This method initializes our private vars "front" and "back" to be * a new Emptys (see - Stack.java-) */ AmortizedQueue () { front = new Emptys(); back = new Emptys(); } * Although the method itself does not return anything, enqueue modifies our queue by calling on * -Stack.java-'s push() on our front stack. * @param elem a generic element to be added to the queue. We do this on front because we are enqueueing */ void enqueue (E elem) { front = front.push(elem); } * This method should remove the first element of our queue. What we mean by "first" here is based off of the * queue's FIFO (first-in-first-out) structure. * That is: we cannot simply just remove from our enqueued "front". Why? * In order to complete this method, transfer everything from our front to our back whenever back DOES NOT * contain any elements. Then, dequeue (remove). * * Think about what would happen if we moved everything from front to back on every dequeue call. Would this process * still be considered amortized? Would this process still be correct? * Use methods in -Stack.java- to help you deal with front and back. * @throws ????? (throws what and why) void dequeue() throws EmptyQueue { // TODO } * Returns the first element in our queue. Similar to dequeue with maintaining the * 2 stacks; the only thing that changes here is that we are not removing the top, but instead returning the element * @return the removed first element of out queue, E * @throws ????? (throws what and why) */ E getFront() throws EmptyQueue { // TODO return null; } public String toString() { return; } } class NonEmptyS extends Stack { private final e top: private final Stack rest; private final int size; NonEmptys (E top, Stack rest) { this. top = top; this.rest = rest; this.size = rest.size() + 1; } boolean isEmpty() { return false; } int size() { return size; } Stack push(E elem) { return new NonEmptyS>(elem, this); } Stack pop() { return rest; } E getTop() { return top; } Stack add Last(E elem) { return new NonEmptys (top, rest.addLast (elem)); } E getLast() throws EmptyStacke { if (rest.isEmpty()) { return top: } else { return rest.getLast(); } } public String toString() { return; } } class NonEmptyS extends Stack { private final e top: private final Stack rest; private final int size; NonEmptys (E top, Stack rest) { this. top = top; this.rest = rest; this.size = rest.size() + 1; } boolean isEmpty() { return false; } int size() { return size; } Stack push(E elem) { return new NonEmptyS>(elem, this); } Stack pop() { return rest; } E getTop() { return top; } Stack add Last(E elem) { return new NonEmptys (top, rest.addLast (elem)); } E getLast() throws EmptyStacke { if (rest.isEmpty()) { return top: } else { return rest.getLast(); } } public String toString() { return String.format("&s; %s", top, rest.toString(); } }