題目描述

　　輸入兩個整數序列，第一個序列表示棧的壓入書序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相同。例如1、2、3、4、5是某棧的壓入序列，序列5、4、3、2、1是該棧對應的一個彈出序列，但4、3、5、1、2就不可能是該壓棧序列的彈出序列。

基本思路

　　設置兩個索引pushIndex和popIndex，分別用于記錄入棧元素的處理位置和出棧元素的處理位置，設置一個循環，當入棧元素還未全部入棧的條件下，如果棧為空，或者棧頂的元素不與當前處理的元素相等，則一直進行入棧操作，直到入棧元素全部入?；蛘哒业揭粋€與棧頂元素相等的元素。如果在上一步入棧過程中找到了與出棧與出棧元素相等的元素。將元素出棧，處理下一個元素。如果沒有找到與出棧元素相等的元素，說明這個出棧順序是不合法的，就返回false。

Java代碼

package com.swordOffer.stackPushPopOrder14;import java.util.Scanner; import java.util.Stack;/*** Created by Feng on 2017/5/11.* 輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。* 假設壓入棧的所有數字均不相等。例如列1、2、3、4、5是某棧的壓棧序列，序列5、4、3、2、1* 是該棧對應的一個彈出序列，但4、3、5、1、2就不可能是該壓棧序列的彈出序列。*/ public class StackPushPopOrder {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();//數組的大小int[] push = new int[n];//表示棧的壓入順序for (int i = 0; i < n; i++) {push[i] = sc.nextInt();}int[] pop = new int[n];//彈出順序for (int i = 0; i < n; i++) {pop[i] = sc.nextInt();}boolean result = isPopOrder(push, pop);System.out.println(result);}}/*** 判斷第二個序列是否為該棧的探春序列** @param push* @param pop* @return*/private static boolean isPopOrder(int[] push, int[] pop) {boolean flag = false;Stack<Integer> stack = new Stack<>();// 輸入校驗，參數不能為空，并且兩個數組中必須有數字，并且兩個數組中的數字個數相同// 否則返回falseif (push == null || pop == null || pop.length == 0 || push.length == 0|| push.length != pop.length) {return false;}// 用于記錄入棧數組元素的處理位置int pushIndex = 0;// 用于記錄出棧數組元素的處理位置int popIndex = 0;// 如果還有出棧元素要處理while (popIndex < pop.length) {// 入棧元素還未全部入棧的條件下，如果棧為空，// 或者棧頂的元素不與當前處理的相等，// 則一直進行棧操作，// 直到入棧元素全部入?；蛘哒业搅艘粋€與當出棧元素相等的元素while (pushIndex < push.length && (stack.isEmpty() ||stack.peek() != pop[popIndex])) {// 入棧數組中的元素入棧 stack.push(push[pushIndex]);// 指向下一個要處理的入棧元素pushIndex++;}//如果在上一步的入棧過程中找到了與出棧的元素相等的元素if (stack.peek() == pop[popIndex]) {// 將元素出棧 stack.pop();// 處理下一個出棧元素popIndex++;}// 如果沒有找到與出棧元素相等的元素，說明這個出棧順序是不合法的// 就返回falseelse {return false;}}return true;} }

?

轉載于:https://www.cnblogs.com/lfeng1205/p/6840265.html

總結

以上是生活随笔為你收集整理的剑指Offer之栈的压入、弹出序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。