Two Stack Queue: 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.

a) Write a class TwoStackQueue that provides the Queue ADT (as specified in the MyQueue.java interface) 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. Use your stack implementation from programming problem 1.

MyQueue.java

/** 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();

}

b) 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 Program2.java. You can find a sample tester class in the file TwoStackQueueTester.java. 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.

TwoStackQueueTester.java

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

}

}

c. In a file called Program2.txt, discuss the big-O running time of the enqueue and dequeue operation for your queue implementation.