设计一个支持压入、弹出、取顶部元素和取最小元素的栈，且时间复杂度为常数。

• push(x) – 压入 x 进入栈。
• pop() – 弹出栈顶元素。
• top() – 获取栈顶元素。
• getMin() – 获取栈最小元素。

举例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

我的第一想法是使用一个链表来解决问题，但我看更多人的题解是使用了栈类来做，只可惜我没用过?。这里使用链表就可以轻松解决四个函数中的三个，而最后一个最小值的函数，则借助于链表节点本身来解决，即增加一个变量来保存栈中当前的最小值。

/*
 * 155. Min Stack
 * https://leetcode.com/problems/min-stack/
 * https://www.whosneo.com/155-min-stack/
 */

public class MinStack {
    private Node head = null;

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }

    private void push(int x) {
        Node node = new Node();
        node.value = x;
        if (head == null || x < head.min)
            node.min = x;
        else
            node.min = head.min;
        node.next = head;
        head = node;
    }

    private void pop() {
        if (head != null)
            head = head.next;
    }

    private int top() {
        if (head != null)
            return head.value;
        else
            return 0;
    }

    private int getMin() {
        if (head != null)
            return head.min;
        else
            return 0;
    }

    static class Node {
        int value;
        int min;
        Node next;
    }
}