牛客网《剑指offer》之Python2.7实现：栈的压入、弹出（利用辅助队列）

题目描述

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

思路

思考下题目的场景：如何判断是否为其弹出序列？
入栈：1,2,3,4,5
出栈：4,5,3,2,1 √
出栈：4,3,5,1,2 ×
需要注意，入栈和出栈并不是一口气全部入栈，一口气全部出栈。而是有可能入两个，出一个，再入两个，再出x个这样的过程，拿出草纸，画出题目中这个入栈、出栈的过程，

我们设置一个辅助队列queue，

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        queue = []
        while pushV:
            # 如果入栈队列的最后一个元素与出栈队列第一元素相同，则该元素符合出栈/入栈顺序规则，删除之
            if pushV[-1] == popV[0]:
                pushV.pop()
                popV.pop(0)
            else:          
            	# 如果辅助队列不为空，且辅助队列首元素与出栈队列首元素形同，
            		# 则该元素符合出栈/入栈顺序规则，删除之
                if queue and queue[0] == popV[0]:
                    popV.pop(0)
                    queue.pop(0)
                # 将入栈对象为元素进入辅助队列
                elif pushV:
                    queue.append(pushV.pop())
		# 辅助队列为空，则所有元素均符合出栈/入栈顺序规则。
        return len(queue) == 0  
test = Solution()   
pushV = [1,2,3,4,5]
popV = [3,5,4,2,1]
print (test.IsPopOrder(pushV, popV))

加上打印看结果更清晰哦:

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        i = 0
        queue = []
        while pushV:
            i += 1
            print ("---------------count:", i)
            print ("pushV before", pushV)
            print ("popV  before", popV)
            print ("if", pushV[-1] == popV[0], pushV[-1] , popV[0])
            if pushV[-1] == popV[0]:
                pushV.pop()
                popV.pop(0)
            else:
                # print ("middle", stack[0], popV[0])               
                if queue and queue[0] == popV[0]:
                    popV.pop(0)
                    queue.pop(0)
                elif pushV:
                    queue.append(pushV.pop())
            print ("pushV after:", pushV)
            print ("popV  after:", popV)
            print ("queue after:", queue)
        return len(queue) == 0    

test = Solution()   
pushV = [1,2,3,4,5]
popV = [3,5,4,2,1]
print (test.IsPopOrder(pushV, popV))

打印如下：

---------------count: 1
pushV before [1, 2, 3, 4, 5]
popV  before [3, 5, 4, 2, 1]
if False 5 3
pushV after: [1, 2, 3, 4]
popV  after: [3, 5, 4, 2, 1]
queue after: [5]
---------------count: 2
pushV before [1, 2, 3, 4]
popV  before [3, 5, 4, 2, 1]
if False 4 3
pushV after: [1, 2, 3]
popV  after: [3, 5, 4, 2, 1]
queue after: [5, 4]
---------------count: 3
pushV before [1, 2, 3]
popV  before [3, 5, 4, 2, 1]
if True 3 3
pushV after: [1, 2]
popV  after: [5, 4, 2, 1]
queue after: [5, 4]
---------------count: 4
pushV before [1, 2]
popV  before [5, 4, 2, 1]
if False 2 5
pushV after: [1, 2]
popV  after: [4, 2, 1]
queue after: [4]
---------------count: 5
pushV before [1, 2]
popV  before [4, 2, 1]
if False 2 4
pushV after: [1, 2]
popV  after: [2, 1]
queue after: []
---------------count: 6
pushV before [1, 2]
popV  before [2, 1]
if True 2 2
pushV after: [1]
popV  after: [1]
queue after: []
---------------count: 7
pushV before [1]
popV  before [1]
if True 1 1
pushV after: []
popV  after: []
queue after: []
True