題目：定義棧的資料結構，要求添加一個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)。
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
http://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622673.html