《剑指Offer》——栈和队列（Python3 实现）

栈和队列

1、用两个栈实现队列

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

思路：使用两个栈stack，stack1用来进栈，stack2是为了出栈时让stack1的所有元素先pop到stack2中，这样方便让队列的最顶端元素最先出来，即从stack2中pop出的第一个元素；pop出来之后恢复原来的stack1，将stack2中的元素依次pop到stack1中。

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

2、栈的压入弹出序列

问题：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：借⽤⼀个辅助的栈，遍历压栈顺序，先将第⼀个放⼊栈中，这⾥是1，然后判断栈顶元素是不是出栈顺序的第⼀个元素，这⾥是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈⼀个元素，则将出栈顺序向后移动⼀位，直到不相等，这样循环，等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：入栈1，2，3，4，5；出栈4，5，3，2，1；首先1入辅助栈，此时栈顶1≠4，继续入栈2，此时栈顶2≠4，继续入栈3，此时栈顶3≠4，继续入栈4，此时栈顶4=4，弹出序列向后一位，此时为5，辅助栈里面是1，2，3，此时栈顶3≠5，继续入栈5（注意：出栈后要对出栈变化后的栈用while循环保证此时栈顶层第一个节点先跟后续序列进行比较，再压入新的元素），此时栈顶5=5，出栈5，弹出序列向后一位，此时为3，辅助栈里面是1，2，3……依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self,pushV,popV):
        stack=[]
        if not pushV or not popV:
            return False
        for i in pushV:
            stack.append(i)
            while stack and stack[-1]==popV[0]:
                stack.pop()
                popV.pop(0)
        if stack:
            return False
        return True