队列接口Queue
- 用接口Queue表示队列这种数据结构，具体的实现因底层使用到的数据结构的不同而不同；
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
循环队列LoopQueue
-
front作为索引，指向队首的元素； -
tail作为索引，指向队尾元素的下一格，即新入队的元素要待的位置； - 队列为空的条件是
front == tail; - 队列为满的条件是
(tail + 1) % data.length == front； - 因为
capacity中的空间要浪费一个，所以在初始化的时候是(E[])new Object[capacity + 1]，即：要创建容量为 10 的队列，就要在底层开辟一个长度为 10+1=11 的数组； - 同样的原因，在返回队列容量的时候，返回的是底层数组的长度减 1，即 data.length - 1，即：队列的容量是 10，底层数组的长度是 11，返回 11-1=10；
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front;
private int 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 boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size --;
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];
}
private void resize(int newCapacity){
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 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<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
输出：
Queue: size = 1 , capacity = 10
front [0] tail
Queue: size = 2 , capacity = 10
front [0, 1] tail
Queue: size = 3 , capacity = 10
front [0, 1, 2] tail
Queue: size = 2 , capacity = 5
front [1, 2] tail
Queue: size = 3 , capacity = 5
front [1, 2, 3] tail
Queue: size = 4 , capacity = 5
front [1, 2, 3, 4] tail
Queue: size = 5 , capacity = 5
front [1, 2, 3, 4, 5] tail
Queue: size = 4 , capacity = 5
front [2, 3, 4, 5] tail
Queue: size = 5 , capacity = 5
front [2, 3, 4, 5, 6] tail
Queue: size = 6 , capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Queue: size = 7 , capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
Queue: size = 6 , capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Queue: size = 7 , capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail
特别关注1：void enqueue(E e)
- 当队列满时，队列要扩容；
- 在维护游标
tail的时候，不是简单的tail++，而是tail = (tail + 1) % data.length;
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
特别关注2：void resize(int newCapacity)
- 扩容时的思路还是新建一个数组，把数组
data中的元素复制到新数组中； - 新建数组的容量对应到底层开辟数组的长度还是要加 1，即
(E[])new Object[newCapacity + 1]； - 老数组的元素在往新数组中“掉”的时候，注意老数组的队首元素和新数组索引为 0 的元素之间有一个
front的偏移量；再加上老数组上的游标是从front开始，从front开始循环遍历，故新数组的游标i和老数组上的游标的对应关系为：i对应(i + front) % data.length； - 完成复制后，让游标
front指向新数组的 0，游标tail指向新数组的size； - 在刚复制完成的时候，
size逻辑上是队列的元素个数，作为索引指向新入队的元素将要待的位置；
private void resize(int newCapacity){
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;
}
特别关注3：E dequeue()
- 出队的时候，若队列为空，则不允许出队操作；
- 在取出队首元素和返回队首元素之间有两个操作：维护游标
front和队列元素个数size，缩容； - 维护游标
front的时候，不是简单的front++，而是让front在data.length的范围内“循环游走”，即：front = (front + 1) % data.length; - 缩容的时候采用
lazy的策略，元素个数为容量 1/4 时，容量缩小为 1/2 ；
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size --;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}
