判断序列是否为该栈的弹出顺序,如何实现?思路分享

KLQ 2020-04-28 14:06:38 java常见问答 8948

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

题目:

输入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实例栏目了解吧。