用两个栈模拟队列

¶题目

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

¶分析

栈的本质是先进后出,而队列的本质是先进先出.

看起来完全相反的东西,很难想象可以互相转化.

首先我们分析一下两个栈可以做什么.假设我们有1到10个数据依次进入两个栈,下面是一种设想的情况.

|------

|------

按照队列的性质,我们应该将1先弄出来.然而这是不可能的,因为1在第一个栈的底部.

唯一的办法是将1放到第二个栈的顶部.

终于大概想通了…

先进后出,先进先出,其实是两个相反的性质.类似负负得正的思想,在这里也是成立的.

不过效率极低就是…

最终代码如下

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        x =  self.stack2.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        return x

上面代码太菜了,看了另外一个人的显然更好,如下

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):




    
        # return xx
        if self.stack2==[]:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
        return self.stack2.pop()