php實作堆疊的壓入以及彈出序列

這篇文章主要介紹了關於php實現堆疊的壓入以及彈出序列，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

題目描述

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

---

• 解題思路

---

• 
  

#傳入入棧序列，和出棧序列，我們使用堆疊作為輔助棧，遍歷將入棧序列壓入輔助棧，如果遍歷時輔助棧不為空，且棧頂元素等於目前出棧元素，則彈出輔助棧元素。遍歷結束後如果輔助堆疊為空則說明第二個序列是該堆疊的彈出順序

• #程式碼如下##<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false;">&lt;?php function isPopOrder($pushValue, $popValue){ $stack = new SplStack; $count = count($pushValue); for ($i = 0, $j = 0; $i &lt; $count; $i++) { $stack-&gt;push($pushValue[$i]); while (!$stack-&gt;isEmpty() &amp;&amp; $stack-&gt;top() == $popValue[$j] &amp;&amp; $j &lt; $count) { $stack-&gt;pop(); $j++; } } return $stack-&gt;isEmpty(); } var_dump(isPopOrder([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]));</pre><div class="contentsignin">登入後複製</div></div>

  實例解說

• 進棧序列為
1，2，3，4，5
• 出棧序列為 

  4，5，3，2，1第一次遍歷，明顯1 不等於4 繼續遍歷，遍歷4 次到輔助堆疊站的棧內元素為1，2，3，4

    棧頂元素為
4
• 時

  #把輔助棧棧頂元素彈出，將待出棧元素變成5

• 這時輔助棧的棧內元素為1 ，2，3

  棧頂元素為
3
• ，很明顯

  3不等於待出堆疊元素5 ，我們繼續遍歷把5

  壓入輔助堆疊

• 剛好這時待出棧元素為5 與棧頂元素相同，於是我們彈出棧頂元素，待出棧元素變成3

• 再繼續，棧頂元素此時為
3
• 與待出堆疊元素相同，彈出堆疊頂元素

• 此時棧頂元素變成

  2

  ，待出堆疊元素變成
2
，繼續彈出堆疊頂元素

#此時堆疊頂部元素變成1

，待出堆疊元素變成

1### ，彈出堆疊頂部元素########## ##由於輔助堆疊此時為空跳出while############由於此時入棧元素以全部進入輔助堆疊跳出for###########輔助堆疊最終為空，程式結束############相關推薦：#########ThinkPHP實作附件上傳功能#########

以上是php實作堆疊的壓入以及彈出序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！