栈的压入、弹出序列问题解决

栈的压入、弹出序列问题解决

题目描述

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

题目分析

栈的特点是先入后出。栈的压入和弹出是同时进行的，这意味着，压入一个数入栈后，可以选择直接弹出或者继续压入下一个数。例如，对于这样的数组{1,2,3}，它的入栈顺序是{1,2,3}，它的出栈顺序可以是：{1,2,3}（压入后立即弹出）、{2,1,3}（先入栈1,2，全部弹出后再入栈3）、{2,3,1}（入栈1,2后弹出2，再入栈3，弹出3,1）……等等。出栈形式多变，想找出一定的规律是可行的，但比较复杂。唯一可以确定的是，它每次只能弹出它的栈顶元素。
题目给出了压入序列和弹出序列，弹出序列正是这个栈每次的栈顶的元素。换句话说，在将压入序列压入栈的时候，当压入序列中的数等于弹出序列中的数时，该数就是当时的栈顶元素，此时应当弹出这个数再继续压入。当所有的数都压入完成后，如果这个栈会正好弹空，则该弹出序列符合压入序列，否则则不是。

编程思路

首先，需要声明一个栈Stack，来进行压入和弹出操作。

Stack<Integer> stack = new Stack<Integer>();

Stack类的方法说明如下：

然后，还需要一个index指示弹出序列的位置

int index = 0;

接下来，for循环将压入序列的数压入该stack中；同时，判断压入的数是否等于index所指位置的弹出序列的数；如果stack不为空且两个数相等（题目中条件是这个序列没有重复的元素），则弹出这个数，并且让index指向下一个元素

for(int i=0;i<pushA.length;i++){
        stack.push(pashA[i]);
        while((!stack.empty())&&(pushA[i]==popA[index])){
                stack.pop();
                index++;
        }
}

最后判断该stack是否为空，如为空则该弹出序列符合压入序列，否则不符合
完整代码段如下

import java.util.Stack;
public boolean IsPopOrder2(int [] pushA,int [] popA){
		Stack<Integer> stack = new Stack<Integer>();
		int index = 0;
		for(int i=0;i<pushA.length;i++)
		{
			stack.push(pushA[i]);
			while((!stack.empty())&&(stack.peek()==popA[index])){
				stack.pop();
				index++;
			}
		}
		return stack.empty();
	}