实现固定长度的java.util.Queue

要求实现 java.util.Queue<E>。

1: 支持范型
2：支持固定size。当queue的满了之后插入元素的时候，最先入队的元素要自动remove。

6 个解决方案

#1

你拿ArrayList模拟下不就差不多了。。。自己设置个size，当大于这个size的时候用list的remove方法把第一个去除，全部元素会前移，然后你再插入~

#2

用滚动数组实现吧

public class FixedSizeQueue<E> {
    Object[] elements;
    int capacity;
    int head;
    int tail;
    int size;

    public FixedSizeQueue(int capacity) {
        if (capacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + capacity);
        elements = new Object[capacity];
        this.capacity = capacity;
        head = 0;
        tail = (head - 1) % capacity;
        size = 0;
    }

    public boolean add(E e) {
        tail = (tail + 1) % capacity;
        elements[tail] = e;
        size = (size + 1) > capacity ? capacity : size + 1;
        head = (tail + 1 + capacity - size) % capacity;
        return true;
    }

    public E remove() {
        if (size == 0)
            return null;
        E element = (E) elements[head];
        head = (head + 1) % capacity;
        size--;
        return element;
    }

    public E element() {
        if (size == 0)
            return null;
        E element = (E) elements[head];
        return element;
    }

    public int size() {
        return size;
    }

    public boolean empty() {
        return size == 0;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0, j = head; i < size; j = (j + 1) % capacity, i++) {
            if (i != 0)
                sb.append(',');
            sb.append(elements[j]);
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main(String[] args) {
        FixedSizeQueue<Integer> queue = new FixedSizeQueue<Integer>(10);
        for (int i = 0; i < 35; i++) {
            queue.add(i);
        }
        System.out.println(queue);
        for (int i = 0; i < 5; i++) {
            System.out.println("remove " + queue.remove());
        }
        System.out.println(queue);
        for (int i = 0; i < 7; i++) {
            queue.add(i);
        }
        System.out.println(queue);
    }
}

输出

[25,26,27,28,29,30,31,32,33,34]
remove 25
remove 26
remove 27
remove 28
remove 29
[30,31,32,33,34]
[32,33,34,0,1,2,3,4,5,6]

#3

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;

@SuppressWarnings("unchecked")
public class FixedSizeQueue<E> implements Queue<E> {
    private Object[] elements;
    private int capacity;
    private int head;
    private int tail;
    private int size;

    private int modCount;

    public FixedSizeQueue(int capacity) {
        if (capacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + capacity);
        elements = new Object[capacity];
        this.capacity = capacity;
        head = 0;
        tail = (head - 1) % capacity;
        size = 0;
    }

    @Override
    public boolean add(E e) {
        modCount++;
        tail = (tail + 1) % capacity;
        elements[tail] = e;
        size = (size + 1) > capacity ? capacity : size + 1;
        head = (tail + 1 + capacity - size) % capacity;
        return true;
    }

    @Override
    public E element() {
        if (size == 0)
            throw new NoSuchElementException();
        E element = (E) elements[head];
        return element;
    }

    @Override
    public boolean offer(E e) {
        return add(e);
    }

    @Override
    public E peek() {
        if (size == 0)
            return null;
        E element = (E) elements[head];
        return element;
    }

    @Override
    public E poll() {
        modCount++;
        if (size == 0)
            return null;
        E element = (E) elements[head];
        head = (head + 1) % capacity;
        size--;
        return element;
    }

    @Override
    public E remove() {
        modCount++;
        if (size == 0)
            throw new NoSuchElementException();
        ;
        E element = (E) elements[head];
        head = (head + 1) % capacity;
        size--;
        return element;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        for (E e : c) {
            add(e);
        }
        return true;
    }

    @Override
    public void clear() {
        modCount++;
        size = 0;
    }

