[JAVA DATA STRUCTURES]

A Queue object can be implemented using two Stack objects. Below is an outline of how to do this. Complete the implementations of the add() and remove() methods. The key idea is that if you push all the elements from one stack onto an empty stack, then the items get reversed and what was the top-of-stack on the original stack becomes the bottom of the new stack. In the implementation below, one of the stacks is used to implement the add() method and the other stack is for the remove() method. It should always be the case that one of the two stacks is empty and the contents of the queue are in the other stack. By shifting the elements from one stack to the other, you can move the front of the queue to the top of a stack, or you can move the rear of the queue to the top of a stack.

import java.util.Stack;

public class Queue

{

private Stack forAdding = new Stack();

private Stack forRemoving = new Stack();

public void add(T item)

{

}

public T remove( )

{

}

}