Implement the required algorithm using LinkedQueue/Stack Suppose you have a stac
ID: 3736571 • Letter: I
Question
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();
}
}
Explanation / Answer
Hi,
In order to return the elements in the Stack in original order, we must store the elements in the queue in reverse order after scanning them from stack. To reverse the elements of queue, first store them in the satck again temporarily, then again restore them in the queue back. Then search the required element in the queue and puch the element in the stack at the same time. This way we can push the elements in the stack in the original order.
Below is the main program. I have created a method void reverse() in the LinkedQueue class, but you can implement the logic directly in the main class also. Let me now if you have any more questions.
Place this method in the LinkedQueue.java class. The main program is below:
Ouput:
Stack: (18, 15, 5)
Queue: (18, 15, 5)
Queue after reversing: (5, 15, 18)
Enter element to search:
5
Number 5 found in Stack.
Stack Restored: (18, 15, 5)