题解 | #设计LRU缓存结构#

#include <deque>
class Solution {
public:
    Solution(int capacity){
         // write code here
        maxsize = capacity;
        cursize = 0;
    }
    
    int get(int key) {
        // write code here
        int res = -1;
        for(auto beg = q.begin();beg != q.end();++beg)
        {
            if(beg->first == key)
            {
                res = beg->second;
                q.erase(beg);
                q.push_front({key,res});
                break;
            }
        }
        return res;
    }
    
    void set(int key, int value){
         // write code here
        if(cursize >= maxsize)
        {
            q.pop_back();
            cursize--;
        }        
        q.push_front({key,value});
        cursize++;
    }
private:
    int maxsize;
    int cursize;
    deque<pair<int,int>> q;
};

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

解题思路：使用双端队列