哪些网站可以做h5/在线查询网站收录
写在前面
本系列代码Gitee地址为点击这里
接口 Queue.java
public interface Queue {
// 入队
void enqueue(E e);
// 出队
E dequeue();
// 获取队首元素
E getFront();
// 获取队列大小
int getSize();
// 判断队列是否为空
boolean isEmpty();
}
实现 ArrayQueue(数组队列)
基于《创建一个自己的Array》
注：此实现在出队时开销过大，不推荐使用
public class ArrayQueue implements Queue {
private Array array;
public ArrayQueue(int capacity) {
array = new Array(capacity);
}
public ArrayQueue() {
array = new Array();
}
@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();
}
public int getCapacity() {
return array.getCapacity();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public String toString() {
return String.format("Queue: size = %d, capacity = %d\n", array.getSize(), array.getCapacity()) +
"front " + array + " tail";
}
}
实现 LoopQueue.java(循环队列)
public class LoopQueue implements Queue {
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);
}
@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 >= 5 && size == getCapacity() / 4)
resize(getCapacity() / 2);
return ret;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("Queue is empty.");
}
return data[front];
}
@Override
public int getSize() {
return size;
}
public int getCapacity() {
return data.length - 1;
}
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d, capacity = %d\n", getSize(), 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();
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++)
newData[i] = data[(1 + front) % data.length];
data = newData;
front = 0;
tail = size;
}
}
实现LinkedListQueue.java(链表队列)
public class LinkedListQueue implements Queue {
LinkedList linkedList;
public LinkedListQueue() {
this.linkedList = new LinkedList();
}
@Override
public void enqueue(E e) {
linkedList.addLast(e);
}
@Override
public E dequeue() {
return linkedList.removeFirst();
}
@Override
public E getFront() {
return linkedList.getFirst();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public String toString() {
return String.format("Queue: size=%d\nhead %s tail", getSize(), linkedList);
}
}
实现PriorityQueue.java(优先队列)
public class PriorityQueue> implements Queue {
private MaxHeap maxHeap;
public PriorityQueue() {
maxHeap = new MaxHeap<>();
}
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
@Override
public E dequeue() {
return maxHeap.extractMax();
}
@Override
public E getFront() {
return maxHeap.findMax();
}
@Override
public int getSize() {
return maxHeap.size();
}
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
}