面试题9：用两个栈实现队列

题目：
https://www.nowcoder.com/ta/coding-interviews

用两个栈来实现一个队列；
完成队列的Push和Pop操作；

思考：

栈是有序的 LIFO，也就是后进先出（先进后出）;
队列是有序的FIFO，也就是先进先出。

也就是要用两个先进后出的栈，实现先进先出的队列。

例如：stack1={a}; stack2={};

压入b,c:stack1={c,b,a}(a在栈底，c在栈顶);stack2={};

当我们想要弹出a时，由于a在stack1底，不能直接弹出，于是我们先将stack1的元素按照栈先入后出的原则弹出并压入stack2有：stack2={a,b,c}(此时，a在栈顶，c在栈底)；

于是，可以顺利从stack2中弹出a，总体上实现队列先入先出的性质。

总结：

push()方法可以利用list.append()方法实现；

pop()方法：判断stack2是否为空，不空，依次弹出栈顶元素；为空，则先将stack1中元素按照先入后出的原则弹出并压入stack2，然后弹出stack2中栈顶元素；总体实现队列功能。

python中可用列表表示后入先出的栈，list.pop()默认删除列表最后一个元素（此外，pop()有可选参数，如：list1.pop(1)，1为待删除元素的索引，pop方法返回删除的列表元素）；

push()方法，可看作用list.append()往列表尾追加新元素。

list1 = ['Google', 'Runoob', 'Taobao']
list_pop=list1.pop()
print( "删除的项为 :", list_pop)
print( "列表现在为 : ", list1)

删除的项为 : Taobao
列表现在为 :  ['Google', 'Runoob']

1
2
3

list2 = ['1', '2', '3']
list_push=list2.append('new_4')
print( "列表现在为 : ", list2)

列表现在为 :  ['1', '2', '3', 'new_4']

class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=['x','y']#顺序，先x，再y，说明在之前有：stack1={'y','x'},y比x先入栈
    
#     def push(self, node):
#         self.stack1.append(node)#直接在stack1中压入元素

#这是一个参考博主的写法，增加了对stack1是否为空的判断及操作
    def push(self, node):
        if self.stack1:#如果stack1非空，在其中压入元素
            self.stack1.append(node)
        else:#若stack1空
            while self.stack2:#在stack2非空时（此时，说明其中数据先进入队列）
                self.stack1.append(self.stack2.pop())#先将stack2中元素弹出并压入到stack1，形成新的待追加新元素的栈，
#我猜这样是为了方便后面的pop处理，因为这样不用判断stack2是否为空（经过形成新的stack1的处理，stack2始终为空），直接将stack1元素弹出压入stack2，再进行pop就好
            self.stack1.append(node)#然后压入新的元素，此步不可少，不然会造成新压入的第一个元素缺失
            
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        elif self.stack1:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
        else:
            return None

method = Solution()
for i in range(1,6):
    push = method.push(i)

print("stack1=",method.stack1)
print("stack2=",method.stack2)

stack1= ['y', 'x', 1, 2, 3, 4, 5]
stack2= []

pop = method.pop()
print("stack1=",method.stack1)
print("弹出的元素为",pop)
print("stack2=",method.stack2)

stack1= []
弹出的元素为 y
stack2= [5, 4, 3, 2, 1, 'x']

由于在push方法中增加了对stack2的处理，原pop方法可以简化，因为处理后的stack2始终为空

class Solution1:
    def __init__(self):
        self.stack1=[]
        self.stack2=[6,7]
    def push(self, node):
        if self.stack2:
            while self.stack2:
                self.stack1.append(self.stack2.pop())
        self.stack1.append(node)
    def pop(self):
        if self.stack1:#如果stack1不空
            while self.stack1:
                self.stack2.append(self.stack1.pop())#直接将stack1中元素弹出，再压入stack2，形成待弹出栈
        return self.stack2.pop()

method = Solution1()
for i in range(1,6):
    push = method.push(i)

print("stack1=",method.stack1)
print("stack2=",method.stack2)

stack1= [7, 6, 1, 2, 3, 4, 5]
stack2= []

pop = method.pop()
print("stack1=",method.stack1)
print("弹出的元素为",pop)
print("stack2=",method.stack2)

stack1= []
弹出的元素为 7
stack2= [5, 4, 3, 2, 1, 6]

reference：

1.https://blog.csdn.net/Datawhale/article/details/82118919

2.https://blog.csdn.net/fuxuemingzhu/article/details/79499461

1
2

面试题9：用两个栈实现队列

谢谢大爷~