A Queue using an additional stack (both the stacks are allocated in the heap)

QueueFrom2Stack

import java.util.Stack;

public class QueueFrom2Stack<E> {

    Stack<E> stack = new Stack<E>();
    Stack<E> popStack = new Stack<E>();

    public void push(E element) {
        this.stack.push(element);
    }

    // It's better to have the expensive operation
    // in the pop of queue
    public E pop() {
        if (this.popStack.empty()) {
            while (!this.stack.empty()) {
                this.popStack.push(this.stack.pop());
            }
        }
       // As long as the popStack is not empty, we can
       // get a O(1) time, otherwise O(n)
        return this.popStack.pop();
    }

    public static void main(String[] args) {
        QueueFrom2Stack<String> queue = new QueueFrom2Stack<String>();
        queue.push("A");
        queue.push("B");
        queue.push("C");
        queue.push("D");
        queue.push("E");
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
    }
}