LeetCode 225 [Implement Stack by Two Queues]

原题

利用两个队列来实现一个栈的功能

样例

push(1)
pop()
push(2)
isEmpty() // return false
top() // return 2
pop()
isEmpty() // return true

解题思路

• 使用两个queue

q1 = []       q2 = []
push 1
q1 = [1]      q2 = []
q1 = []       q2 = [1] 
push 2
q1 = [2]      q2 = [1]
q1 = [2, 1]   q2 = []
q1 = []       q2 = [2, 1]
push 3
q1 = [3]       q2 = [2, 1]   
q1 = [3, 2, 1] q2 = []
q1 = []        q2 = [3, 2, 1]

完整代码

import Queue

class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q1 = Queue.Queue()
        self.q2 = Queue.Queue()

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.q1.put(x)
        while self.q2.qsize() != 0:
            self.q1.put(self.q2.get())
        while self.q1.qsize() != 0:
            self.q2.put(self.q1.get())
        

    def pop(self):
        """
        :rtype: nothing
        """
        self.q2.get()
        

    def top(self):
        """
        :rtype: int
        """
        return self.q2.queue[0]
        

    def empty(self):
        """
        :rtype: bool
        """
        return self.q2.qsize() == 0