6、用两个栈实现一个队列

题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

队列：先进先出。
栈：后进先出。

也就说，要实现先push进去的点，也要先出来。

首先想到的就是，把一个list比如1,2,3先压入S1中，然后再依次弹出压入S2中，这样在pop的时候，只需要pop出S2的栈顶元素即可。
但是，这个思路只能实现一次性的操作。
如果在弹出3的时候，又压入了4，那么此时再把4压入S1，S1又弹出4压入S2，那么此时S2栈顶就是4了，再弹出的就是4而不是2了。

因此，想到转换思路，放慢一下脚步：对于第一次压入的L1，先依次压入S1，然后依次弹出并压入到S2，如果下次又来了L2，那么我们就先压入S1然后等L2的元素都弹完了（也就是说，等先进去的都先弹出了，再把S1中后来进来的L2再依次压入S2中。，这样就能够保证先进先出了）

将上面想法，用伪码表示如下：

上面所述，就是在pop时，进行判断S2是否为空，再决定是否对S2执行相应的操作。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.S1 = []
        self.S2 = []
    def push(self, node):
        # write code here
        #所有来的点，都先压入到S1中。

        self.S1.append(node)

    def pop(self):
        # return xx
        # 在弹出时进行判断
            # 如果此时S2不为空，则不对S2进行操作
            #如果此时S2为空，则把S1中的所有元素，挨个压入到S2中，使栈顶为最先push进的元素
        if len(self.S2) == 0:
            for i in range(len(self.S1)):
                temp = self.S1.pop()
                self.S2.append(temp)
        return self.S2.pop()

Q = Solution()
Q.push(1)
Q.push(2)
Q.push(3)
print(Q.pop())
Q.push(4)
Q.push(5)
print(Q.pop())
print(Q.pop())
print(Q.pop())
print(Q.pop())