Java动态循环队列怎么实现

这篇文章将为大家详细讲解有关Java动态循环队列怎么实现，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

一、队列

1.1 定义

队列 (Queue) 是一种限定性的有序线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出 (Fist In Fist Out，缩写为FIFO)的特性。

• 在队列中，允许插入的一端叫做队尾(rear)；

• 允许删除的一端则称为队头(front)。

• 队列是一个有序列表，可以用数组或是链表来实现。

• 遵循先进先出的原则。即:先存入队列的数据，要先取出。

1.2 抽象数据类型

数据元素：可以是任意类型的数据，但必须属于同一个数据对象。

关系：队列中数据元素之间是线性关系。

基本操作:

初始化操作。使用构造方法设置一个空队列。

isEmpty():判空操作。若队列为空，则返回TRUE，否则返回FALSE。

isFull():判满操作。若队列为满,则返回TRUE，否则返回FALSE。

getSize():获取队列元素个数。

add(E e):进队操作。在队列Q的队尾插入e。如果队满，抛出异常。

poll():出队操作。使队列Q的队头元素出队，并用e返回其值。如果队空，抛出异常。

getHead ():取队头元素操作。用e取得队头元素的值。如果队列为空，则返回null。

clear():队列置空操作。将队列Q置为空队列。

destroy():队列销毁操作。释放队列的空间。

1.3 顺序存储

队列的一种顺序存储称为顺序队列。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组Queue[maxSize]。

二、数组队列

由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针 front和 rear。

• front：指示队头元素在数组中的位置;

• rear：指示真实队尾元素相邻的下一个位置。

2.1 思路分析

• 初始化队列时，令front = rear = 0。

• 判断队空的条件：front == rear。

• 判断队满的条件：rear == maxSize。

• 入队时，若尾指针rear 小于队列的最大下标 maxSize,则将数据存入rear所指的数组元素中,否则无法存入数据；然后将尾指针往后移: rear + 1。

• 出队时，若队列不为空，取出队头指针front所指的元素；然后将尾指针往后移: front + 1。

2.2 代码实现

定义接口方法：

public interface Queue<E> {        boolean isEmpty();        boolean isFull();        int getCapacity();        int getSize();        void add(E e);        E poll();        E getHead();}

2.3 数组队列实现

public class ArrayQueue<E> implements Queue<E> {        private int maxSize;        private int front;        private int rear;        private E[] data;        @SuppressWarnings("unchecked")    public ArrayQueue(int arrMaxSize) {        maxSize = arrMaxSize;        data = (E[]) new Object[maxSize];        front = 0;        rear = 0;    }        @Override    public boolean isEmpty() {        return front == rear;    }        @Override    public boolean isFull() {        return rear == maxSize;    }        @Override    public int getSize() {        return rear - front;    }        @Override    public void add(E e) {        if (isFull()) {            throw new IllegalArgumentException("队列已满，不能入队！");        }        data[rear++] = e;    }        @Override    public E poll() {        if (isEmpty()) {            throw new IllegalArgumentException("队列为空，不能出队！");        }        //出队位置置null        E temp = data[front];        data[front++] = null;        return temp;    }        @Override    public E getHead() {        return data[front];    }        @Override    public int getCapacity() {        return data.length - 1;    }        public int getEmptyCount() {        return maxSize - rear;    }    @Override    public String toString() {        StringBuilder res = new StringBuilder();        res.append("Queue: ");        res.append("front [");        for (int i = front; i < rear; i++) {            res.append(data[i]);            if (i != rear - 1) {                res.append(", ");            }        }        res.append("] rear");        return res.toString();    }        public static void main(String[] args) {        ArrayQueue<Integer> queue = new ArrayQueue<>(5);        Scanner sc = new Scanner(System.in);        char c;        boolean loop = true;        while (loop) {            System.out.println("s(toString):输出队列");            System.out.println("e(exit):退出程序");            System.out.println("a(add):添加数据到队列");            System.out.println("p(poll):从队列取出数据");            System.out.println("h(getHead):查看队列头的数据");            System.out.println("n(isEmpty):是否队空");            System.out.println("f(isFull):是否队满");            c = sc.next().charAt(0);            switch (c) {                case 's':                    System.out.println("当前队列：" + queue.toString() + "\t元素个数：" + queue.getSize() + "\t有效容量：" + queue.getEmptyCount());                    break;                case 'e':                    sc.close();                    loop = false;                    break;                case 'a':                    System.out.println("请输入一个整数");                    queue.add(sc.nextInt());                    break;                case 'p':                    System.out.printf("出队元素：%d\n", queue.poll());                    break;                case 'h':                    System.out.printf("队首元素：%d\n", queue.getHead());                    break;                case 'n':                    System.out.println("队空：" + queue.isEmpty());                    break;                case 'f':                    System.out.println("队满：" + queue.isFull());                    break;                default:                    break;            }        }        System.out.println("程序退出");    }}

2.4 分析

假溢出现象

在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素。当rear == maxSize - 1 时，认为队满。但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元，如下图所示。由于只能在队尾入队，使得上述空单元无法使用。把这种现象称为假溢出。

问题：目前这个数组使用一次就不能用（出队的空间），没有达到复用的效果。可使用算法将其改造成环形队列（取模：%）。

三、环形队列

为了解决假溢出现象并使得队列空间得到充分利用,一个较巧妙的办法是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。

3.1 思路分析

• 初始化队列时，令front = rear = 0。front指向队列的第一个元素，rear指向队列最后一个元素的后一个位置（希望损失一个位置作为约定，用来区分队空和队满）。

• 判断队空的条件：front == rear。

• 判断队满的条件：(rear + 1) % maxSize == front。

• 队列中的元素个数：(rear + maxSize - front) % maxSize。

• 入队时，将数据存入rear所指的数组元素中，指针变化：rear = ( rear+1) % maxSize。

• 出队时，将数据存入front所指的数组元素中，指针变化：front = ( front+1 ) % maxSize。

下图给出了循环队列的几种情况：

3.2 代码实现

public class LoopQueue<E> implements Queue<E> {        private int maxSize;        private int front;        private int rear;        private E[] data;        @SuppressWarnings("unchecked")    public LoopQueue(int arrMaxSize) {        //循环队列需要有意识浪费一个空间        maxSize = arrMaxSize + 1;        data = (E[]) new Object[maxSize];    }        @Override    public boolean isEmpty() {        return front == rear;    }        @Override    public boolean isFull() {        return (rear + 1) % maxSize == front;    }        @Override    public int getCapacity() {        return data.length - 1;    }        @Override    public int getSize() {        return (rear + maxSize - front) % maxSize;    }        @Override    public void add(E e) {        if (isFull()) {            throw new IllegalArgumentException("队列已满，不能入队！");        }        data[rear] = e;        //rear指针后移一位        rear = (rear + 1) % maxSize;    }        @Override    public E poll() {        if (isEmpty()) {            throw new IllegalArgumentException("队列为空，不能出队！");        }        E temp = data[front];        //出队位置置null        data[front] = null;        //front指针后移一位        front = (front + 1) % maxSize;        return temp;    }        @Override    public E getHead() {        return data[front];    }    @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 != rear; i = (i + 1) % data.length) {            res.append(data[i]);            if ((i + 1) % data.length != rear) {                res.append(", ");            }        }        res.append("] tail");        return res.toString();    }        public static void main(String[] args) {        LoopQueue<Integer> queue = new LoopQueue<>(5);        Scanner sc = new Scanner(System.in);        char c;        boolean loop = true;        while (loop) {            System.out.println("s(toString):输出队列");            System.out.println("e(exit):退出程序");            System.out.println("a(add):添加数据到队列");            System.out.println("p(poll):从队列取出数据");            System.out.println("h(getHead):查看队列头的数据");            System.out.println("n(isEmpty):是否队空");            System.out.println("f(isFull):是否队满");            c = sc.next().charAt(0);            switch (c) {                case 's':                    System.out.println("当前队列：" + queue.toString());                    break;                case 'e':                    sc.close();                    loop = false;                    break;                case 'a':                    System.out.println("请输入一个整数");                    queue.add(sc.nextInt());                    break;                case 'p':                    System.out.printf("出队元素：%d\n", queue.poll());                    break;                case 'h':                    System.out.printf("队首元素：%d\n", queue.getHead());                    break;                case 'n':                    System.out.println("队空：" + queue.isEmpty());                    break;                case 'f':                    System.out.println("队满：" + queue.isFull());                    break;                default:                    break;            }        }        System.out.println("程序退出");    }}

3.3 分析

相比数组队列来说，循环队列解决了数组空间不能再次利用的问题。但依然存在一些问题：

• 当队列真的满的时候就不能再进行入队操作了。但是从我们常用的ArrayList来分析，在存储空间允许的条件下是可以一直添加元素的。

• 当数组元素频繁进行入队或者出队操作时，可能造成空间的浪费。循环队列其实只利用了有限的存储空间，但是在最初实例化循环队列的时候，如果空间声明的很大，那么会造成一定程度上的空间浪费。

• 假设，声明一个容量为20的循环队列，但每次入队2个元素后，又出队2个元素，那么实际只利用了很有限的空间，造成了空间浪费，但又不能声明的空间太小，并不能保证未来每次只入队或者出队2个元素。

因此，是否可以实现动态的将循环队列进行扩容或者缩容，上述两个问题，可以利用下面的动态循环队列来实现。

当然，上述的数组队列，也可以改造成动态的，但是出队元素的空间依然会浪费，所以没必要进行实现。

四、动态循环队列

为了解决循环队列，队满不能入队，以及频繁入队出队引起的空间浪费，而引出动态循环队列的概念。即在队满时进行扩容，在队列元素个数下降到一定情况下进行缩容。

4.1 思路分析

• 除了入队和出队操作，其他操作均与循环队列相同。

• 循环队列存储元素的数组容量变更思路：使用扩容一倍/缩容一倍的新数组接收原来循环队列存储的元素。接收后，将front指针置为0；将rear指针值到最后一个元素的位置（即存储有效元素的数量）。

• 什么时候扩容：队满

• 什么时候缩容：队列元素只有1/4，并且缩容后容量不为0。

• 数组容量为0时，缩容会出现异常

• 为什么不在队列元素只有1/2时缩容？当数组元素为一半的时候一次添加，一次删除，造成的一直扩容和减小的操作。

4.2 代码实现

public class DynamicLoopQueue<E> implements Queue<E> {        private int maxSize;        private int front;        private int rear;        private E[] data;        @SuppressWarnings("unchecked")    public DynamicLoopQueue(int arrMaxSize) {        //循环队列需要有意识浪费一个空间        maxSize = arrMaxSize + 1;        data = (E[]) new Object[maxSize];    }        @Override    public boolean isEmpty() {        return front == rear;    }        @Override    public boolean isFull() {        return (rear + 1) % maxSize == front;    }        @Override    public int getCapacity() {        return data.length - 1;    }        @Override    public int getSize() {        return (rear + maxSize - front) % maxSize;    }        @Override    public void add(E e) {        if (isFull()) {            //队满不再进行报错，而是进行动态扩容            resize(getCapacity() * 2);        }        data[rear] = e;        //rear指针后移一位        rear = (rear + 1) % maxSize;    }        @Override    public E poll() {        if (isEmpty()) {            throw new IllegalArgumentException("队列为空，不能出队！");        }        E temp = data[front];        //出队位置置null        data[front] = null;        //front指针后移一位        front = (front + 1) % maxSize;        //当数组实际元素减小到空间的一半的时候，对其进行缩小        //if(size == data.length / 2)                if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {            resize(getCapacity() / 2);        }        return temp;    }        @Override    public E getHead() {        return data[front];    }        @SuppressWarnings("unchecked")    private void resize(int newCapacity) {        E[] newData = (E[]) new Object[newCapacity + 1];        //有多个元素循环多少次        for (int i = 0; i < getSize(); i++) {            //循环队列会发生偏移，重新赋值给新数组            newData[i] = data[(i + front) % data.length];        }        data = newData;        maxSize = data.length;        //重置指针        front = 0;        rear = getSize();    }    @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 != rear; i = (i + 1) % data.length) {            res.append(data[i]);            if ((i + 1) % data.length != rear) {                res.append(", ");            }        }        res.append("] tail");        return res.toString();    }        public static void main(String[] args) {        DynamicLoopQueue<Integer> queue = new DynamicLoopQueue<>(3);        Scanner sc = new Scanner(System.in);        char c;        boolean loop = true;        while (loop) {            System.out.println("s(toString):输出队列");            System.out.println("e(exit):退出程序");            System.out.println("a(add):添加数据到队列");            System.out.println("p(poll):从队列取出数据");            System.out.println("h(getHead):查看队列头的数据");            System.out.println("n(isEmpty):是否队空");            System.out.println("f(isFull):是否队满");            c = sc.next().charAt(0);            switch (c) {                case 's':                    System.out.println("当前队列：" + queue.toString());                    break;                case 'e':                    sc.close();                    loop = false;                    break;                case 'a':                    System.out.println("请输入一个整数");                    queue.add(sc.nextInt());                    break;                case 'p':                    System.out.printf("出队元素：%d\n", queue.poll());                    break;                case 'h':                    System.out.printf("队首元素：%d\n", queue.getHead());                    break;                case 'n':                    System.out.println("队空：" + queue.isEmpty());                    break;                case 'f':                    System.out.println("队满：" + queue.isFull());                    break;                default:                    break;            }        }        System.out.println("程序退出");    }}

关于“Java动态循环队列怎么实现”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。