232. Implement Queue using Stacks

题目：

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.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

链接： http://leetcode.com/problems/implement-queue-using-stacks/

题解：

用栈实现队列。之前的做法是使用一个栈保存所有的数据，每次增加新数据之前先倒腾到另外一个栈里，再倒腾回来，这样的速度会很慢，只击败了13%的玩家...

仔细想了想，两个栈，一个用来push，另外一个专门用来pop。当两个栈都不为空的时候可以做到push和pop以及peek，isEmpty()都是O(1)。但最坏情况也会时间较长。总的来说可以用平均时间取胜。代码还可以再优化优化。

Time Complexity - push - O(n)， pop - O(n)， peek - O(n)， isEmpty - O(1)。

class MyQueue {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
    
    // Push element x to the back of queue.
    public void push(int x) {
        if(stack1.isEmpty()) {
            stack1.push(x);
        } else if (stack2.isEmpty()) {
            stack2.push(x);
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        } else {
            stack1.push(x);
        }        
    }

    // Removes the element from in front of queue.
    public void pop() {
        if(!stack2.isEmpty()) {
            stack2.pop();
        } else if(!stack1.isEmpty()) {
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
            stack2.pop();
        }
    }

    // Get the front element.
    public int peek() {
        if(!stack2.isEmpty()) {
            return stack2.peek();
        } else if(!stack1.isEmpty()) {
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
            return stack2.peek();
        } else 
            return 0;
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

二刷：

还是使用两个栈，一个pushStack, 一个popStack, 平时只往pushStack放入，当popStack为空的时候，push，pop和peek操作都会把pushStack里面的元素先倒腾进popStack，然后对popStack进行操作。

Time Complexity - push - O(n)， pop - O(n)， peek - O(n)， isEmpty - O(1)。

Java:

class MyQueue {
    // Push element x to the back of queue.
    Stack<Integer> pushStack = new Stack<>();
    Stack<Integer> popStack = new Stack<>();
    
    public void push(int x) {
        pushStack.push(x);
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        popStack.pop();
    }

    // Get the front element.
    public int peek() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        return popStack.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }
}

三刷:

跟二刷逻辑一样，但速度还是比较慢。

Java:

class MyQueue {
    // Push element x to the back of queue.
    Stack<Integer> pushStack = new Stack<>();
    Stack<Integer> popStack = new Stack<>();
    
    public void push(int x) {
        pushStack.push(x);
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        popStack.pop();
    }

    // Get the front element.
    public int peek() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        return popStack.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }
}

简化一下Code:

Time Complexity - push - O(1)， pop - O(n)， peek - O(n)， isEmpty - O(1)。 Space Complexity - O(n).

class MyQueue {
    // Push element x to the back of queue.
    Stack<Integer> pushStack = new Stack<>();
    Stack<Integer> popStack = new Stack<>();
    
    public void push(int x) {
        pushStack.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        peek();
        popStack.pop();
    }

    // Get the front element.
    public int peek() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        return popStack.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }
}

Update:

快了一点点，还需要进一步提速。

Time Complexity - push - O(n)， pop - O(1)， peek - O(1)， isEmpty - O(1). Space Complexity - O(n)

class MyQueue {
    Stack<Integer> stack = new Stack<>();
    
    // Push element x to the back of queue.
    public void push(int x) {
        Stack<Integer> tmp = new Stack<>();
        while (!stack.isEmpty()) tmp.push(stack.pop());
        tmp.push(x);
        while (!tmp.isEmpty()) stack.push(tmp.pop());
    }

    // Removes the element from in front of queue.
    public void pop() {
        stack.pop();
    }

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

    // Return whether the queue is empty.
    public boolean empty() {
        return stack.isEmpty();
    }
}

Reference:

https://leetcode.com/discuss/44106/short-o-1-amortized-c-java-ruby

https://leetcode.com/discuss/44124/accepted-0ms-c-solution-with-two-std-stack-easy-understand

https://leetcode.com/discuss/45146/accepted-clean-java-solution

https://leetcode.com/discuss/58346/my-java-solution-with-only-editing-the-push-method

https://leetcode.com/discuss/53948/java-solution-using-two-stacks

https://leetcode.com/discuss/47278/o-n-3o-1-solution-in-java

https://leetcode.com/discuss/67154/easy-java-solution-just-edit-push-method

https://leetcode.com/discuss/62282/my-java-solution-with-2-stacks