Build a queue out of two completely separate stacks, S1 and S2. Enqueue operations happen by pushing the data on to stack 1. Dequeue operations are completed with a pop from stack 2.

Obviously you will have to find some way to get the input stack information over to the output stack. Your job is to figure out how and when to do that, using only push and pop operations.

Write a class TwoStackQueue that provides the Queue ADT (as specified in MyQueue interface provided in the file MyQueue.java) using two stacks. Your class should explicitly implement the interface provided above. Since the interface is generic, your class should be as well. 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 MyStack class that you implemented in the first problem.

Write a tester class with a main method to demonstrate that your TwoStackQueue works correctly (by enqueueing a number of objects and then dequeueing and printing them in the correct order). Call your tester class Problem2.java. You can find a sample tester class in the file TwoStackQueueTester. It is similar to the one that we will use to grade your submission. Your tester should try different examples than the ones from this sample.

In a file called Problem2.txt, discuss the big-O running time of the enqueue and dequeue operation for your queue implementation. (Hint: one of these operations should always be O(1) the other can vary a bit, but shouldnt always be O(N)).

/** This is the interface that your TwoStackQueue class must * implement. */ public interface MyQueue {

// Performs the enqueue operation public void enqueue(AnyType x);

// Performs the dequeue operation. For this assignment, if you // attempt to dequeue an already empty queue, you should return // null public AnyType dequeue();

// Checks if the Queue is empty public boolean isEmpty();

// Returns the number of elements currently in the queue public int size();

}

public class TwoStackQueueTester {

/** If implemented correctly, this code should output:

* 0

* Peter

* 2

* Paul

* Mary

* Simon

* Alvin

* Theodore

*/

public static final void main(String[] args) {

TwoStackQueue q = new TwoStackQueue();

System.out.println(q.size());

q.enqueue("Peter");

q.enqueue("Paul");

q.enqueue("Mary");

System.out.println(q.dequeue());

System.out.println(q.size());

q.enqueue("Simon");

q.enqueue("Alvin");

System.out.println(q.dequeue());

q.enqueue("Theodore");

while(!q.isEmpty())

System.out.println(q.dequeue());

}

}