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
#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