【刷算法】栈的压入、弹出序列

灰太狼 2021-09-18 14:48 254阅读 0赞

# 题目描述 #

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

# 分析 #

其实该题就是考察一个进栈序列能否和一个出栈序列对应起来，但是棘手的地方在于：一个进栈序列可能会有多个出栈的顺序，所以还是得好好想一想。  
  
  
可以从一个简单的例子开始：  
  
序列A：1,2,3  
  
序列B：2,3,1  
  
1先进栈，B序列中未出栈的第一个数字是2，说明此时1不能再接着出栈；  
  
2再进栈，B序列中未出栈 的第一个数字是2，说明第一个出栈的数字是2，那么2就此出栈；  
  
此时栈顶元素为1，B序列中未出栈的第一个数字是1，说明1是自2出栈后的再一个出栈元素，那么1就此出栈，此时栈为空；  
  
3继续进栈，此时B序列的中未出栈的第一个数字是3，说明3是再一个出栈元素，那么3就此出栈，此时栈为空，序列A也全都进栈完毕了；  
  
栈空了，序列A也进栈完毕了，说明B就是A的弹出序列。

# 代码实现 #

接着这个思路，可以试着写代码了