正文
Swift处理堆栈问题——给定两组序列，其中一个序列表示栈的push 顺序，判断另一个序列有没有可能是对应的pop 顺序
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目：输入两个整数序列。其中一个序列表示栈的push 顺序，判断另一个序列有没有可能是对应的pop 顺序。
为了简单起见，我们假设push 序列的任意两个整数都是不相等的。
比如输入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一个pop 系列，但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。
分析:
我们首先定义遍历push的序数i=0 遍历pop序列的序数 j =0
我们可以先遍历给出的push序列，并且时刻与pop序列的头元素pop[j]进行比较
若找到与pop序列的头元素相同的push元素，则j向右移一位（移动完成后需要比较pop[j] 与当前的栈顶元素是不是相等，若相等则需要退出当前栈顶元素）
若push已经遍历完成，但是j依然小于 pop的元素个数，则我们只需要继续比较pop中剩余的元素与当前栈中的元素是不是对应的即可
代码：
func judgeStackOrder(var pushArray:Array<Int>,var popArray:Array<Int>)->Bool{
var tempStack = Stack<Int>() //构造一个tempStack的临时栈
if(pushArray == [] || popArray == []){
return false
}
if(pushArray.count != popArray.count){
return false
}
var i = 0,j = 0
for(i; i < pushArray.count ; i++){
println(i)
if(pushArray[i] != popArray[j]){
println(pushArray[i])
tempStack.push(pushArray[i])
}
else{
tempStack.push(pushArray[i])
tempStack.pop()
if(tempStack.top() == popArray[j+1]){
tempStack.pop()
j++
}
j++
}
}
if(j < popArray.count){
while( j < popArray.count ){
if(tempStack.top() != popArray[j] ){
println(tempStack.top())
popArray[j]
return false
}
else{
tempStack.pop()
j++
continue//若当前栈顶元素等于当前j所处的pop序列的元素，则临时栈退栈，并且使j向右移动一个单位，跳入下一轮循环
}
}
return true
}
return false
}
//测试代码
var pushArray:Array<Int> = [1,3,5,7,9,8]
var popArray:Array<Int> = [3,1,9,8,7,5]
judgeStackOrder(pushArray, popArray)
