题解 | #设计LRU缓存结构，双栈+hash表#

import java.util.*;


public class Solution {
    //双栈加，hash表
    //st1栈，栈顶是最近使用的，栈底是最久未使用的
    //st2栈，用来中转数据
    //hash表查询数据
    HashMap<Integer , Integer> map = new HashMap<>() ;
    Stack<Integer> st1 = new Stack<>() ;
    Stack<Integer> st2 = new Stack<>() ;
    int MaxSize = 0 ;
    int size = 0 ;
    public Solution(int capacity) {
        this.MaxSize = capacity ;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1 ;
        move(key) ;
        return map.get(key) ;
    }

    public void set(int key, int value) {
        if(map.containsKey(key)) {//已经有，替换，提前
            map.put(key , value) ;
            move(key) ;
        } else {
            if(this.size == this.MaxSize) {//置换,删除栈底的元素
                int last = removeLast() ;
                map.remove((Integer)last) ;
                st1.push(key) ;
                map.put(key , value) ;
            } else {//存储,size++
                map.put(key , value) ;
                this.size ++ ;
                st1.push(key) ;
            }
        }
    }
    //将key移动到栈顶
    public void move(int key) {
        while(!st1.isEmpty()) {
            int cur = st1.pop() ;
            if(cur != key) {
                st2.push(cur) ;
            }
        }
        while(!st2.isEmpty()) {
            st1.push(st2.pop()) ;
        }
        st1.push(key) ;
    }
    //删除栈底,并返回栈底元素
    public int removeLast() {
        int res = 0 ;
        int size = st1.size() ;
        for(int i = 0 ; i < size ; i ++) {
            if(i == size - 1) {
                res = st1.pop() ;
            } else {
                st2.push(st1.pop()) ;
            }
        }
        while(!st2.isEmpty()) {
            st1.push(st2.pop()) ;
        }
        return res ;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */