栈的压入、弹出序列,合理性比较
栈的压入、弹出序列
http://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
核心思路是 : 咱们的要求是要检查PushV和popV的组合是否合理,那就去利用栈的性质看能不能凑出这种情况合理, 不能就不行,利用栈的后进先出。 pushV名单一个一个循环压 进stack, 每压一个pushV, 就把stack最后一位与PopV遍历到的那一位比较,如果相同就把这个从stack中弹出。。。一直循环检查PopV与stack最后一位。。。如果一旦不相等,就继续返回上一层循环继续压进stack,直到没东西可以压了。。。 跳出循环
能跳出循环的,如果stack里面还有东西,说明这个popV序列不科学是错误的,因为如果是正常的序列,stack在把pushV名单压完之后,始终是可以把自己的东西按照PopV全部倒出来的。。跳出最外层循环之后不会再剩东西
def IsPopOrder(self, pushV, popV): # 栈,pushV角标,popV角标定义 stack = [] pushVind = 0 popVind = 0 # 循环压入栈中,只要没压完 while pushVind <= len(pushV) - 1: stack.append(pushV[pushVind]) pushVind = pushVind + 1 # 比较栈的最后一位与PopV第一位 while popVind<=len(pushV) - 1 and stack[-1]== popV[popVind]: # 相等就循环pop掉栈的东西, stack.pop() # popV角标更新 popVind = popVind+1 # 如果能出来说明 if stack: return 0 return 1