一、問題描述

給定兩個(gè)數(shù)組，一個(gè)進(jìn)棧順序，一個(gè)出棧順序。判定出棧數(shù)組的出棧順序是不是有可能的。

二、Code

1 package algorithm; 2 3 import java.util.ArrayDeque; 4 import java.util.Deque; 5 6 /** 7 * Created by adrian.wu on 2019/5/30. 8 */ 9 public class StackPopOrderJudge { 10 /* 11 思路： 12 1、整體思路用一個(gè)輔助棧還原入棧元素的順序，并比較兩者是否一致 13 2、如果第一個(gè)出棧元素并非最后一個(gè)入棧元素，則這個(gè)出戰(zhàn)元素之前的元素不可能先于它出棧，因此把這個(gè)元素即之前的元素都?jí)喝霔?14 3、上述步驟之后，如果出棧元素并非入棧棧頂元素，則其是先pop出去了，因此直接壓人輔助棧 15 4、重復(fù)上述步驟，并比較輔助棧和壓入棧的元素，遇到相同則pop 16 5、觀察最后入棧元素和輔助棧是否都為空，為空則正確，不為空則False 17 */ 18 19 public static boolean isPopOrder(int[] in, int[] out) { 20 int n = out.length; 21 int nextPop = 0, nextPush = 0; 22 Deque<Integer> deque = new ArrayDeque<>(); 23 24 25 while (nextPop != n) { 26 while (deque.isEmpty() || deque.peek() != out[nextPop]) { 27 if (nextPush == n) break; 28 deque.push(in[nextPush++]); 29 } 30 31 if (!deque.isEmpty() && deque.peek() != out[nextPop++]) break; 32 deque.pop(); 33 } 34 return nextPop == n && deque.isEmpty(); 35 } 36 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ylxn/p/10954150.html

總結(jié)

以上是生活随笔為你收集整理的(24) 不可能的出栈顺序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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