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

考查对栈的理解，入栈，出栈操作，解题思路。

题：

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

解：

解一：

package interview.q1;

import java.util.Random;
import java.util.Stack;

/**
 * 栈：一种线型数据结构，先进后出，后进先出。可以看做只有一个开口的圆桶容器。
 * 问：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
 * 思路一：使用两个栈，一个完成数据的出栈入栈操作，另一个辅助栈存储每次操作之后得到的最小值。
 */
public class Demo1 {

    Stack stack1 = new Stack();
    Stack stack2 = new Stack();

    int min = 0;

    /**
     * 入栈
     */
    public void push(int node) {
        stack1.push(node);
        //只有一个元素时
        if (stack1.size() == 1) {
            min = (int) stack1.peek();
        } else {
            //每加入一个元素，都需要将其与最小值比较，判断此次操作后的最小值
            if (min > node) {
                min = node;
            }
        }
        //栈顶一直维持最小,加入
        stack2.push(min);
    }

    /**
     * 出栈
     */
    public void pop() {
        //如果出栈的元素大于min,那么stack2的栈顶元素与倒数第二个是相同的，所以删掉一个后，最小值仍然是栈顶元素
        stack1.pop();
        //无论栈顶元素与min是否相等，都需要向下移动一个，要保证辅助栈stack2中值与操作的一致                                       性
        stack2.pop();
        min = (int) stack2.peek();
    }

    /**
     * 栈顶
     *
     * @return
     */
    public int top() {
        return (int) stack1.peek();
    }

    /**
     * 最小
     *
     * @return
     */
    public int min() {
        return min;
    }

    public static void main(String[] args) {
        Demo1 demo1 = new Demo1();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            int anInt = random.nextInt(100);
            demo1.push(anInt);
        }
        System.out.println(demo1.min());

        for (int i = 0; i < 10; i++) {
            demo1.pop();
        }
        System.out.println(demo1.min());
    }
}

解二：

package interview.q1;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * 栈：一种线型数据结构，先进后出，后进先出。可以看做只有一个开口的圆桶容器。
 * 问：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
 * 思路二：原理同方法一，只是数据操作的栈是自定义栈，通过数组扩容完成
 */
public class Demo2 {

    private Integer[] elements = new Integer[10];
    private int size = 0;
    private int min = 0;

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

    /**
     * 入栈
     *
     * @param node
     */
    public void push(int node) {
        //确保可以再添加一个元素,如果不够就扩容
        ensureCapacity(size + 1);
        //添加元数,数组元素个数为size
        elements[size++] = node;
        if (size == 1) {
            min = node;
        } else {
            if (node < min) {
                min = node;
            }
        }
        minStack.push(min);
    }

    /**
     * 数组扩容
     *
     * @param size
     */
    public void ensureCapacity(int size) {
        int len = elements.length;
        if (size > len) {
            int newLen = len * 2;
            elements = Arrays.copyOf(elements, newLen);
        }
    }

    /**
     * 出栈
     */
    public void pop() {
        if (size >= 1) {
            elements[size - 1] = null;
            //此处需要注意，int[]数组元素不能设置为null,即使是（Integer）null，也会报空指针异常
            //因此使用 Integer[] 数组
        }
        size--;
        minStack.pop();
        min = minStack.peek();
    }

    /**
     * 栈顶
     *
     * @return
     */
    public int top() {
        if (size >= 1) {
            return elements[size - 1];
        }
        return Integer.parseInt(null);
    }

    /**
     * 最小
     *
     * @return
     */
    public int min() {
        return min;
    }

    public static void main(String[] args) {
        Demo2 demo1 = new Demo2();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            int anInt = random.nextInt(100);
            demo1.push(anInt);
        }
        System.out.println(demo1.min());

        for (int i = 0; i < 10; i++) {
            demo1.pop();
        }
        System.out.println(demo1.min());
    }
}