天天看點

關于隊列與棧互相模拟的讀書筆記

          棧與隊列都是比較進階的資料結構,雖然不難,但有時有些問題也比較靈活,在《程式設計之美》與《劍指offer》上就有一些這樣的題目。用隊列模拟棧、用站棧模拟隊列,以及現實隊列與棧的最大值與最小值求解,這些都是基礎的,隻要了解棧的後進先出與隊列的先進先出特點即可解決。

1、棧模拟隊列

      用兩個棧,元素從一個棧stackA進入,從另一個棧stackB出來。進隊列時直接添加到stackA,出隊列時若stackA非空,則直接出,否則将stackB中元素全部初戰裝到stackA,然後從stackA出棧。

關于隊列與棧互相模拟的讀書筆記

2、隊列模拟棧

     用兩個隊列,進棧時進入其中一個空的隊列,出棧時将其中一個隊列中的元素進入另外一個空的隊列,最後一個元素不進入直接出隊列模拟出棧。

關于隊列與棧互相模拟的讀書筆記

3、棧的最小值與最大值操作

       以最小值為例,直接開辟個輔助棧儲存即可。上代碼。

4、隊列的最小值與最大值操作

        此處可以用優先級隊列(堆+隊列),此處棧模拟。與棧模拟隊列類比,隻不過這裡的棧要用3中的棧,即包含最小(大)值的棧,其他比較簡單,在此不多說了。

         由于每個元素出入兩個隊列或棧的次數為常數,是以總的時間複雜度與直接用棧或隊列相同,且最值求解的時間複雜度為O(1),是典型的犧牲空間換取時間。

     由于時間有限,欠缺測試,如有錯誤或不足,歡迎斧正!