栈的压入、弹出序列
问题
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序
假设压入栈的所有数字均不相等
例如序列 1,2,3,4,5
是某栈的压入顺序,序列 4,5,3,2,1
是该压栈序列对应的一个弹出序列,但 4,3,5,1,2
就不可能是该压栈序列的弹出序列(注意:这两个序列的长度是相等的)
思路
用一个栈来模拟压入、弹出的过程即可:
使用一个指针指向弹出序列的头部
根据压入序列入栈
入栈时判断入栈元素是否跟弹出序列指针元素相同
若相同,则指针向后移,数据出栈
重复执行
1
,2
,3
,4
直到所有元素都入栈完成,如果出栈顺序正确,此时栈为空
实现
1 | function IsPopOrder(pushArr, popArr) { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 乱炖锅!
评论