Implement the following operations of a queue using stacks.
push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Notes:
You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.

My original solution: rearrage the element when adding a new one – add the new element to the head of the stack.
But this solution keeps initializing new stack each time the push() method is called, so not efficient.
The right way for this kind of questions is to have 2 data structures pre-defined. (Like the solution at the bottom)
This can be transfered as “225. Implement Stack using Queues”

class MyQueue {

    Stack<Integer> stack;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if(stack.size()==0) stack.push(x);
        else{
            Stack<Integer> tmp = new Stack<>();
            while(stack.size()>0){
                tmp.add(stack.pop());
            }
            stack.push(x);
            while(tmp.size()>0){
                stack.add(tmp.pop());
            }
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack.pop();
    }

    /** Get the front element. */
    public int peek() {
        return stack.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.size()==0;
    }
}

Better solution:

I have one input stack, onto which I push the incoming elements, and one output stack, from which I peek/pop.
I move elements from input stack to output stack when needed, i.e., when I need to peek/pop but the output stack is empty.
When that happens, I move all elements from input to output stack, thereby reversing the order so it’s the correct order for peek/pop.

The loop in peek does the moving from input to output stack.
Each element only ever gets moved like that once, though, and only after we already spent time pushing it, so the overall amortized cost for each operation is O(1).

class MyQueue {

    Stack<Integer> input = new Stack();
    Stack<Integer> output = new Stack();

    public void push(int x) {
        input.push(x);
    }

    public void pop() {
        peek();
        output.pop();
    }

    public int peek() {
        if (output.empty())
            while (!input.empty())
                output.push(input.pop());
        return output.peek();
    }

    public boolean empty() {
        return input.empty() && output.empty();
    }
}