225. 用队列实现栈

• 用两个队列实现栈的功能，思路如下：
  1. 往空队列中放新元素
  2. 把非空队列中的元素依次放入刚才添加了新元素的队列，直到非空队列变为空队列

class MyStack(object):

    def __init__(self):
        self.queue1 = []
        self.queue2 = []


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """

        if not self.queue1:
            self.queue1.append(x)
            while self.queue2:
                self.queue1.append(self.queue2.pop(0))
        else:
            self.queue2.append(x)
            while self.queue1:
                self.queue2.append(self.queue1.pop(0))



    def pop(self):
        """
        :rtype: int
        """
        if self.queue1:
            return self.queue1.pop(0)
        elif self.queue2:
            return self.queue2.pop(0)
        else:
            return None


    def top(self):
        """
        :rtype: int
        """
        # 返回列表的第一个元素但不出队
        if self.queue1:
            return self.queue1[0]
        elif self.queue2:
            return self.queue2[0]
        else:
            return None


    def empty(self):
        """
        :rtype: bool
        """
        return not self.queue1 and not self.queue2

\

232. 用栈实现队列

• 用栈实现队列，思路如下：
  1. 将两个栈分别称入队栈和出队栈
  2. 当出队栈存在内容的时候，出队栈的栈顶即为第一个出队的元素
  3. 若出堆栈没有元素，而需求为出栈，我们就需要把入队栈的内容放入出队栈，然后再从出堆栈取栈顶

 class MyQueue(object):

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        self.stack1.append(x)

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

    def peek(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self):
        return not self.stack1 and not self.stack2