    @Override
    public boolean contains(Object o) {
        if (o == null) {
            for (Object obj : elements) {
                if (obj == null) {
                    return true;
                }
            }
        } else {
            for (Object obj : elements) {
                if (o.equals(obj)) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        if (c.size() > size) {
            return false;
        }
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iter();
    }

    @Override
    public boolean remove(Object o) {
        modCount++;
        if (o == null) {
            for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
                Object obj = elements[j];
                if (obj == null) {
                    if (j >= head) {
                        System.arraycopy(elements, head, elements, (head + 1)
                                % capacity, i);
                        head = (head + 1) % capacity;
                        size--;
                    } else {
                        System.arraycopy(elements, j + 1, elements, j, size - i
                                - 1);
                        tail = (tail - 1) % capacity;
                        size--;
                    }
                    return true;
                }
            }
        } else {
            for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
                Object obj = elements[j];
                if (o.equals(obj)) {
                    if (j >= head) {
                        System.arraycopy(elements, head, elements, (head + 1)
                                % capacity, i);
                        head = (head + 1) % capacity;
                        size--;
                    } else {
                        System.arraycopy(elements, j + 1, elements, j, size - i
                                - 1);
                        tail = (tail - 1) % capacity;
                        size--;
                    }
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        int count = 0;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (c.contains(e.next())) {
                e.remove();
                count++;
            }
        }
        modCount += count;
        return count != 0;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        int count = 0;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (!c.contains(e.next())) {
                e.remove();
                count++;
            }
        }
        modCount += count;
        return count != 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object[] toArray() {
        Object[] arr = new Object[size];
        for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
            arr[i] = elements[j];
        }
        return arr;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        if (a.length < size) {
            T[] arr = (T[]) Array.newInstance(a.getClass().getComponentType(),
                    size);
            for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
                arr[i] = (T) elements[j];
            }
            return (T[]) arr;
        }
        for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
            a[i] = (T) elements[j];
        }
        if (a.length > size) {
            a[size] = null;
        }
        return a;
    }

    private class Iter implements Iterator<E> {
        int cursor = 0;
        int lastRet = -1;
        int expectedModCount = modCount;

        @Override
        public boolean hasNext() {
            return cursor != size();
        }

        @Override
        public E next() {
            checkForComodification();
            E next = (E) elements[(head + cursor) % capacity];
            lastRet = cursor++;
            return next;
        }

        @Override
        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();
            int j = (head + lastRet) % capacity;
            if (j >= head) {
                System.arraycopy(elements, head, elements, (head + 1)
                        % capacity, lastRet);
                head = (head + 1) % capacity;
                size--;
            } else {
                System.arraycopy(elements, j + 1, elements, j, size - lastRet
                        - 1);
                tail = (tail - 1) % capacity;
                size--;
            }
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0, j = head; i < size; j = (j + 1) % capacity, i++) {
            if (i != 0)
                sb.append(',').append(' ');
            sb.append(elements[j]);
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main(String[] args) {
        FixedSizeQueue<Integer> queue = new FixedSizeQueue<Integer>(10);
        for (int i = 0; i < 35; i++) {
            queue.add(i);
        }
        System.out.println(queue);
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 32; i < 35; i++) {
            list.add(i);
        }
        queue.retainAll(list);
        System.out.println(queue);
        System.out.println(queue.contains(31));
    }
}

很十三的去implements Queue<E>……
功能是都实现了，有没有bug不知道……

#4

@zhuzeitou:圆满了。

#5

学习了~~

#6

最后一行测试有BUG

引用 3 楼 zhuzeitou 的回复:

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;

@SuppressWarnings("unchecked")
public class FixedSizeQueue<E> implements Queue<E> {
    private Object[] elements;
    private int capacity;
    private int head;
    private int tail;
    private int size;

    private int modCount;

    public FixedSizeQueue(int capacity) {
        if (capacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + capacity);
        elements = new Object[capacity];
        this.capacity = capacity;
        head = 0;
        tail = (head - 1) % capacity;
        size = 0;
    }

    @Override
    public boolean add(E e) {
        modCount++;
        tail = (tail + 1) % capacity;
        elements[tail] = e;
        size = (size + 1) > capacity ? capacity : size + 1;
        head = (tail + 1 + capacity - size) % capacity;
        return true;
    }

    @Override
    public E element() {
        if (size == 0)
            throw new NoSuchElementException();
        E element = (E) elements[head];
        return element;
    }

    @Override
    public boolean offer(E e) {
        return add(e);
    }

