• 周日. 10 月 6th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

栈的压入弹出序列

admin

11 月 28, 2021

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

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        
      
    }
}

annalysis:

判断序列 4 5 3 2 1 是否为弹出序列

 

判断序列4 3 5 1 2是否为弹出序列

经过上面的分析,思路就很清楚了,下面我们开始写代码实现

首先我们需要创建一个栈stack按照数组pushA的顺序依次压栈,然后再创建一个栈pop_stack表示弹出序列。每次压入一个数就判断当前栈顶stack是否与弹出栈pop_stack的栈顶相等。如果相等那么就弹出当前的栈顶stack元素,然后继续比较stack和pop_stack的栈顶,如果不相等,就继续压入。

resolution:

   public boolean IsPopOrder(int [] pushA,int [] popA) {
            //创建两个栈分别存储压栈序列和弹出序列
            Stack<Integer> stack = new Stack<Integer>();
            Stack<Integer> popStack = new Stack<Integer>();
            boolean flg = false;

            //处理特殊情况
            if(pushA.length == 0 || popA.length == 0 ) return flg;

            //将popA数组倒序存入弹出栈(因为栈为后进先出,先进后出)
            for(int i = popA.length - 1; i>=0;i--){
                popStack.push(popA[i]);
            }

            //首先先将第一个数压入栈stack
            stack.push(pushA[0]);
            //这里i的初值为1
            int i = 1;

            //设置终止条件为stack不为空
            while(!stack.isEmpty()){
                //处理当stack为空的时候的栈顶值,否则会抛出异常
                //stack==null时不能调用stack.peek()方法
                int stackPeek = 0;
                if(stack.isEmpty()){
                    stackPeek = 0;
                }else {
                    stackPeek = stack.peek();
                }
                int popStackPeek = popStack.peek();

                if(stackPeek != popStackPeek){
                    //处理特殊情况
                    if(i == pushA.length) break;
                    stack.push(pushA[i]);
                    i++;

                }

                if(stack.peek() == popStack.peek()){
                    stack.pop();
                    popStack.pop();
                    //当弹出栈弹完了说明能够对应,返回true
                    if(popStack.isEmpty()) flg = true;
                }
            }

            return flg;

        }

总结:在编码的过程中还是遇到了很多的小问题,首先就是处理特殊情况不全面,没有考虑数组长度为0的时候,以及调用stack.peek方法的时候没有考虑到stack为空的情况。贴上stack.peek()的源码

  /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();//可以看出当len==0时,会抛出异常
        return elementAt(len - 1);
    }

其次就是压入stack的第一个数的时候什么时候压入,以及i应该从0开始还是1开始这里搞了半天。

以及while()里面的终止条件设置也出现了点问题,我最先设置的是i不大于pushA的数组长度,以及最后如何修改返回值(当popStack为空的时候事实上就已经满足了条件)

还有就是测试的时候,没有考虑周全测试用例,比如两个数组都为{1}{1}的情况,以及{1}{2}的情况。

还有一个说重要也不重要,但是又很让人头疼的问题是,因为我是在idea里面写的代码,但是粘贴到牛客网的时候,只粘贴了方法,没有注意头文件,导致一直编译不通过,真是蠢到家了,以后一定要注意这些小问题

发表回复