java队列的实现
程序员文章站
2024-03-01 13:21:28
...
还是拿之前的自己打造的ArrayList进行编写
Queue接口
public interface Queue<E> {
int getSize();
boolean isEmpty();
//入队
void enqueue(E e);
//出队
E dequeue();
//获得队首
E getFront();
}
ArrayQueue队列的实现
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity) {
array = new Array<>(capacity);
}
public ArrayQueue() {
array=new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@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 String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue:").append("front [");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize()) {
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args) {
ArrayQueue<Integer >queue=new ArrayQueue<>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
LoopQueue循环队列
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int size;
private int front, tail;//如果队首等于对于队尾,则代表数据为空
public LoopQueue(int capacity) {
data = (E[]) new Object[capacity + 1];//真如刚才所说,当队首等于队尾的时候数据为空,所以我们需要浪费一个空间
size = 0;
front = 0;
tail = 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 = (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()!=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++) {
//将旧的数据的队列指向新的数据的0的位置
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);
}
}
}
}
测试循环队列和队列的效率
public class TestQueue {
//测试使用q运行opCount和enqueue和dequeue操作所需要的时间,单位:s
private static double testQueue(Queue<Integer> q, int opCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
q.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < opCount; i++) {
q.dequeue();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue,time:" + time1 + "s");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue,time:" + time2 + "s");
}
}
循环队列的出栈复杂度是0(1)的,而队列的出栈复杂度是0(n)
上一篇: 利用Python实现Windows下的鼠标键盘模拟的实例代码
下一篇: Java实现--链表队列