232. Implement Queue using Stacks

 一刷 07/2022

Version #2 Two Stack - time optimized

We don't transfer until the output is empty

Time - amortized O(1)

Space O(N)

Runtime: 1 ms, faster than 69.17% of Java online submissions for Implement Queue using Stacks.

Memory Usage: 42 MB, less than 40.33% of Java online submissions for Implement Queue using Stacks.

class MyQueue {

    Stack<Integer> input;

    Stack<Integer> output;

    public MyQueue() {

        input = new Stack<>();

        output = new Stack<>();

    }

    

    public void push(int x) {

        input.push(x);

    }

    

    private void transfer() {

        while (!input.isEmpty()) {

            output.push(input.pop());

        }

    }

    

    public int pop() {

        if (output.isEmpty()) {

            transfer();

        }

        return output.pop();

    }

    

    public int peek() {

        if (output.isEmpty()) {

            transfer();

        }

        return output.peek();

    }

    

    public boolean empty() {

        return input.isEmpty() && output.isEmpty();

    }

}

Version #1 Two Stacks 

Time - worst case O(N) time

Space O(N)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement Queue using Stacks.

Memory Usage: 41.9 MB, less than 49.96% of Java online submissions for Implement Queue using Stacks.

class MyQueue {

    Stack<Integer> firstStack;

    Stack<Integer> secondStack;

    public MyQueue() {

        firstStack = new Stack<>();

        secondStack = new Stack<>();

    }

    

    public void push(int x) {

        while (!secondStack.isEmpty()) {

            firstStack.push(secondStack.pop());

        }

        firstStack.push(x);

    }

    

    public int pop() {

        while (!firstStack.isEmpty()) {

            secondStack.push(firstStack.pop());

        }

        return secondStack.pop();

    }

    

    public int peek() {

        while (!firstStack.isEmpty()) {

            secondStack.push(firstStack.pop());

        }

        return secondStack.peek();

    }

    

    public boolean empty() {

        return firstStack.isEmpty() && secondStack.isEmpty();

    }

}