Show that a stack and a queue can be used to realize any per

Show that a stack and a queue can be used to realize any permutation. that is, suppose you are given an empty stack s, and numbers, 1,2...,n in this order, initially stored in a queue, Q. show how to use only these two structures and at most a constant number of additional registers to result in any given permutation, PI, of the numbers, 1,2,..., n stored in the Q in the order specified by PI. What is the running time of your algorithm?

Solution

public interface StackInterface<AnyType>

{

   public void push(AnyType e);

   public AnyType pop();

   public AnyType peek();

   public boolean isEmpty();

}

/*the complexity of this problem is O(1)*/