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

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

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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

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

{

stack.push(pushA[i]);

while((!stack.empty())&&(stack.peek()==popA[index])){

stack.pop();

index++;

}

}

return stack.empty();

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!