MUST USE THIS QUEUE CLASS: */

package algs13;

import stdlib.*;

import java.util.Iterator;

import java.util.NoSuchElementException;

/* ***********************************************************************

* Compilation: javac Queue.java

* Execution: java Queue < input.txt

* Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt

*

* A generic queue, implemented using a linked list.

*

* % java Queue < tobe.txt

* to be or not to be (2 left on queue)

*

*************************************************************************/

/**

* The Queue class represents a first-in-first-out (FIFO)

* queue of generic items.

* It supports the usual enqueue and dequeue

* operations, along with methods for peeking at the top item,

* testing if the queue is empty, and iterating through

* the items in FIFO order.

*

* All queue operations except iteration are constant time.

*

* For additional documentation, see Section 1.3 of

* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

*/

public class Queue implements Iterable {

private int N; // number of elements on queue

private Node first; // beginning of queue

private Node last; // end of queue

// helper linked list class

private static class Node {

public Node() { }

public T item;

public Node next;

}

/**

* Create an empty queue.

*/

public Queue() {

first = null;

last = null;

N = 0;

}

/**

* Is the queue empty?

*/

public boolean isEmpty() {

return first == null;

}

/**

* Return the number of items in the queue.

*/

public int size() {

return N;

}

/**

* Return the item least recently added to the queue.

* @throws java.util.NoSuchElementException if queue is empty.

*/

public T peek() {

if (isEmpty()) throw new NoSuchElementException("Queue underflow");

return first.item;

}

/**

* Add the item to the queue.

*/

public void enqueue(T item) {

Node oldlast = last;

last = new Node<>();

last.item = item;

last.next = null;

if (isEmpty()) first = last;

else oldlast.next = last;

N++;

}

/**

* Remove and return the item on the queue least recently added.

* @throws java.util.NoSuchElementException if queue is empty.

*/

public T dequeue() {

if (isEmpty()) throw new NoSuchElementException("Queue underflow");

T item = first.item;

first = first.next;

N--;

if (isEmpty()) last = null;

return item;

}

/**

* Return string representation.

*/

public String toString() {

StringBuilder s = new StringBuilder();

for (T item : this)

s.append(item + " ");

return s.toString();

}

// check internal invariants

private static boolean check(Queue that) {

int N = that.N;

Queue.Node first = that.first;

Queue.Node last = that.last;

if (N == 0) {

if (first != null) return false;

if (last != null) return false;

}

else if (N == 1) {

if (first == null || last == null) return false;

if (first != last) return false;

if (first.next != null) return false;

}

else {

if (first == last) return false;

if (first.next == null) return false;

if (last.next != null) return false;

// check internal consistency of instance variable N

int numberOfNodes = 0;

for (Queue.Node x = first; x != null; x = x.next) {

numberOfNodes++;

}

if (numberOfNodes != N) return false;

// check internal consistency of instance variable last

Queue.Node lastNode = first;

while (lastNode.next != null) {

lastNode = lastNode.next;

}

if (last != lastNode) return false;

}

return true;

}

/**

* Return an iterator that iterates over the items on the queue in FIFO order.

*/

public Iterator iterator() {

return new ListIterator();

}

// an iterator, doesn't implement remove() since it's optional

private class ListIterator implements Iterator {

private Node current = first;

public boolean hasNext() { return current != null; }

public void remove() { throw new UnsupportedOperationException(); }

public T next() {

if (!hasNext()) throw new NoSuchElementException();

T item = current.item;

current = current.next;

return item;

}

}

public void toGraphviz(String filename) {

GraphvizBuilder gb = new GraphvizBuilder ();

toGraphviz (gb, null, first);

gb.toFile (filename, "rankdir=\"LR\"");

}

private void toGraphviz (GraphvizBuilder gb, Node prev, Node n) {

if (n == null) { gb.addNullEdge (prev); return; }

gb.addLabeledNode (n, n.item.toString ());

if (prev != null) gb.addEdge (prev, n);

toGraphviz (gb, n, n.next);

}

/**

* A test client.

*/

public static void main(String[] args) {

StdIn.fromString ("to be or not to - be - - that - - - is");

Queue q = new Queue<>();

int count = 0;

q.toGraphviz ("queue" + count + ".png"); count++;

while (!StdIn.isEmpty()) {

String item = StdIn.readString();

if (!item.equals("-")) q.enqueue(item);

else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");

q.toGraphviz ("queue" + count + ".png"); count++;

}

StdOut.println("(" + q.size() + " left on queue)");

}

}

*/

* mergeQueues

* precondition: input queues q1, q2 may be empty

* postconditions:

* return a new queue containing merged contents of q1,q2 using

* an every-other-one policy - starting with q1

* if queues are not the same length, the 'tail' of the longer one ends

* up getting appended to the result - see examples below

* original queues are empty

* you may use: basic java arrays, Stack<>, Queue<> from algs13

* you may NOT use any other Java classes, algorithms without permission

* your solution must be all client code: you may not alter the original Stack, Queue classes

* In the examples below, the left-most values are at the front of the queues

* Examples:

* q1: abcd , q2: wxyz mergeQueues(q1,q2) --> awbxcydz

* q1: abc , q2: xy mergeQueues(q1,q2) --> axbyc

* q1: ab , q2: xyz mergeQueues(q1,q2) --> axbyz

* q1: abc , q2: mergeQueues(q1,q2) --> abc

* q1: , q2: mergeQueues(q1,q2) -->

* merge

*/

public static Queue mergeQueues(Queue q1,Queue q2) {