題目描述

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列 1,2,3,4,5 是某棧的壓入順序，序列 4,5,3,2,1 是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2 就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

解題思路

用棧來壓入彈出元素，相等則出棧。

將數(shù)組 pushA 中的元素依次入棧，在入棧的過程中，若與數(shù)組 popA 中的標記索引處的元素相等，則棧頂元素出棧，且數(shù)組 popA 的標記索引后移。最后，直到數(shù)組 popA 的標記索引到數(shù)組尾端或者棧中的元素為空（全部出棧），則說明數(shù)組 popA 的元素是 pushA 的一個出棧序列。

代碼實現(xiàn)

import java.util.ArrayList; import java.util.Stack;public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {if (null == pushA || null == popA) {return false;}Stack<Integer> stack = new Stack<>();int index = 0;for (int i = 0; i < pushA.length; i++) {stack.push(pushA[i]);while (!stack.isEmpty() && stack.peek() == popA[index]) {stack.pop();index ++;}}return stack.isEmpty();} }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。