實作棧，擷取棧中最小值

• 空間換時間
• • 基本思想
  • 代碼
  • • 複雜度分析
  • 時間換空間
  • 基本思想
  • 代碼
  • • 複雜度分析

兩種方式實作，第一種用空間換時間，第二種用時間換空間

空間換時間

基本思想

• 用兩個棧來實作，一個棧維護入棧資料（資料棧），一個棧維護最小值（最小棧）
• 元素入棧時，比較入棧元素與最小棧棧頂
  • 如果最小棧棧頂元素更小，那麼再次将該最小棧棧頂元素壓入最小棧
  • 如果入棧元素更小，那麼将入棧的元素同步壓入最小棧
• 元素出棧時，資料棧與最小棧同步出棧即可，最小棧彈出元素即為目前棧中最小值

代碼

import java.util.Stack;

/**
 * 實作棧，并且可以擷取棧中的最小值
 *
 * 解決：兩個棧 -> 棧1維護所有資料，棧2維護最小值
 */
public class MinStack {

    public static class MyStack{
        //初始化定義兩個棧
        public Stack<Integer> dataStack;
        public Stack<Integer> minStack;

        public MyStack(){
            dataStack = new Stack<>();
            minStack = new Stack<>();
        }

        //入棧
        public void push(int value){
            //判斷最小棧的處理
            //若最小棧為空或最小棧棧頂值大于傳入值，則放入
            if (minStack.isEmpty() || minStack.peek() > value){
                minStack.push(value);
            } else {
                //否則，再次在最小棧放入最小棧棧頂元素
                minStack.push(minStack.peek());
            }
            //資料棧放入值
            dataStack.push(value);
        }

        //出棧
        public int pop(){
            //判空
            if (dataStack.isEmpty()){
                System.out.println("棧空");
                return -1;
            }

            //彈出最小棧棧頂，傳回資料棧棧頂
            minStack.pop();
            System.out.println(dataStack.peek());
            return dataStack.pop();
        }

        public int getMin(){
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(5);
        System.out.println(myStack.getMin()); // 5 5
        myStack.push(2);
        System.out.println(myStack.getMin()); // 2 2
        myStack.push(3);
        System.out.println(myStack.getMin()); // 3 2
        myStack.push(1);
        System.out.println(myStack.getMin()); // 1 1
        myStack.pop();
        System.out.println(myStack.getMin()); // 3 2
    }
}
           

複雜度分析

所謂空間換時間，
就是元素每次進棧時，最小棧同步會壓入，占用了和資料棧同等大小的空間
但擷取棧中的最小值時，隻需要擷取最小棧棧頂元素即可，節省了時間
           

時間換空間

基本思想

• 同樣定義資料棧和最小棧
• 元素入棧時，比較入棧元素與最小棧棧頂
  • 如果入棧元素>最小棧棧頂元素，則最小棧不壓入
  • 如果入棧元素<=最小棧棧頂元素，則最小棧同步壓入
• 元素出棧時
  • 隻有資料棧棧頂元素與最小棧棧頂元素相等時，才會同步彈出
  • 這樣才可以保證最小棧棧頂元素始終為棧的最小值

代碼

import java.util.Stack;

/**
 * 實作棧，并且可以擷取棧中的最小值
 *
 * 解決：兩個棧 -> 棧1維護所有資料，棧2維護最小值
 *      入棧時：棧2隻有在其棧頂元素≤目前值時才入棧
 *      出棧時：棧2隻有棧頂元素 = 資料棧棧頂元素時才出棧
 */
public class MinStack2 {

    public static class MyStack{
        //初始化定義兩個棧
        public Stack<Integer> dataStack;
        public Stack<Integer> minStack;

        public MyStack(){
            dataStack = new Stack<>();
            minStack = new Stack<>();
        }

        //入棧
        public void push(int value){
            //判斷最小棧的處理
            //若最小棧為空或傳入值≤最小棧棧頂值，則放入
            if (minStack.isEmpty() || value <= minStack.peek()){
                minStack.push(value);
            }
            //資料棧放入值
            dataStack.push(value);
        }

        //出棧
        public int pop(){
            //判空
            if (dataStack.isEmpty()){
                System.out.println("棧空");
                return -1;
            }

            //若資料棧棧頂=最小棧棧頂，彈出最小棧棧頂，傳回資料棧棧頂
            if (dataStack.peek() == minStack.peek()){
                minStack.pop();
            }
            System.out.println(dataStack.peek());
            return dataStack.pop();
        }

        public int getMin(){
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(5);
        System.out.println(myStack.getMin()); // 5 5
        myStack.push(2);
        System.out.println(myStack.getMin()); // 2 2
        myStack.push(3);
        System.out.println(myStack.getMin()); // 3 2
        myStack.push(1);
        System.out.println(myStack.getMin()); // 1 1
        myStack.pop();
        System.out.println(myStack.getMin()); // 3 2
    }
}
           

複雜度分析

所謂時間換空間，
就是元素每次進棧時，最小棧不會同步會壓入，隻有<=最小棧棧頂元素時才會壓入，最小棧占用空間會小
但擷取棧中的最小值時，需要判斷資料棧棧頂元素與最小棧棧頂元素是否相等，相等時才會彈出，因為增加了邏輯判斷，是以會比方法一占用更多的時間