定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

最普通的方法

public class MinStack {
    int[] arr;
    int flag;
    public MinStack(){
        arr=new int[100];
        flag=0;
    }
    public void push(int x) {
        if(flag==arr.length){
            int[] brr=new int[arr.length*2];
            for (int i = 0; i <arr.length ; i++) {
                brr[i]=arr[i];
            }
            arr=brr;
        }
        arr[flag++]=x;
    }

    public void pop() {
        flag--;
    }

    public int top() {
        return arr[flag-1];
    }

    public int min() {
        int min=arr[0];
        for (int i = 0; i <flag ; i++) {
            if(min>arr[i]){
                min=arr[i];
            }
        }
        return min;
    }
}

使用辅助栈后

public class MinStack {
   LinkedList<Integer> xStack;
   LinkedList<Integer> minStack;
    public MinStack(){
        xStack=new LinkedList<>();
        minStack=new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(),x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

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

如果在最后进行遍历，一定会极其浪费时间，要求是在调用min时时间复杂度为o(1)。
所以，可以创建两个栈，一个栈是主栈 stackstack，另一个是辅助栈 minStackminStack，用于存放对应主栈不同时期的最小值。
需要注意，弹栈的时候也应将minStack的相应位置一起弹出。

复习LinkedList:
LinkedList的本质是双向链表。它也可以被当作堆栈、队列或双端队列进行操作。它采用的是链表式储存，所以比较适合用来执行插入，删除等功能,减少在列表中插入或删除元素所付出的代价。
一、基本使用
1.添加
boolean add（Object element） 它将元素附加到列表的末尾。
boolean add（int index,Object element） 指定位置插入。
void addFirst(E element) 元素附加到列表的头部
void addLast(Eelement) 元素附加到列表的尾部

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.addFirst(4);
linkedList.addFirst(5);
linkedList.addLast(6);
linkedList.add(2,9);
System.out.println(linkedList);

输出
[5, 4, 9, 1, 2, 3, 6]
2.获取
Object get（int index）获取指定下标元素
Object getFirst（） 它返回链表的第一个元素。
Object getLast（） 它返回链接列表的最后一个元素。

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println("获取下标为1的元素："+linkedList.get(1));
System.out.println("链表的第一个元素："+linkedList.getFirst());
System.out.println("链表的最后一个元素："+linkedList.getLast());

3.查询
boolean contains（Object element）如果元素存在于列表中，则返回true。

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(1);
System.out.println("是否出现过元素1："+linkedList.contains(1));
System.out.println("是否出现过元素4:"+linkedList.contains(4));

输出
是否出现过元素1：true
是否出现过元素4:false
4.修改
Object set（int index，Object element）它用于用新元素替换列表中的现有元素

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(1);
linkedList.set(1,9);
System.out.println("更新过的链表："+linkedList);

输出
更新过的链表：[1, 9, 3, 1]
5.删除
E remove() 删除第一个元素
E remove(int location) 删除指定位置的元素
E removeFirst() 删除并返回链接列表的头部一个元素
E removeLast() 删除并返回链接列表的尾部一个元素

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(1);
linkedList.remove(); //删除第一个元素
linkedList.remove(2);//删除指定位置的元素
System.out.println(linkedList);

6. 清空
   void clear（）：它删除列表中的所有元素。

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(1);
linkedList.clear();
System.out.println(linkedList);

输出
[]
7.链表长度

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(1);
System.out.println("链表的长度："+linkedList.size());

输出
链表的长度：4

如果你将其作为栈使用，那么他也可以直接调用push(),peek(),pop()等方法