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

示例 1：? 輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

????????????????輸出：true

????????????????解釋：我們可以按以下順序執(zhí)行：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?push(1), push(2), push(3), push(4), pop() -> 4,? push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：? 輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

????????????????輸出：false

????????????????解釋：1 不能在 2 之前彈出。

解題思路：判斷合不合法，用個(gè)棧試一試: 把壓棧的元素按順序壓入，當(dāng)棧頂元素和出棧的第一個(gè)元素相同，則將該元素彈出，出棧列表指針后移并繼續(xù)判斷。最后判斷出棧列表指針是否指向出棧列表的末尾即可。

?public?boolean?validateStackSequences(int[]?pushed,?int[]?popped)?{

????????Deque<Integer>?deque?=?new?ArrayDeque<>();? //初始化一個(gè)棧

????????int?tan?=?0; //出棧列表指針

????????for(int?node?:?pushed)?{

????????????deque.push(node); // 把壓棧的元素按順序壓入

????????????while(?!deque.isEmpty()?&&?deque.peek()?==?popped[tan])?{ // 當(dāng)棧頂元素和出棧的第一個(gè)元素相同

????????????????deque.pop(); // 則將該元素彈出

????????????????tan++; // 出棧列表指針后移

????????????}

????????}

????????return?tan?==?popped.length; // 判斷出棧列表指針是否指向出棧列表的末尾

????}