C# · 12月 20, 2021

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

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

题目描述

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

题目分析

栈的特点是先入后出。栈的压入和弹出是同时进行的,这意味着,压入一个数入栈后,可以选择直接弹出或者继续压入下一个数。例如,对于这样的数组{1,3},它的入栈顺序是{1,3},它的出栈顺序可以是:{1,3}(压入后立即弹出)、{2,3}(先入栈1,2,全部弹出后再入栈3)、{2,1}(入栈1,2后弹出2,再入栈3,弹出3,1)……等等。出栈形式多变,想找出一定的规律是可行的,但比较复杂。唯一可以确定的是,它每次只能弹出它的栈顶元素。

题目给出了压入序列和弹出序列,弹出序列正是这个栈每次的栈顶的元素。换句话说,在将压入序列压入栈的时候,当压入序列中的数等于弹出序列中的数时,该数就是当时的栈顶元素,此时应当弹出这个数再继续压入。当所有的数都压入完成后,如果这个栈会正好弹空,则该弹出序列符合压入序列,否则则不是。

编程思路

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

Stack stack = new Stack();

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 stack = new Stack();

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();

}