[TOC]
# 数组队列的问题
数组队列的出队复杂度是O(n)
队列的首移除,不把里面的元素重新排列,就把font指向向后移动
**font == tail 队列为空**
**(tail+1)%c == front 队列满**
如果tail到最后,这个数组此时不应该扩容,因为数组前面有空间没有被利用
那么这时候应该把tail移动到前面没有用的位置
capacity中,浪费一个空间
# 接口
还是用之前的动态数组
~~~
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
~~~
# 实现类
~~~
public class LoopQueue<E> implements Queue<E> {
//里面单位有一个会被有意识的浪费
private E[] data;
//对首和对尾
private int front, tail;
//队列大小
private int size;
public LoopQueue(int capacity) {
//循环队列有意识的浪费一个空间
data = (E[]) new Object[capacity + 1];
//初始化成员变量
front = 0;
tail = 0;
size = 0;
}
public LoopQueue() {
this(10);
}
//循环队列中可以装多个元素
public int getCapacity() {
//有一个会被潜意识浪费
return data.length - 1;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front == tail;
}
//入队
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == front) {
//表示要扩容
resize(getCapacity() * 2);
}
data[tail] = e;
//添加了一个元素,tail就要+1,同时为了防止数组满了,需要跑队列前面
tail = (tail + 1) % data.length;
size++;
}
//扩容
private void resize(int newCapacity) {
//在构造函数那边还会再+1的
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
//位置可能会跑到前面,但是数组不能越界,最终这个位置会被放到后面
//就像被重新拉长了
newData[i] = data[(i + front) % data.length];
}
data = newData;
front = 0;
//对尾就是这个最大长度
tail = size;
}
//出队
@Override
public E dequeue() {
//空队列是不能出队的
if (isEmpty()) {
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
}
//出队是要把头部的元素出去
E ret = data[front];
//把头部元素的引用置为null,让他可以被gc,占着引用无法gc
data[front] = null;
//头元素向后移动1位,同时不能超过数组的长度
front = (front + 1) % data.length;
size--;
//如果出队之后,装的元素少于1/4就缩容,但是队列中元素不能为0
if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
//进行缩容
resize(getCapacity() / 2);
}
return ret;
}
//获取对首
@Override
public E getFront() {
//空队列是不能出队的
if (isEmpty()) {
throw new IllegalArgumentException("Queue is empty");
}
return data[front];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size=%d,capacity=%d\n", size, getCapacity()));
res.append("front [");
//由于是循环队列
for (int i = front; i != tail; i = (i + 1) % data.length) {
res.append(data[i]);
//如果不是最后一个元素
if (i+1 % data.length != tail) {
res.append(", ");
}
}
res.append("] tail");
return res.toString();
}
}
~~~
# 测试
~~~
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<Integer>();
for (int i = 0; i<10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 ==2) {
queue.dequeue();
System.out.println(queue);
}
}
}
~~~
# 复杂度分析
