Implement the required algorithm using LinkedQueue/Stack 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.

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(); } }

public interface Queue { /** * Returns the number of elements in the queue. * @return number of elements in the queue */ int size();

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

/** * Inserts an element at the rear of the queue. * @param e the element to be inserted */ void enqueue(E e);

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

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

linked stack

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(); } }

Queue

public interface Queue { /** * Returns the number of elements in the queue. * @return number of elements in the queue */ int size();

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

/** * Inserts an element at the rear of the queue. * @param e the element to be inserted */ void enqueue(E e);

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

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

Stack

public interface Stack {

/** * Returns the number of elements in the stack. * @return number of elements in the stack */ int size();

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

/** * Inserts an element at the top of the stack. * @param e the element to be inserted */ void push(E e);

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

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

SinglyLinkedList

public class SinglyLinkedList implements Cloneable { //---------------- nested Node class ---------------- /** * Node of a singly linked list, which stores a reference to its * element and to the subsequent node in the list (or null if this * is the last node). */ private static class Node {

/** The element stored at this node */ private E element; // reference to the element stored at this node

/** A reference to the subsequent node in the list */ private Node next; // reference to the subsequent node in the list

/** * Creates a node with the given element and next node. * * @param e the element to be stored * @param n reference to a node that should follow the new node */ public Node(E e, Node n) { element = e; next = n; }

// Accessor methods /** * Returns the element stored at the node. * @return the element stored at the node */ public E getElement() { return element; }

/** * Returns the node that follows this one (or null if no such node). * @return the following node */ public Node getNext() { return next; }

// Modifier methods /** * Sets the node's next reference to point to Node n. * @param n the node that should follow this one */ public void setNext(Node n) { next = n; } } //----------- end of nested Node class -----------

// instance variables of the SinglyLinkedList /** The head node of the list */ private Node head = null; // head node of the list (or null if empty)

/** The last node of the list */ private Node tail = null; // last node of the list (or null if empty)

/** Number of nodes in the list */ private int size = 0; // number of nodes in the list

/** Constructs an initially empty list. */ public SinglyLinkedList() { } // constructs an initially empty list

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

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

/** * Returns (but does not remove) the first element of the list * @return element at the front of the list (or null if empty) */ public E first() { // returns (but does not remove) the first element if (isEmpty()) return null; return head.getElement(); }

/** * Returns (but does not remove) the last element of the list. * @return element at the end of the list (or null if empty) */ public E last() { // returns (but does not remove) the last element if (isEmpty()) return null; return tail.getElement(); }

// update methods /** * Adds an element to the front of the list. * @param e the new element to add */ public void addFirst(E e) { // adds element e to the front of the list head = new Node<>(e, head); // create and link a new node if (size == 0) tail = head; // special case: new node becomes tail also size++; }

/** * Adds an element to the end of the list. * @param e the new element to add */ public void addLast(E e) { // adds element e to the end of the list Node newest = new Node<>(e, null); // node will eventually be the tail if (isEmpty()) head = newest; // special case: previously empty list else tail.setNext(newest); // new node after existing tail tail = newest; // new node becomes the tail size++; }

/** * Removes and returns the first element of the list. * @return the removed element (or null if empty) */ public E removeFirst() { // removes and returns the first element if (isEmpty()) return null; // nothing to remove E answer = head.getElement(); head = head.getNext(); // will become null if list had only one node size--; if (size == 0) tail = null; // special case as list is now empty return answer; }

@SuppressWarnings({"unchecked"}) public boolean equals(Object o) { if (o == null) return false; if (getClass() != o.getClass()) return false; SinglyLinkedList other = (SinglyLinkedList) o; // use nonparameterized type if (size != other.size) return false; Node walkA = head; // traverse the primary list Node walkB = other.head; // traverse the secondary list while (walkA != null) { if (!walkA.getElement().equals(walkB.getElement())) return false; //mismatch walkA = walkA.getNext(); walkB = walkB.getNext(); } return true; // if we reach this, everything matched successfully }

@SuppressWarnings({"unchecked"}) public SinglyLinkedList clone() throws CloneNotSupportedException { // always use inherited Object.clone() to create the initial copy SinglyLinkedList other = (SinglyLinkedList) super.clone(); // safe cast if (size > 0) { // we need independent chain of nodes other.head = new Node<>(head.getElement(), null); Node walk = head.getNext(); // walk through remainder of original list Node otherTail = other.head; // remember most recently created node while (walk != null) { // make a new node storing same element Node newest = new Node<>(walk.getElement(), null); otherTail.setNext(newest); // link previous node to this one otherTail = newest; walk = walk.getNext(); } } return other; }

public int hashCode() { int h = 0; for (Node walk=head; walk != null; walk = walk.getNext()) { h ^= walk.getElement().hashCode(); // bitwise exclusive-or with element's code h = (h << 5) | (h >>> 27); // 5-bit cyclic shift of composite code } return h; }

/** * Produces a string representation of the contents of the list. * This exists for debugging purposes only. */ public String toString() { StringBuilder sb = new StringBuilder("("); Node walk = head; while (walk != null) { sb.append(walk.getElement()); if (walk != tail) sb.append(", "); walk = walk.getNext(); } sb.append(")"); return sb.toString(); } }