【算法】最小棧的實現(getMin)

看書時遇到這樣一道題，挺有趣的數據結構，所以記錄下來

題目:

實現一個棧，該棧帶有出棧(pop)，入棧(push)，取最小元素(getMin)，三個方法。要保證這3個方法的時間復雜度都是O(1)

算法：

1.定義兩個棧，一個棧自定義棧用于入棧、出棧，一個輔助棧用于動態存放自定義棧的最小值

2.入棧操作，當元素壓入 自定義棧 的時候，會判斷輔助棧是否為空，
如果輔助棧為空，或者新元素小于等于輔助棧棧頂，則將新元素壓入(push) 輔助棧。

因為當第一個元素入棧時，這個唯一的元素也就是自定義棧當前最小的值，所以也壓入(push) 輔助棧

3.出棧操作，如果出棧元素和輔助棧棧頂元素值相等，輔助棧出棧(pop)。

代碼如下：

入棧操作

如果輔助棧為空，或者新元素小于等于輔助棧棧頂，則將新元素壓入輔助棧

    /**
     * 入棧操作
     * @param element 入棧的元素 
     */

    public void push(int element){
        mainStack.push(element);
        //如果輔助棧為空，或者新元素小于等于輔助棧棧頂，則將新元素壓入輔助棧
        if(minStack.empty()|| element <= minStack.peek()){
            //empty() 表示的是測試堆棧是否為空。
            //peek() 表示的是查看堆棧頂部的對象，但不從堆棧中移除它。
            minStack.push(element);
        }
    }

出棧操作

如果出棧元素和輔助棧棧頂元素值相等，輔助棧出棧(pop)。

    /**
     * 出棧操作
     */
    public Integer pop(){
        //如果出棧元素和輔助棧棧頂元素值相等，輔助棧出棧
        if(mainStack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        return mainStack.pop();
    }

獲取棧的最小元素(getMin方法)

/**
     * 獲取棧的最小元素
     */
    public int getMin() throws Exception{
        if(mainStack.empty()){
            throw new Exception ("stack is empty");
        }
        return minStack.peek();
    }   

主函數

元素入棧，輸出最小值，元素出棧，再輸出最小值

public static void main(String[] args) throws Exception {
        MinStack stack=new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());

    }

運行結果：
3
4

完整代碼

package min_ini;
import java.util.Stack;
public class MinStack {

    private Stack<Integer> mainStack=new Stack<Integer>();
    private Stack<Integer> minStack=new Stack<Integer>();

    /**
     * 入棧操作
     * @param element 入棧的元素 
     */

    public void push(int element){
        mainStack.push(element);
        //如果輔助棧為空，或者新元素小于等于輔助棧棧頂，則將新元素壓入輔助棧
        if(minStack.empty()|| element <= minStack.peek()){
            //empty() 表示的是測試堆棧是否為空。
            //peek() 表示的是查看堆棧頂部的對象，但不從堆棧中移除它。
            minStack.push(element);
        }
    }

    /**
     * 出棧操作
     */
    public Integer pop(){
        //如果出棧元素和輔助棧棧頂元素值相等，輔助棧出棧
        if(mainStack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        return mainStack.pop();
    }
    /**
     * 獲取棧的最小元素
     */
    public int getMin() throws Exception{
        if(mainStack.empty()){
            throw new Exception ("stack is empty");
        }
        return minStack.peek();
    }   

    public static void main(String[] args) throws Exception {
        MinStack stack=new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());

    }

}