题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

解题思路

1，两个栈，一个完成基本功能，一个充当辅助栈
2，辅助栈内最小值总是上浮到栈顶

代码实现

/** * */
package 栈和队列;

import java.util.Stack;

/** * <p> * Title:MinStack * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月22日 上午10:40:43 */
public class MinStack {
    Stack<Integer> stack1 = new Stack<Integer>(); // 主栈
    Stack<Integer> stack2 = new Stack<Integer>(); // 辅助栈，栈顶即为最小值
    int min = Integer.MAX_VALUE;

    public void push(int node) {
        stack1.push(node);
        if (min > node) {
            stack2.push(node);
            min = node;
        } else {
            stack2.push(min);     //栈2的顶永远存放当前的最小值
        }

    }

    public void pop() {
        if (!stack1.isEmpty() && !stack2.isEmpty()) {
            stack1.pop();
            stack2.pop();
        }

    }

    public int top() {
        return stack1.peek();

    }

    public int min() {
        return stack2.peek();

    }

    public static void main(String[] args) {

    }
}