LeetCode-225-用队列实现栈

解题思路：

1. 维护两个队列q1和q2，当推入队列的数据为[1,2,3]，推入1时，q1为空，直接推入q1.append(1)；
2. 当推入2时，先将q1中的1推入q2，再将2推入q1，然后将q2中1推入q1，此时q1中数据的顺序为[2,1]；
3. 推入3时，同上一步，将q2作为中转站，类似汉诺塔的最后一步，先将q1中[2,1]推入q2，接着将3推入q1，然后将q2中的数据[2,1]推入q1，此时q1的数据顺序为[3,2,1]实现了栈的先进后出规律；
4. 未操作时，队列q2始终为空，只是作为中转站；
5. 因此pop操作时，直接从q1中取出第一个数；
6. 判断empty时，只需判断q1中是否有数据即可。

Python3代码：

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = collections.deque()
        self.q2 = collections.deque()


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        # 若q1有数据，则推入q2
        while self.q1:
            self.q2.append(self.q1.popleft())
        # 将x推入q1
        self.q1.append(x)
        # 将q2推入q1
        while self.q2:
            self.q1.append(self.q2.popleft())


    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        if self.q1:
            return self.q1.popleft()
        else:
            return -1


    def top(self) -> int:
        """
        Get the top element.
        """
        if self.q1:
            return self.q1[0]


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        if not self.q1:
            return True
        return False


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