Min Stack 155

public class MinStack {
    Stack<Integer> numsk;
    Stack<Integer> minsk;
    public MinStack() { numsk = new Stack<>(); minsk = new Stack<>();}

    public void push(int x) {
        numsk.push(x);
        if (minsk.isEmpty() || minsk.peek() > x) {minsk.push(x);}
        else { minsk.push(minsk.peek()); }
    }

    public void pop() { numsk.pop(); minsk.pop();}

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

    public int getMin() { return minsk.isEmpty() ? -1 : minsk.peek();}
}

LRU Cache 146

public class LRUCache {
    private class Node {
        int k, val;
        Node prev, next;
        Node (int k, int val) {
            this.k = k; this.val = val; this.prev = null; this.next = null;
        }
    }
    int capacity;
    Map<Integer, Node> map;
    Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        // get
        Node current = map.get(key);
        // reconnect
        current.prev.next = current.next;
        current.next.prev = current.prev;
        // move to tail
        movetotail(current);
        return current.val;
    }

    public void put(int key, int value) {
        // use get to check if already exists; if yes, just set value. calling get automatically updates it to tail
        if (get(key) != -1) { 
            map.get(key).val = value;
            return;
        }
        // check map capacity. if full, remove the one at head and reconnect
        if (this.capacity == map.size()) {
            map.remove(head.next.k);
            head.next = head.next.next;
            head.next.prev = head;
        }
        // insert at tail
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        movetotail(newNode);
    }

    private void movetotail(Node node) {
        tail.prev.next = node;
        node.next = tail;
        node.prev = tail.prev;
        tail.prev = node;
    }
}