C-6.24: Suppose you have a stack S containing n elements and a queue Q that is initially empty. Describe how you can use Q to scan S to see if it contains a certain element x, with the additional constraint that your algorithm must return the elements back to S in their original order. You may only use S, Q, and a constant number of other primitive variables.

Implement the required algorithm using provided LinkedQueue/Stack files.

LinkedQueue.java:

public class LinkedQueue implements Queue { /** The primary storage for elements of the queue */ private SinglyLinkedList list = new SinglyLinkedList<>(); // an empty list

/** Constructs an initially empty queue. */ public LinkedQueue() { } // new queue relies on the initially empty list

/** * Returns the number of elements in the queue. * @return number of elements in the queue */ @Override public int size() { return list.size(); }

/** * Tests whether the queue is empty. * @return true if the queue is empty, false otherwise */ @Override public boolean isEmpty() { return list.isEmpty(); }

/** * Inserts an element at the rear of the queue. * @param element the element to be inserted */ @Override public void enqueue(E element) { list.addLast(element); }

/** * Returns, but does not remove, the first element of the queue. * @return the first element of the queue (or null if empty) */ @Override public E first() { return list.first(); }

/** * Removes and returns the first element of the queue. * @return element removed (or null if empty) */ @Override public E dequeue() { return list.removeFirst(); }

/** Produces a string representation of the contents of the queue. * (from front to back). This exists for debugging purposes only. */ public String toString() { return list.toString(); } }

LinkedStack.java

public class LinkedStack implements Stack {

/** The primary storage for elements of the stack */ private SinglyLinkedList list = new SinglyLinkedList<>(); // an empty list

/** Constructs an initially empty stack. */ public LinkedStack() { } // new stack relies on the initially empty list

/** * Returns the number of elements in the stack. * @return number of elements in the stack */ @Override public int size() { return list.size(); }

/** * Tests whether the stack is empty. * @return true if the stack is empty, false otherwise */ @Override public boolean isEmpty() { return list.isEmpty(); }

/** * Inserts an element at the top of the stack. * @param element the element to be inserted */ @Override public void push(E element) { list.addFirst(element); }

/** * Returns, but does not remove, the element at the top of the stack. * @return top element in the stack (or null if empty) */ @Override public E top() { return list.first(); }

/** * Removes and returns the top element from the stack. * @return element removed (or null if empty) */ @Override public E pop() { return list.removeFirst(); }

/** Produces a string representation of the contents of the stack. * (ordered from top to bottom) * * This exists for debugging purposes only. * * @return textual representation of the stack */ public String toString() { return list.toString(); } }