由兩個棧組成的隊列
【題目】
編寫一個類,用兩個棧實現隊列,支持隊列的基本操作(add,poll, peek)。
【解答】
棧的特點是先進後出,而隊列的特點是先進先出。我們用兩個棧正好能把順序反過來實現類似隊列的操作。
具體實現上是一個棧作為壓入棧,在壓入數據時只往這個棧中壓入,記為 stack Push;另一個棧只作為彈出棧,在彈出數據時只從這個棧彈出,記為 stackpop.
因為數據壓入棧的時候,順序是先進後出的。那麼只要把stack Push的數據再壓入 stack Pop中,順序就變回來了。例如,將1~5依次壓入 stack Push,那麼從 stack Push的棧頂到棧底為5~1,此時依次再將5~1倒入 stackpop,那麼從 stackpop的棧頂到棧底就變成了1~5。再從 stack Pop彈出時,順序就像隊列一樣,如圖1-3所示。
聽起來雖然簡單,實際上必須做到以下兩點。
1.如果 stack Push要往 Estack Pop中壓入數據,那麼必須一次性把stackPush中的數據全部壓入。
2.如果 stack Pop.不為空, stack Push絕對不能向 stack Pop中壓入數據。
違反了以上兩點都會發生錯誤
違反1的情況舉例:1~5依次壓入 stack Push, stack Push的棧頂到棧底為5~1,從 stack Push壓入 stack Pop時,只將5和4壓入了tack Pop, stack Push還剩下1、2、3沒有壓入。此時如果用戶想進行彈出操作,那麼4將最先彈出,與預想的隊列順序就不一致。
違反2的情況舉例:1~5依次壓入 stack Push, stack Push將所有的數據壓入了 stack Pop,此時從 stack Pop的棧頂到棧底就變成了1~5此時又有6~10依次壓入 stack Push, stackpop不為空, stack Push不能向其中壓入數據。如果違反2壓入了 stackpop,從 stack Pop的棧頂到棧底就變成了6~10、1~5。那麼此時如果用戶想進行彈出操作6將最先彈出,與預想的隊列順序就不一致。
上面介紹了壓入數據的注意事項。那麼這個壓入數據的操作在何時發生呢?
這個選擇的時機可以有很多,調用add、poll和peek三種方法中的任何一種時發生“壓”入數據的行為都是可以的。只要滿足如上提到的兩點,就不會出錯。
本書的實現是在調用poll和peek方法時進行壓入數據的過程。
具體實現請參看如下的 Twostacksqueue類：
閱讀更多 CSDN學院 的文章
