[TOC] # 棧簡介 棧是一個先入后出的集合 # 問題 **實現一個棧,讓這個棧帶有出棧(pop),入棧(push),查找最小元素(getMin)這3個方法,并且要保證這3個方法的時間復雜度都是0(1)** # 解題(錯誤版本) 先創建一個整形變量,存儲棧中最小元素的位置,每次新元素接近棧的時候,讓新元素和當前最小元素比較... 大致意思 1. 創建一個整型變量 min，初始值-1 2. 當第一個元素進棧時，讓min=0，即把唯一的元素當做最小值。 3. 之后每當一個新元素近棧，讓新元素和min指向位置的元素比較大小。如果Stack[min]大于新元素，則min等于新元素的下標；Stack[min]小于新元素，則不做改變。 4. 當調用getMin方法的時候，直接返回min所指向位置的元素即可。 示意圖  按這個思路，近棧、出棧、取最小值的時間復雜度都是O(1)，空間復雜度也是O(1) # 錯誤點 這個思路,在時間復雜度和空間復雜度都是最優的! 那么哪里有問題呢? 問題在于 在進棧的時候,這樣是沒有什么問題的,可以當出棧的時候,一旦最小元素出棧了,誰來頂替他呢?  也就是說,僅僅用一個下標變量來做記錄是不夠的,因為一旦這個小標的元素出棧,就沒有了"備胎" # 正確解法 可以用一個額外的棧來存儲所有曾經的最小值,也就是"備胎"們.當真正的最小值出棧時,讓"備胎"們頂上去 思路: 1. 設原有的棧叫做棧A，此時創建一個額外的棧B，用于輔助原棧A。 2. 當第一個元素進入棧A的時候，讓新元素的下標進入棧B。這個唯一的元素是棧A的當前最小值。（考慮到棧中元素可能不是類對象，所以B棧存儲的是A棧元素的下標） 3. 每當新元素進入棧A時，比較新元素和棧A當前最小值的大小，如果小于棧A當前最小值，則讓新元素的下標進入棧B，此時棧B的棧頂元素就是棧A當前最小值的下標。 4. 每當棧A有元素出棧時，如果出棧元素是棧A當前最小值，則讓棧B的棧頂元素也出棧。此時棧B余下的棧頂元素所指向的，是棧A當中原本第二小的元素，代替剛才的出棧元素成為了棧A的當前最小值。（備胎轉正） 5. 當調用getMin方法的時候，直接返回棧B的棧頂所指向的棧A對應元素即可。 圖解  這個解法中近棧、出棧、取最小值的時間復雜度都是O(1)，最壞情況空間復雜度是O(N)。 這個才是最小棧的真正解法,同時,從這道題算法題真中可以引申出更有意思的題目 # 擴展題目 實現一個隊列，帶有出隊（deQueue），入隊（enQueue），取最小元素（getMin）三個方法。要保證這三個方法的時間復雜度都盡可能小。