    @Override
    public E peek() {
        if (size == 0)
            return null;
        E element = (E) elements[head];
        return element;
    }

    @Override
    public E poll() {
        modCount++;
        if (size == 0)
            return null;
        E element = (E) elements[head];
        head = (head + 1) % capacity;
        size--;
        return element;
    }

    @Override
    public E remove() {
        modCount++;
        if (size == 0)
            throw new NoSuchElementException();
        ;
        E element = (E) elements[head];
        head = (head + 1) % capacity;
        size--;
        return element;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        for (E e : c) {
            add(e);
        }
        return true;
    }

    @Override
    public void clear() {
        modCount++;
        size = 0;
    }

    @Override
    public boolean contains(Object o) {
        if (o == null) {
            for (Object obj : elements) {
                if (obj == null) {
                    return true;
                }
            }
        } else {
            for (Object obj : elements) {
                if (o.equals(obj)) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        if (c.size() > size) {
            return false;
        }
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iter();
    }

    @Override
    public boolean remove(Object o) {
        modCount++;
        if (o == null) {
            for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
                Object obj = elements[j];
                if (obj == null) {
                    if (j >= head) {
                        System.arraycopy(elements, head, elements, (head + 1)
                                % capacity, i);
                        head = (head + 1) % capacity;
                        size--;
                    } else {
                        System.arraycopy(elements, j + 1, elements, j, size - i
                                - 1);
                        tail = (tail - 1) % capacity;
                        size--;
                    }
                    return true;
                }
            }
        } else {
            for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
                Object obj = elements[j];
                if (o.equals(obj)) {
                    if (j >= head) {
                        System.arraycopy(elements, head, elements, (head + 1)
                                % capacity, i);
                        head = (head + 1) % capacity;
                        size--;
                    } else {
                        System.arraycopy(elements, j + 1, elements, j, size - i
                                - 1);
                        tail = (tail - 1) % capacity;
                        size--;
                    }
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        int count = 0;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (c.contains(e.next())) {
                e.remove();
                count++;
            }
        }
        modCount += count;
        return count != 0;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        int count = 0;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (!c.contains(e.next())) {
                e.remove();
                count++;
            }
        }
        modCount += count;
        return count != 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object[] toArray() {
        Object[] arr = new Object[size];
        for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
            arr[i] = elements[j];
        }
        return arr;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        if (a.length < size) {
            T[] arr = (T[]) Array.newInstance(a.getClass().getComponentType(),
                    size);
            for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
                arr[i] = (T) elements[j];
            }
            return (T[]) arr;
        }
        for (int i = 0, j = head; i < size; i++, j = (j + 1) % capacity) {
            a[i] = (T) elements[j];
        }
        if (a.length > size) {
            a[size] = null;
        }
        return a;
    }

    private class Iter implements Iterator<E> {
        int cursor = 0;
        int lastRet = -1;
        int expectedModCount = modCount;

        @Override
        public boolean hasNext() {
            return cursor != size();
        }

        @Override
        public E next() {
            checkForComodification();
            E next = (E) elements[(head + cursor) % capacity];
            lastRet = cursor++;
            return next;
        }

        @Override
        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();
            int j = (head + lastRet) % capacity;
            if (j >= head) {
                System.arraycopy(elements, head, elements, (head + 1)
                        % capacity, lastRet);
                head = (head + 1) % capacity;
                size--;
            } else {
                System.arraycopy(elements, j + 1, elements, j, size - lastRet
                        - 1);
                tail = (tail - 1) % capacity;
                size--;
            }
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0, j = head; i < size; j = (j + 1) % capacity, i++) {
            if (i != 0)
                sb.append(',').append(' ');
            sb.append(elements[j]);
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main(String[] args) {
        FixedSizeQueue<Integer> queue = new FixedSizeQueue<Integer>(10);
        for (int i = 0; i < 35; i++) {
            queue.add(i);
        }
        System.out.println(queue);
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 32; i < 35; i++) {
            list.add(i);
        }
        queue.retainAll(list);
        System.out.println(queue);
        System.out.println(queue.contains(31));
    }
}

很十三的去implements Queue<E>……
功能是都实现了，有没有bug不知道……