算法--获取最小元素的栈

package algorithm;

import java.util.Stack;

/**
 * 题目：实现一个特殊的栈，在实现栈的基本功能的基础上，在实现返回栈中的最小元素
 * 思路：使用Stack类
 * 1.创建两个栈，一个用来存储元素：stackData，一个用来储存最小元素：stackMin
 * 2.压入元素时，将元素压入stackData，是否压入stackMin进行判断
 * 如果stackMin为空，压入元素，如果添加的元素比stackMin的最小元素小，压入元素，否则不压入
 * 通过上面的压入规则，保证stackMin的元素从栈底到栈顶是逐渐变小的
 * 3.弹出元素时，将stackData栈顶元素弹出，是否弹出stackMin元素进行判断
 * 如果元素和stackMin的栈顶元素相等则弹出，否则不弹出
 * 4.获取最小元素
 * 由stackMin的压入规则得，stackMin的栈顶元素是最小的直接返回栈顶元素即可
 */

/**
 * 实现类
 */
public class MyStack1 {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public MyStack1() {
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }

    /**
     * 入栈操作
     * @param num 入栈的元素
     */
    public void push(int num) {
        this.stackData.push(num);
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(num);
        } else if (num < this.stackMin.peek()) {
            this.stackMin.push(num);
        }
    }

    /**
     * 出栈操作
     * @return 出栈元素
     */
    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int value = this.stackData.pop();
        if (value == this.stackMin.peek()) {
            this.pop();
        }
        return value;
    }

    /**
     * 获取最小栈最小元素
     * @return 栈的最小元素
     */
    public int getMin() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return this.stackMin.peek();
    }
}

/**
 * 测试类
 */
class Test {
    public static void main(String[] args) {
        MyStack1 myStack1 = new MyStack1();
        myStack1.push(30);
        myStack1.push(40);
        myStack1.push(27);
        myStack1.push(80);
        myStack1.push(16);
        myStack1.push(40);
        System.out.println(myStack1.getMin());
    }
}