4
栈的压入、弹出序列（算法22）
source link: https://allenwind.github.io/blog/3058/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Mr.Feng Blog
NLP、深度学习、机器学习、Python、Go
栈的压入、弹出序列（算法22）
问题：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设：压入栈的所有数字均不相等。
例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
其实模拟这个压入、弹出的过程即可，如果第一个序列表示栈的压入顺序，而弹出顺序是第二个序列，那么最后的栈一定是空栈。
实现如下，
def validateStackSequences(pushed, popped):
stack = []
i = 0
for num in pushed:
# 模拟压入
stack.append(num)
while stack and stack[-1] == popped[i]:
# 满足条件则弹出
stack.pop()
i += 1
return not stack
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK