Java如何实现循环队列

小编给大家分享一下Java如何实现循环队列，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

循环队列

循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O(n)) 的问题.

循环队列的底层依然是数组, 不过增加了指向头和尾的指针.

循环队列实现

1. 判断队列是否为空: 当头指针 Q.front == 尾指针 Q.rear, 队列为空

2. 判断队列是否为满: 当头指针 Q.front == 尾指针 Q.rear + 1) % Maxsize, 队列为满

改变队列大小

// 改变队列大小private void resize(int capacity) {        // 定义新数组    E[] newData = (E[]) new Object[capacity + 1];        // 转移数组元素    for (int i = 0; i < size; i++) {        newData[i] = data[(i +front) % data.length];    }    // 更新    data = newData;    front = 0;    rear = size;}

enqueue 方法

// 入队public void enqueue(E e) {    // 判断是否为满    if((rear + 1) % data.length == front) {        resize(getCapacity() * 2);    }    // 队伍加入    data[rear] = e;    rear = (rear + 1) % data.length;    size++;}

dequeue 方法

// 出队public E dequeue() {    // 判断是否为空    if(isEmpty()) {        throw new RuntimeException("队列为空");    }    // 取出第一个元素    E element = data[front];    data[front] = null;    // 移动头指针    front = (front + 1) % data.length;    // 数组大小-1    size--;    // 判断是否需要缩小    if(size==getCapacity() / 4 && getCapacity() / 2 != 0) {        resize(getCapacity() / 2);    }    return element;}

main

// 主函数public static void main(String[] args) {    // 创建循环队列    CircularQueue queue = new CircularQueue<>(5);    // 入队    for (int i = 0; i < 8; i++) {        queue.enqueue(i);        System.out.println(queue);    }    // 出队    for (int i = 0; i < 8; i++) {        queue.dequeue();        System.out.println(queue);    }}

输出结果:

CircularQueue{data=[0, null, null, null, null, null], front=0, rear=1, size=1}

CircularQueue{data=[0, 1, null, null, null, null], front=0, rear=2, size=2}

CircularQueue{data=[0, 1, 2, null, null, null], front=0, rear=3, size=3}

CircularQueue{data=[0, 1, 2, 3, null, null], front=0, rear=4, size=4}

CircularQueue{data=[0, 1, 2, 3, 4, null], front=0, rear=5, size=5}

CircularQueue{data=[0, 1, 2, 3, 4, 5, null, null, null, null, null], front=0, rear=6, size=6}

CircularQueue{data=[0, 1, 2, 3, 4, 5, 6, null, null, null, null], front=0, rear=7, size=7}

CircularQueue{data=[0, 1, 2, 3, 4, 5, 6, 7, null, null, null], front=0, rear=8, size=8}

CircularQueue{data=[null, 1, 2, 3, 4, 5, 6, 7, null, null, null], front=1, rear=8, size=7}

CircularQueue{data=[null, null, 2, 3, 4, 5, 6, 7, null, null, null], front=2, rear=8, size=6}

CircularQueue{data=[null, null, null, 3, 4, 5, 6, 7, null, null, null], front=3, rear=8, size=5}

CircularQueue{data=[null, null, null, null, 4, 5, 6, 7, null, null, null], front=4, rear=8, size=4}

CircularQueue{data=[null, null, null, null, null, 5, 6, 7, null, null, null], front=5, rear=8, size=3}

CircularQueue{data=[6, 7, null, null, null, null], front=0, rear=2, size=2}

CircularQueue{data=[7, null, null], front=0, rear=1, size=1}

CircularQueue{data=[null, null], front=0, rear=0, size=0}

完整代码

import java.util.ArrayList;import java.util.Arrays;public class CircularQueue {    private E[] data;    private int front, rear;    private int size;    // 无参构造    public CircularQueue() {        this(10);    }    // 有参构造    public CircularQueue(int capacity) {       data = (E[]) new Object[capacity + 1];       front = rear = size = 0;    }    // 入队    public void enqueue(E e) {        // 判断是否为满        if((rear + 1) % data.length == front) {            resize(getCapacity() * 2);        }        // 队伍加入        data[rear] = e;        rear = (rear + 1) % data.length;        size++;    }    // 出队    public E dequeue() {        // 判断是否为空        if(isEmpty()) {            throw new RuntimeException("队列为空");        }        // 取出第一个元素        E element = data[front];        data[front] = null;        // 移动头指针        front = (front + 1) % data.length;        // 数组大小-1        size--;        // 判断是否需要缩小        if(size==getCapacity() / 4 && getCapacity() / 2 != 0) {            resize(getCapacity() / 2);        }        return element;    }    // 获取队列大小    public int getSize() {        return size;    }    // 获取队列容量    public int getCapacity() {        return data.length - 1;    }    // 队列是否为空    public boolean isEmpty() {        return front == rear;    }    // 改变队列大小    private void resize(int capacity) {        // 创建新数组        E[] newData = (E[]) new Object[capacity + 1];        // 转移数组元素        for (int i = 0; i < size; i++) {            newData[i] = data[(i +front) % data.length];        }        // 更新        data = newData;        front = 0;        rear = size;    }    @Override    public String toString() {        return "CircularQueue{" +                "data=" + Arrays.toString(data) +                ", front=" + front +                ", rear=" + rear +                ", size=" + size +                '}';    }    // 主函数    public static void main(String[] args) {        // 创建循环队列        CircularQueue queue = new CircularQueue<>(5);        // 入队        for (int i = 0; i < 8; i++) {            queue.enqueue(i);            System.out.println(queue);        }        // 出队        for (int i = 0; i < 8; i++) {            queue.dequeue();            System.out.println(queue);        }    }}

看完了这篇文章，相信你对"Java如何实现循环队列"有了一定的了解，如果想了解更多相关知识，欢迎关注行业资讯频道，感谢各位的阅读！