question archive In this problem you will implement a Banker's queue, as discussed in class, which uses two completely separate stacks, S1 and S2
In this problem you will implement a Banker's queue, as discussed in class, which uses two completely separate stacks, S1 and S2
Subject:Computer SciencePrice: Bought3
In this problem you will implement a Banker's queue, as discussed in class, which uses two completely separate stacks, S1 and S2. Enqueue operations happen by pushing the data on to S1.
Dequeue operations are completed with a pop from S2.
Write a class TwoStackQueue that provides the Queue ADT (by implementing the Queue interface) using two stacks. Provide all methods specified in the interface. Your class should not use any additional memory to store the data in the queue except for the two stacks.
For your stacks, use the provided ArrayStack class.
Your TwoStackQueue should raise a java.util.NoSuchElementException when trying to dequeue from an empty queue.
You may use the TestTwoStackQueue class to test your code.
import java.util.NoSuchElementException;
public class TwoStackQueue<T> implements Queue<T> {
private Stack<T> s1;
private Stack<T> s2;
public TwoStackQueue() {
// write a constructor
}
public void enqueue(T x) {
return; // replace this
}
public T dequeue() throws NoSuchElementException {
return null; // replace this
}
public boolean isEmpty() {
return true; // replace this
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.NoSuchElementException;
public class TestTwoStackQueue {
public static void main(String[] args) {
Queue<Integer> q = new TwoStackQueue<Integer>();
// Test isEmpty
boolean isEmptyTest = true;
if (! q.isEmpty()) {
System.err.println((char)27 + "[31misEmpty failed on empty queue."+(char)27+"[0m");
isEmptyTest = false;
}
q.enqueue(1);
if (q.isEmpty()) {
System.err.println((char)27 + "[31misEmpty failed on non-empty queue."+(char)27+"[0m");
isEmptyTest = false;
}
Integer test = q.dequeue();
if (! q.isEmpty()) {
System.err.println((char)27 + "[31misEmpty failed after dequeuing one element."+(char)27+"[0m");
isEmptyTest = false;
}
if (isEmptyTest)
System.err.println((char)27 + "[32misEmpty OK."+(char)27+"[0m");
try {
q.dequeue();
} catch (NoSuchElementException e) {
System.err.println((char)27 + "[32mDequeue from empty queue results in NoSuchElementException. Ok."+(char)27+"[0m");
}
List<Integer> testList = new ArrayList<>();
for (int i = 0; i < 10; i++) {
testList.add(i);
q.enqueue(i);
}
boolean fifoTest = true;
for (int i=0; i < testList.size(); i++)
if (! testList.get(i).equals(q.dequeue()))
fifoTest = false;
if (fifoTest)
System.err.println((char)27 + "[32mFIFO order Ok."+(char)27+"[0m");
else
System.err.println((char)27 + "[31mDequeued elements in the wrong order (not FIFO)."+(char)27+"[0m");
}
}
public class ArrayStack<T> implements Stack<T> {
private static final int DEFAULT_SIZE = 10;
int topOfStack;
private T[] theArray;
@SuppressWarnings("unchecked")
public ArrayStack(){
theArray = (T[]) new Object[DEFAULT_SIZE];
topOfStack = -1;
}
@SuppressWarnings("unchecked")
private void ensureCapacity(int size) {
if (size > theArray.length) {
T[] old = theArray;
theArray = (T[]) new Object[old.length * 2 + 1];
for (int i = 0; i < old.length; i++)
theArray[i] = old[i];
}
}
public void push(T x) {
topOfStack++;
ensureCapacity(topOfStack + 1);
theArray[topOfStack] = x;
}
public T pop() {
if (topOfStack == -1)
throw new IndexOutOfBoundsException("Pop from empty stack!");
T result = theArray[topOfStack];
theArray[topOfStack] = null; // allow the garbage collector to recycle the pop-ed object
topOfStack--;
return result;
}
public T top() {
return theArray[topOfStack];
}
public int size(){
return topOfStack + 1;
}
public boolean isEmpty() {
return topOfStack == -1;
}
public String toString() {
StringBuilder sb = new StringBuilder( "[ " );
for(int i=0;i<=topOfStack;i++)
sb.append(theArray[i] + " ");
sb.append("]");
return new String( sb );
}
/**
* Test the stack.
*/
public static void main(String[] args) {
Stack<Integer> s = new ArrayStack<>();
s.push(5);
s.push(42);
System.out.println(s);
s.push(23);
System.out.println(s);
System.out.println("Top: " + s.top());
System.out.println("Pop: " + s.pop());
System.out.println(s);
}
}
interface Queue<T> {
/**
* Insert a new item at the back of the queue
*/
public void enqueue(T x);
/**
* Remove and return the next item from the
* front of the queue. Should throw a
* NoSuchElementException if dequeuing from
* an empty queue
*/
public T dequeue();
/**
* Return true if the queue is empty and
* false otherwise
*/
public boolean isEmpty();
}
interface Stack<T> {
/* Push a new item x on top of the stack */
public void push(T x);
/* Remove and return the top item of the stack */
public T pop();
/* Return the top item of the stack without removing it */
public T top();
/* Return true if the stack is empty and false otherwise */
public boolean isEmpty();
/* Return the size of the stack */
public int size();
}
