[Java] 固定队列的实现思路

原创作品，转载请注明出处：http://blog.csdn.net/qiujuer/article/details/40298761

有时候我有这样的需求：在一个程序的操作中我需要保存历史记录，或者存储一些信息；但我不希望这个数据在内存中是无限量增加的。简单的说，就是使用数组或者链表但是我不希望其无限量的增长，我只需要保存最近的20或者30条记录就ok，多了我不要。

就上面的需求来说，可能我们可以直接通过一定的方法对数组或者链表进行一定的操作（满了就删除第一个）就能实现对应的需求，当然也可以二次封装。

我最初的实现方式如下：

首先建立一个接口：

import java.util.Deque;
import java.util.List;

/**
 * Created by QiuJu
 * on 2014/9/23.
 */
public interface FixedList<T> extends List<T>, Deque<T>, Cloneable, java.io.Serializable {
    /**
     * 向最后添加一个新的
     * 如果长度超过允许的最大值，则弹出一个
     */
    T addElement(T addLast);

    /**
     * 获得最大阈值
     *
     * @return 阈值
     */
    int getMaxSize();

    /**
     * 设置最大存储范围
     *
     * @return 因为改变了队列大小，导致弹出的头部数据
     */
    List<T> setMaxSize(int maxSize);

    /**
     * 转换为List数据
     * @return List
     */
    List<T> toList();
}

而后我实现了这个接口：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class FixedLinkedList<T> extends LinkedList<T> implements FixedList<T> {
    private transient int maxSize = Integer.MAX_VALUE;

    public FixedLinkedList() {
        super();
    }

    public FixedLinkedList(int maxSize) {
        super();
        this.maxSize = maxSize;
    }

    @Override
    public T addElement(T addLast) {
        T head = null;
        while (size() >= maxSize) {
            head = poll();
        }
        addLast(addLast);
        return head;
    }

    @Override
    public List<T> setMaxSize(int maxSize) {
        List<T> list = null;
        if (maxSize < this.maxSize) {
            list = new ArrayList<T>();
            while (size() > maxSize) {
                list.add(poll());
            }
        }
        this.maxSize = maxSize;
        return list;
    }

    @Override
    public List<T> toList() {
        List<T> list = new ArrayList<T>();
        list.addAll(this);
        return list;
    }

    @Override
    public int getMaxSize() {
        return this.maxSize;
    }
}

实现接口也相对简单，无非就是添加判断删除，改变大小时弹出多余的就OK。

使用方法也简单：

FixedList<String> fixed = new FixedLinkedList<String>(10);
//添加元素
fixed.addElement("1");
fixed.addElement("2");
fixed.addElement("3");
fixed.setMaxSize(5);
//转换为List
List<String> fixedList = fixed.toList();

实现功能是实现了，但是对于我这个有完美情节的人来说心里始终有个疙瘩；因为其添加元素只能使用 addElement() 方法，不能使用默认的 add() 方法，默认方法不知道删除多余数据的，当然这也是这种实现方式的短板。为了解决这个问题，我查看了 Java 对 List 的 实现，查看了其对 ArrayList 和 LinkedList 的实现，发现针对上面的需求使用 ArrayList 是不恰当的，因为其需要经常删除元素，如果使用 ArrayList 将会涉及到重复拷贝的问题。所以打算重写 LinkedList 类。

重写当然是个漫长的过程，不过真的非常感谢国外的大牛对 LinkedList 的贡献，站在巨人肩膀上就是好，重写后的操作为下：

// ===================FixedList===================
// 固定长度队列
// 可指定长度，使用方法与普通队列类似
// 当加入元素数量达到指定数量时将弹出元素
// 头部插入尾部弹出，尾部插入头部弹出

// 初始化最大长度为5
FixedList<Integer> list = new FixedList<Integer>(5);
// 添加元素
list.add(1);
// 末尾插入元素与add一样
list.addLast(1);
// 从头部插入，默认删除尾部超出元素
list.addFirst(19);
// 添加一个列表
list.addAll(new ArrayList<Integer>());

// 获取最大容量
list.getMaxSize();
// 调整最大长度；缩小长度时将自动删除头部多余元素
list.setMaxSize(3);

// 采用poll方式弹出元素
int i = list.poll();
// remove 与 poll 类似，不过不返回删除元素，仅删除一个元素
list.remove();
// 清空操作
list.clear();

// 可使用List操作
List<Integer> list1 = new FixedList<Integer>(2);
list1.add(1);
list1.clear();

这下心里舒服多了，对了源码较多我给个链接：源码

如果觉得不错，可以看看我的开源项目：

Genius-Android