题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：使用两个栈来进行轮换， 设为l1, l2。
入队：判断当前的数据在l1, 还是l2。 如果在l2 则switch 到l1 进行入队
出队：将l1中的所有弹出到l2中，并弹出l2的最上面元素
其他：可以将l1 中你n-1个数字放入l2 这样 遇到pop 从l1 弹出，再次pop时候，从l2弹出，可以直接弹出两个，减少了switch的次数，其实增加了判断次数。各有优略，几本没啥区别。
如图：
image.png
# 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class List2Stack(object):
def __init__(self):
self.l1 = []
self.l2 = []
def _switch(self, x, y):
'''
:param x: reverse x -->y ,
:param y: x(1, 3) y(3, 1)
:return:
'''
y.extend([x.pop() for i in range(0, len(x))])
return y
def npush(self, num):
if self.l1:
self.l1.append(num)
else: # l1 is none, maybe l2 is not
if len(self.l2) == 0:
self.l1.append(num)
else: # it's in l2 pull back to l1
self._switch(self.l2, self.l1)
self.l1.append(num)
def npop(self):
if self.l1: # in l1
self._switch(self.l1, self.l2)
return self.l2.pop() if self.l2 else None
else: # l1 is None
if len(self.l2) == 0:
return None
else:
return self.l2.pop()
if __name__ == '__main__':
stk = List2Stack()
stk.npush(1)
stk.npush(9)
print stk.npop()
