队列特征
网络异常，图片无法展示
|
队列的实现
网络异常，图片无法展示
|
依旧是基于我们自己封装的Array。
public class Queue<E> implements QueueInterface<E> { private Array<E> array; public Queue(int capacity) { array = new Array<>(capacity); } public Queue() { this(10); } @Override public void enqueue(E e) { // 加入元素 array.addLast(e); } @Override public E dequeue() { // 取出第一个元素 return array.removeFirst(); } @Override public E getFront() { return array.getFirst(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue ["); for(int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if(i != array.getSize() - 1) { res.append(","); } } res.append("]"); return res.toString(); } }
复杂度分析
网络异常，图片无法展示
|
由于上面出队的时间复杂度为o(n)，结合队列的特征，我们可以使用循环队列来解决这个问题。
由于，我们出队时，后面的元素顺序是不会改变的。所以我们没必要把后面的元素依次向前移动。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
循环队列
基于上面的分析，我们可以编写出一下结构。
- 入队的时候，有益让数组空出一个位置，为了判断队列已满。（tail + 1）% arr.length == front。
- 扩容的时候，巧妙地使用了size。让i来控制front向下移动。让其按照顺序加入新队列。
- front始终指向队首元素，tail始终指向队尾的下一个位置。
- 所有循环的获取位置都是通过 % arr.length
public class LoopQueue<E> implements QueueInterface<E> { private E[] arr; private int front; private int tail; private int size; public LoopQueue(int capacity) { // 为了满足tail + 1 == front为满 arr = (E[]) new Object[capacity + 1]; front = 0; tail = 0; size = 0; } public LoopQueue() { this(10); } @Override public void enqueue(E e) { // 入队 if((tail + 1) % arr.length == front) { // 未删除，并且队列已满 // throw new Error("(tail + 1) % arr.length == front, 队列已满"); resize(getCapacity() * 2); } arr[tail] = e; tail = (tail + 1) % arr.length; size++; } public void resize(int capacity) { E[] newArr = (E[]) new Object[capacity + 1]; // 巧妙地使用了size。让i来控制front向下移动。 for(int i = 0; i < size; i++) { // 这里就将队列中的元素按顺序加入了 newArr[i] = arr[(i + front) % arr.length]; } arr = newArr; front = 0; tail = size; } @Override public E dequeue() { if(isEmpty()) { throw new Error("Queue is empty"); } E e = arr[front]; arr[front] = null; // 移动头指针。 front = (front + 1) % arr.length; size--; if(size == getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return e; } @Override public E getFront() { if(isEmpty()) { throw new Error("Queue is empty"); } return arr[front]; } public int getCapacity() { return arr.length - 1; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return false; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("LoopQueue capacity %d, size %d", getCapacity(), size)); res.append(" front ["); for(int i = front; i != tail ; i = (i + 1) % arr.length) { res.append(arr[i]); if((i + 1) % arr.length != tail) { res.append(","); } } res.append("] tail"); return res.toString(); } }
循环队列复杂度分析
网络异常，图片无法展示
|
队列和循环队列的复杂度比较
网络异常，图片无法展示
|
