13 给定的出栈序列是否满足入栈序列

本文主要是介绍13 给定的出栈序列是否满足入栈序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

本博文部分图片, 思路来自于剑指offer 或者编程珠玑

问题描述

这里写图片描述

思路

对于这个问题, 书中给出了一种解法

思路 : 依照给定的序列模拟进行压栈, 出栈操作, 判断是否能够形成给定的出栈序列, 详细思路请见 “剑指offer”, 或者下面的代码的注释

参考代码

/*** file name : Test06StackPushPopOrder.java* created at : 2:15:32 PM Jun 7, 2015* created by 970655147*/package com.hx.test05;public class Test06StackPushPopOrder {// 给定一个入栈顺序  判定是否能形成制定的出栈序列public static void main(String []args) {int[] pushSeq = new int[] {1, 2, 3, 4, 5 };
//      int[] popSeq = new int[] {1, 2, 3, 4, 5 };int[] popSeq = new int[] {1, 3, 2, 5, 4 };
//      int[] popSeq = new int[] {5, 4, 3, 2, 1 };isStatisfiyPushPopOrder(pushSeq, popSeq);}// 思路 : 先判断Stack顶部的元素是否是下一个popSeq中的元素[top]   如果是, 则直接从stack中pop该元素// 否则  将pushSeq中的元素 压入Stack中, 直到新的栈顶元素为top 或者push了pushSeq中所有的元素// 现在 判定Stack的顶部元素是否是top   如果是, pop顶部元素, 进入下一个循环, 判定下一个popSeq的元素// 否则 则说明添加了所有的pushSeq中的元素 也没有找到一个和top相同的元素    表示不可能形成此输出序列  返回falsepublic static void isStatisfiyPushPopOrder(int[] pushSeq, int[] popSeq) {Deque<Integer> stack = new LinkedList<Integer>();boolean isLeagel = true;int pushIdx = 0, popIdx = 0;        while(popIdx < popSeq.length) {int top = popSeq[popIdx ++];if((stack.size() > 0) && (top == stack.getFirst()) ) {stack.pop();} else {for(; pushIdx < pushSeq.length; pushIdx ++) {stack.push(pushSeq[pushIdx]);if(pushSeq[pushIdx] == top) {break;}}if(top == stack.getFirst()) {stack.pop();} else {
//                  Log.log(false);isLeagel = false;break ;}}}Log.log(isLeagel);}}