【刷算法】棧的壓入、彈出序列

CarlBenjamin 發布于2019-08-22 18:17 / 1355人閱讀

摘要：題目描述輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。

題目描述

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

分析

其實該題就是考察一個進棧序列能否和一個出棧序列對應起來，但是棘手的地方在于：一個進棧序列可能會有多個出棧的順序，所以還是得好好想一想。

可以從一個簡單的例子開始：

序列A：1,2,3

序列B：2,3,1

1先進棧，B序列中未出棧的第一個數字是2，說明此時1不能再接著出棧；

2再進棧，B序列中未出棧的第一個數字是2，說明第一個出棧的數字是2，那么2就此出棧；

此時棧頂元素為1，B序列中未出棧的第一個數字是1，說明1是自2出棧后的再一個出棧元素，那么1就此出棧，此時棧為空；

3繼續進棧，此時B序列的中未出棧的第一個數字是3，說明3是再一個出棧元素，那么3就此出棧，此時棧為空，序列A也全都進棧完畢了；

棧空了，序列A也進棧完畢了，說明B就是A的彈出序列。

代碼實現

接著這個思路，可以試著寫代碼了

function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length === 0 || pushV.length !== popV.length)
        return false;
    // 進棧序列和出棧序列分別有一個指針，從頭開始
    var curPushIndex = 0, curPopIndex = 0;
    var stack = [];
    
    for(;curPushIndex < pushV.length;curPushIndex++) {
        
        stack.push(pushV[curPushIndex]);
        while(curPopIndex < popV.length && stack[stack.length-1] === popV[curPopIndex]){
        // 棧頂元素和當前popIndex指向的數字一樣的話，stack彈出棧頂元素，且當前popIndex指向pop序列的下一個數字
            stack.pop();
            curPopIndex++;
        }
    }
    // 棧中元素沒有全部彈出，說明兩個序列并不匹配，否則，就是匹配
    return stack.length === 0;
}

GPU云服務器云服務器最大功序列算法 php 壓入 web服務器的壓測全棧的

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

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

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

摘要：題目描述輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。指向壓棧序列的指針指向彈棧序列的指針儲存壓棧序列的輔助空間第一次遍歷把壓棧序列放入輔助空間中如果有相等的就讓彈棧序列指針。 1.題目描述輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓...

Zhuxy 2019-08-19 10:11 評論0 收藏0
【劍指offer】讓抽象問題具體化

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

Keagan 2019-08-23 15:15 評論0 收藏0
Java數據結構與算法[原創]——棧

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

hiyang 2019-08-19 10:42 評論0 收藏0
棧的實現原理

摘要：使用棧實現字符串逆序將字符串反轉用兩個棧實現隊列用兩個棧來實現一個隊列，完成隊列的和操作。假設棧中有個元素，基于簡單數組實現的棧。可以看到棧是實現，其實底層也是用數組來實現的。移除此堆棧頂部的對象，并將該對象作為此函數的值返回。目錄介紹 01.棧由簡單數據實現 1.1 簡單數組代碼實現 1.2 可能出現問題 1.3 性能和局限性 02.棧由動態數組實現 2.1 基于簡單...

soasme 2019-08-19 11:35 評論0 收藏0
2019秋招知識盲點總結

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

Doyle 2019-08-23 11:52 評論0 收藏0