题目:栈的压入、弹出序列
题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
思路:借用一个额外的辅助栈, 模拟一下pop的过程,看能否得到弹出序列。
举例:
压入序列:1,2,3,4,5
弹出序列:3,5,4,2,1
推理过程:
a用于压入,b用于弹出,则
- a=[1], 因为弹出序列第一个为3,所以此时不可能弹出,继续压入
- a=[1,2], 同1,不可能弹出,继续压入
- a=[1,2,3], 此时栈中出现了3,那么可以弹出3到b中,b=[3], a=[1,2]
- a是否继续弹出?发现弹出序列需要a弹出的是5,所以无法继续弹出只能继续压入 a=[1,2,4]
- 同样此时弹出栈顶元素无法获得5,所以继续压入 a=【1,2,4,5]
- 此时出现了元素5,可以弹出b=[3,5], a=[1,2,4]
- a是否继续弹出?发现弹出序列需要a弹出的是4,恰好a栈顶元素是4,于是弹出 a=[1,2], b=[3,5,4]
- a是否继续弹出?弹出序列需要元素2,恰好a的栈顶元素是2,于是继续弹出 a=[1], b=[3,5,4,2]
- a是否继续弹出? 弹出序列需要元素1,恰好a的栈顶元素是1,于是继续弹出a=[],b=[3,5,4,2,1]
- 此时a为空,且没有元素可以继续压入,说明压入元素都pop成功,于是可以获得输出序列。
总结整个过程:
迭代步骤:辅助栈a, 当前栈a能否按弹出栈弹出,能则依序弹出,否则继续压入
终止条件: 所有的压入步骤完成后,辅助栈为空,则表示恰好得到弹出序列,否则不能得到弹出序列
python代码实现
def pop_order(push_list, pop_list):
a = []
for v in push_list:
a.append(v) # 压入
while len(a)>0 and a[-1] == pop_list[-1]: # a可以弹出所需要的元素,则弹出
a.pop()
pop_list.pop()
if a: return False
return True
print(pop_order([1,2,3,4,5], [3,5,4,2,1]))
print(pop_order([1,2,3,4,5], [5,1,3,2,4]))