包含min函數的棧和兩個棧實作一個隊列

題目：定義棧的資料結構，要求添加一個min函數，能夠得到棧的最小元素。要求函數min、push以及pop的時間複雜度都是O(1)。

分析：這是google的一道面試題。

看到這道題目時，第一反應就是每次push一個新元素時，将棧裡所有逆序元素排序。這樣棧頂元素将是最小元素。但由于不能保證最後push進棧的元素最先出棧，這種思路設計的資料結構已經不是一個棧了。在棧裡添加一個成員變量存放最小元素（或最小元素的位置）。每次push一個新元素進棧的時候，如果該元素比目前的最小元素還要小，則更新最小元素。

乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果目前最小元素被pop出去，如何才能得到下一個最小元素？是以僅僅隻添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次push一個新元素的時候，同時将最小元素push到輔助棧中（考慮到元素可能是複雜的資料類型，用位置将能減少空間消耗）；每次pop一個元素出棧的時候，同時pop輔助棧。

參考代碼：

  步驟     資料棧      輔助棧        最小值

1.push 3    3          0             3

2.push 4    3,4        0,0           3

3.push 2    3,4,2      0,0,2         2

4.push 1    3,4,2,1    0,0,2,3       1

5.pop        3,4,2      0,0,2         2

6.pop        3,4        0,0           3

7.push 0   3,4,0      0,0,2         0

另一道題目：用兩個棧實作一個隊列的功能。

要求給出算法和思路！

答：設2個棧為A,B, 一開始均為空.

入隊:

若A有空間，将新元素push入棧A;

若A滿則判斷B是否有元素，有則無法進隊列；若無則将棧A中所有元素依次pop出并push到棧B，将新元素push進A

出隊:

(1)判斷棧B是否為空；

(2)如果不空，則B的棧頂元素出棧；如果為空，則将棧A中所有元素依次pop出并push到棧B；

(3)将棧B的棧頂元素pop出；

兩個棧都是空時隊列為空

這樣實作的隊列入隊和出隊的平攤複雜度都還是O(1)。

<a></a>