題目
用一個棧來實現另一個棧的排序
將一個棧從頂到底按從大到小的順序排序, 過程通過一個輔助棧來實現
思路分析
要使棧A從頂到底按照從大到小的順序, 那麼如果棧B中是從頂到底按照從小到大的順序, 這樣將棧B的數據依次彈出並壓入棧A, 就實現了棧A中數據的排序.
那麼如果將棧A中的數據按照從大到小的順序依次壓入棧B呢? 棧B中的數據一定是上邊的要小於等於下邊的, 將棧A中的數據彈出後, 將其插入到棧B適當的位置, 如此即可.
數據壓入棧B的具體規則如下:
- 從棧A中彈出數據num
- 若棧B為空, 則直接入棧
- 若棧B不為空, 將num與棧B的棧頂元素max比較
- 若num <= max, 則num入棧B
- 若num > max, 則將棧B的元素逐一出棧並壓入棧A, 直到num小於或等於棧B的棧頂元素, 此時將num入棧B
經過以上過程, 即可將棧A中的元素按照從小到大的順序依次入棧B, 此時將棧B依次出棧併入棧A即可. Java代碼的簡單實現如下:
分享到:
閱讀更多 牛牛的編程之路 的文章
