题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路
1. 引入辅助栈stack（旨在将其与指定弹出序列popV进行比较）；
2. 遍历pushV的元素，并将其压入辅助栈stack；
3. 比较stack的末尾元素（即栈顶元素）与popV中首位元素是否相等，若相等则将两个元素都从栈中弹出，继续步骤2的遍历。
# -*- coding:utf-8 -*-class Solution:def IsPopOrder(self, pushV, popV):if len(pushV)!=len(popV): #两栈长度不等不符合题目描述return Falsestack=[] #引入辅助栈stackfor i in pushV: #遍历pushV的元素stack.append(i) # 将元素追加到stack栈，i始终为栈顶元素/末尾元素while len(stack)!=0 and stack[-1]==popV[0]: #stack栈顶元素与popV中首位元素相等stack.pop() #stack栈顶元素弹出popV.pop(0) #popV首位元素弹出if len(stack)!=0: #此时辅助栈中还有元素，则说明popV中还有剩余元素，不可能是压栈序列的弹出序列return Falsereturn True
测试1：
s=Solution()pushV=[1,2,3,4,5]popV=[4,5,3,2,1]print(s.IsPopOrder(pushV,popV))# result：True
运行过程中辅助栈stack和popV的变化：
遍历开始stack:[1] popV:[4, 5, 3, 2, 1]stack:[1, 2] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3, 4] popV:[4, 5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[5, 3, 2, 1]stack:[1, 2, 3, 5] popV:[5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2] popV:[2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1] popV:[1]stack弹出末尾元素,popV弹出首位元素之后stack:[] popV:[]return True
测试2：
s=Solution()pushV=[1,2,3,4,5]popV=[4,3,5,1,2]print(s.IsPopOrder(pushV,popV))# result：False
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路
1. 引入辅助栈stack（旨在将其与指定弹出序列popV进行比较）；
2. 遍历pushV的元素，并将其压入辅助栈stack；
3. 比较stack的末尾元素（即栈顶元素）与popV中首位元素是否相等，若相等则将两个元素都从栈中弹出，继续步骤2的遍历。
# -*- coding:utf-8 -*-class Solution:def IsPopOrder(self, pushV, popV):if len(pushV)!=len(popV): #两栈长度不等不符合题目描述return Falsestack=[] #引入辅助栈stackfor i in pushV: #遍历pushV的元素stack.append(i) # 将元素追加到stack栈，i始终为栈顶元素/末尾元素while len(stack)!=0 and stack[-1]==popV[0]: #stack栈顶元素与popV中首位元素相等stack.pop() #stack栈顶元素弹出popV.pop(0) #popV首位元素弹出if len(stack)!=0: #此时辅助栈中还有元素，则说明popV中还有剩余元素，不可能是压栈序列的弹出序列return Falsereturn True
测试1：
s=Solution()pushV=[1,2,3,4,5]popV=[4,5,3,2,1]print(s.IsPopOrder(pushV,popV))# result：True
运行过程中辅助栈stack和popV的变化：
遍历开始stack:[1] popV:[4, 5, 3, 2, 1]stack:[1, 2] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3, 4] popV:[4, 5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[5, 3, 2, 1]stack:[1, 2, 3, 5] popV:[5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2] popV:[2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1] popV:[1]stack弹出末尾元素,popV弹出首位元素之后stack:[] popV:[]return True
测试2：
s=Solution()pushV=[1,2,3,4,5]popV=[4,3,5,1,2]print(s.IsPopOrder(pushV,popV))# result：False
转载请注明：XAMPP中文组官网 » Python题代码实现_栈的压入弹出序列