最近最少使用队列算法

定义：

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法就是将最近最久未使用的页面予以淘汰。

可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时，便将该页面号压入栈顶，其他的页面号往栈底移，如果内存不够，则将栈底的页面号移除。这样，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未访问的页面的页面号。

import java.util.HashSet;
import java.util.Set;

public class LRU2<E> {

    private Node<E> head;

    private Node<E> tail;

    private int maxcapacity = 3;

    private int count = 0;

    private final Set<E> valueSet = new HashSet<E>();

    LRU2(int maxcapacity){
        this.maxcapacity = maxcapacity;
    }

    LRU2(){
    }

    public boolean add(E e) {
        Node newNode = new Node(e);
        if(count == 0) {
            this.head = newNode;
            this.tail = newNode;
            valueSet.add(e);
            count++;
            return true;
        }

        if(valueSet.contains(e)) {
            if(count == 1) {
                return false;
            }else if(e == head.value) {
                head.next.before = null;
                head = head.next;
                tail.next = newNode;
                newNode.before = tail;
                tail = newNode;
                return false;
            }else if( e == tail.value) {
                return false;
            }else {
                Node temp = head.next;
                while(temp != null) {
                    if(e == temp.value) {
                        Node b = temp.before;
                        b.next = temp.next;
                        temp.next.before = temp.before;
                        temp.next = null;
                        tail.next = temp;
                        temp.before = tail;
                        tail = temp;
                        return false;
                    }else {
                        temp = temp.next;
                    }
                }
            }
        }else {
            tail.next = newNode;
            newNode.before = tail;
            tail = newNode;
            count++;
            valueSet.add(e);
            if(count > maxcapacity) {
                E v = head.value;
                Node h = head.next;
                h.before = null;
                head = h;
                count--;
                valueSet.remove(v);
            }
            return true;
        }

        return false;
    }

    class Node<E> {
        Node<E> before ;
        Node<E> next ;
        E value;

        Node(E e){
            this.value = e;
        }

    }


    public void printNodes() {
        Node temp = head;
        while(null != temp) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LRU2<Integer> l = new LRU2<Integer>(4);
        l.add(1);
        l.printNodes();
        l.add(2);
        l.printNodes();
        l.add(3);
        l.printNodes();
        l.add(3);
        l.printNodes();
        l.add(4);
        l.printNodes();
        l.add(3);
        l.printNodes();
        l.add(5);
        l.printNodes();
    }
}