劍指offer：棧的壓入、彈出序列（Java）

Zhuxy 發布于2019-08-19 10:11 / 3557人閱讀

摘要：題目描述輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。指向壓棧序列的指針指向彈棧序列的指針儲存壓棧序列的輔助空間第一次遍歷把壓棧序列放入輔助空間中如果有相等的就讓彈棧序列指針。

1.題目描述

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

2.思路

首先要理解為什么棧的壓入順序一定的情況下卻可以有不同的彈出順序，就是在棧的壓入過程中可以向外彈元素，不一定是全部元素進棧才開始向外彈棧，所以會產生不同的彈棧順序。
1.題目給的是ArrayList，使用這個作為輔助空間
然后就是借助一個輔助空間，將壓棧的序列儲存起來，儲存過程中判斷是否和彈棧序列一致，如果一致就讓彈棧序列指向后一位，等壓棧序列全部進輔助空間后，在開始反向遍歷一次，因為題目說明沒有重復元素，所以進輔助空間過程中判斷過的元素可以重復判斷，不會出錯，遍歷過程中判斷是否和彈棧序列元素相等，相等就彈棧序列指向后一位，并且輔助空間也指向下一個元素，不相等就只讓輔助空間指向下一個元素，這樣反向遍歷完輔助空間后如果彈棧序列沒有走到最后，就說明不是正確的彈棧序列，如果走到了最后就是正確序列。

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        int i = 0;    //指向壓棧序列的指針
        int j = 0;    //指向彈棧序列的指針
        ArrayList helpList = new ArrayList<>();    //儲存壓棧序列的輔助空間
        while(i < pushA.length){    //第一次遍歷把壓棧序列放入輔助空間中
            helpList.add(pushA[i]);    
            if(helpList.get(i) ==  popA[j]){    //如果有相等的就讓彈棧序列指針++。
                j++;
            }
            i++;
        }
        i = i-1;    //這里是細節，最后i=pushA.length所以要-1.
        while(i>= 0 && j < popA.length){    //i>=0也是細節，如果只是大于0，0位置的元素就沒辦法判斷了。
            if(helpList.get(i)== popA[j]){    
                i--;
                j++;
            }else{
                i--;
            }
        }
        return j == popA.length ? true:false;    //根據彈棧序列的指針是否走到最后判斷是不是彈棧序列。
    }
}

2：使用Stack

使用棧結構的好處就是可以省去上面方法過程中的重復判斷，因為可以判斷到一個相等就直接彈出。

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack temp = new Stack<>();
        int popIndex = 0;
        for(int i = 0 ; i < pushA.length; i++){
            temp.push(pushA[i]);
            while(!temp.isEmpty() && temp.peek() == popA[popIndex]){
                temp.pop();
                popIndex++;
            }
        }
        return temp.isEmpty();
    }
}

方法2參考：Alias

云服務器 GPU云服務器棧的java描述 java 棧的應用 java棧的深度 java棧的源代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75592.html

【劍指offer】讓抽象問題具體化

摘要：假設壓入棧的所有數字均不相等。注意這兩個序列的長度是相等的思路借助一個輔助棧來存儲數據。當所有數據入棧完成，如果出棧順序正確，那么輔助棧應該為空。若存在，左右子樹，遞歸檢測左右子樹是否復合規范。 1.包含min函數的棧定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））。思路 1.定義兩個棧，一個棧用于存儲數據，另一個棧用于存儲每次數...

Keagan 2019-08-23 15:15 評論0 收藏0
【刷算法】棧的壓入、彈出序列

摘要：題目描述輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。題目描述輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的...

CarlBenjamin 2019-08-22 18:17 評論0 收藏0
2019秋招知識盲點總結

摘要：實際上是一個讓出線程的標志遇到會立即返回一個狀態的。一個簡單的防抖函數如果定時器存在則清除重新開始定時執行缺點只能在最后執行，不能立即被執行，在某些情況下不適用。假設壓入棧的所有數字均不相等。接收數據不受同源政策限制。開始盡管秋招還沒有拿到offer（好難過），但是一些知識點還是要總結的，既然自己選了這條路，那就一定要堅定不移的走下去...... 注意 new 運算符的優先級 fu...

Doyle 2019-08-23 11:52 評論0 收藏0
劍指offer/LintCode494_用兩個隊列實現一個棧

摘要：劍指用兩個隊列實現一個棧聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能用兩個隊列實現一個棧，實現，，和方法解題思路假設有隊列和實現棧的操作實現棧操作始終用來入隊實現實現棧的方法模擬棧的過程中，保證兩個隊列中始終有一個隊列為空，另一劍指offer/LintCode494_用兩個隊列實現一個棧聲明文章均為本人技術筆記，轉載請注明出處https://segmentfault....

rose 2019-08-14 18:10 評論0 收藏0
Java數據結構與算法[原創]——棧

摘要：前言數據結構與算法專題會不定時更新，歡迎各位讀者監督。方法調用編寫的程序在進行方法函數調用時，會完成對方法的壓棧操作，等方法執行結束后，對應的會完成對方法的彈棧操作。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文介紹數據結構中的棧的概念、存儲結構、棧的特點以及棧的適用場景，另外會穿插介紹面試中的一些經典問題...

hiyang 2019-08-19 10:42 評論0 收藏0