[剑指 Offer 第 2 版第 9-1 题] “用两个栈实现队列”做题记录

第 9-1 题：用两个栈实现队列

传送门：AcWing：用两个栈实现队列，牛客网 online judge 地址。

请用栈实现一个队列，支持如下四种操作：

push(x) – 将元素x插到队尾；

pop() – 将队首的元素弹出，并返回该元素；

peek() – 返回队首元素；

empty() – 返回队列是否为空；

注意：

你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；

如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；

输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作；

样例

``` MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false ```

分析：+ 相关的练习还有 LeetCode 第 232 题，还有第 225 题。 + 在这里我设置了一个“上一次的操作”作为状态。具体应用如下：

如果“上一次的操作”是 push：

1、我继续 push 的时候，就可以继续往栈里存数据；
2、但是如果我 pop 的话，就要把“栈底”的元素拿出来，拿出之前，要把“栈底”以上的所有元素弹出到另一个栈中。此时，如果继续出队的话，就从临时栈中陆续弹出“栈顶”元素就可以了。

如果“上一次的操作”是 pop：

1、如果我继续 pop，因为在上一次 pop 的时候，就把之前那个栈中的元素全部弹出到一个新的栈，此时这个新栈继续弹出“栈顶”元素，其实就是原来入队的顺序；
2、如果我 push，就得恢复之前入队的顺序，因此，要把这个栈中的数据全部弹出到之前入队的那个栈。

总而言之，我们可以准备两个栈 stack1 和 stack2 ：
1、使用 stack1 专门用于 push 的时候用，要“出队”之前，全部弹出到 stack2，从 stack2 弹出；
2、使用 stack2 专门用于 pop 的时候用，要“入队”之前，全部弹出到 stack1，从 stack1 压入。

Java 代码：

  import java.util.Stack;

    public class Solution {
        /**
         * 专门 push 的时候用
         */
        private Stack<Integer> stack1 = new Stack<Integer>();
        /**
         * 专门 pop 的时候用
         */
        private Stack<Integer> stack2 = new Stack<Integer>();

        private State lastState = State.PUSH;

        enum State {
            PUSH, POP
        }

        public void push(int node) {
            if (lastState == State.PUSH) {
                stack1.add(node);
            } else {
                assert lastState == State.POP;
                // 如果上一步是 pop 的话，
                while (!stack2.isEmpty()) {
                    stack1.add(stack2.pop());
                }
                stack1.add(node);
                lastState = State.PUSH;
            }
        }

        public int pop() {
            if (lastState == State.POP) {
                if (stack2.empty()) {
                    throw new IllegalArgumentException("queue is empty");
                }
                return stack2.pop();
            } else {
                // 如果上一步是 PUSH 的话
                while (!stack1.empty()) {
                    stack2.add(stack1.pop());
                }
                lastState = State.POP;
                return stack2.pop();
            }
        }
    }

注意：下面这个逻辑是错的，应该是只要 stack2 是空的，才把 stack1 的元素全部搬到 stack2，这里要小心。

      def __shift(self):
            if self.stack1:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())

Python 代码：

  class MyQueue(object):

        def __init__(self):
            """
            Initialize your data structure here.
            """

            self.stack1 = []
            self.stack2 = []

        def push(self, x):
            """
            Push element x to the back of queue.
            :type x: int
            :rtype: void
            """
            self.stack1.append(x)

        def __shift(self):
            if len(self.stack2) == 0:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())

        def pop(self):
            """
            Removes the element from in front of queue and returns that element.
            :rtype: int
            """
            self.__shift()
            return self.stack2.pop()

        def peek(self):
            """
            Get the front element.
            :rtype: int
            """
            self.__shift()
            return self.stack2[-1]

        def empty(self):
            """
            Returns whether the queue is empty.
            :rtype: bool
            """
            return len(self.stack1) == 0 and len(self.stack2) == 0

    # Your MyQueue object will be instantiated and called as such:
    # obj = MyQueue()
    # obj.push(x)
    # param_2 = obj.pop()
    # param_3 = obj.peek()
    # param_4 = obj.empty()