下面要给大家分享的是一个和栈的压入、弹出序列有关的内容，一起来了解一下吧。

题目：

输入2个整数序列，第1个序列表示栈的压入顺序，请判断第2个序列是否是这个栈的弹出顺序。

假设：

压入栈的所有数字都不相等。

例:

序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是这个压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是这个压栈序列的弹出序列。

注：

这2个序列的长度是相等的。

思路1

代码实现：

class Solution {
public:
    bool IsPopOrder(vector
<int> pushV,vector
    <int> popV) {
        if(pushV.size() == 0) return false;
        vector
        <int> stack;
        for(int i = 0,j = 0 ;i < pushV.size();){
            stack.push_back(pushV[i++]);
            while(j < popV.size() && stack.back() == popV[j]){
                stack.pop_back();
                j++;
            }      
        }
        return stack.empty();
    }
};

思路2：

借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，随后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，一直到相等之后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，一直到不相等，这样循环等压栈顺序遍历完成，假如辅助栈还不为空，那么就表示弹出序列不是这个栈的弹出顺序。

例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，这个时候栈顶1≠4，继续入栈2

这个时候栈顶2≠4，继续入栈3

这个时候栈顶3≠4，继续入栈4

这个时候栈顶4=4，出栈4，弹出序列向后一位，这个时候为5，,辅助栈里面是1,2,3

这个时候栈顶3≠5，继续入栈5

这个时候栈顶5=5，出栈5,弹出序列向后一位，这个时候为3，,辅助栈里面是1,2,3

….

依次执行，最后辅助栈为空。

假如，不为空，那么就表示弹出序列不是这个栈的弹出顺序。

代码实现：

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack
<Integer> s = new Stack
    <Integer>();
        //用于标识弹出序列的位置
        int popIndex = 0;
        for(int i = 0; i< pushA.length;i++){
            s.push(pushA[i]);
            //如果栈不为空，且栈顶元素等于弹出序列
            while(!s.empty() &&s.peek() == popA[popIndex]){
                //出栈
                s.pop();
                //弹出序列向后一位
                popIndex++;
            }
        }
        return s.empty();
    }
}

思路3

代码实现：

import java.util.ArrayList;
import java.util.Stack;
public class Solution
{
    public boolean IsPopOrder(int[] pushA, int[] popA)
    {
        //数组为空的情况
        if (pushA.length == 0 || popA.length == 0)
        {
            return false;
        }
        //弹出序列的下表索引
        int popIndex = 0;
        //辅助栈
        Stack < Integer > stack = new Stack < Integer > ();
        for (int i = 0; i < pushA.length; i++)
        {
            //不停地将pushA中的元素压入栈中，一旦栈顶元素与popA相等了，则开始出栈
            //不相等则继续入栈
            stack.push(pushA[i]);
            while (!stack.isEmpty() && stack.peek() == popA[popIndex])
            {
                stack.pop();
                popIndex++;
            }
        }
        //栈中没有元素了说明元素全部一致，并且符合弹出顺序，那么返回true
        return stack.isEmpty();
    }
}

以上和栈的压入、弹出序列有关的实例就给大家分享到这里了，更多的java实例，请继续关注奇Q工具网的java实例栏目了解吧。