Java 数组实现队列

队列，一种比较直观的数据结构，遵循先进先出的原则。更具体的就不展开介绍了，这里给出一个简单的实现。

环形队列

import java.util.Arrays;
import java.util.StringJoiner;

public class ArrayCycleQueue<Z> {

    private int front; // index of the first element's index;
    private int rear; // index of the last element's index+1;
    private final int maxSize;
    private final Object[] array;

    public ArrayCycleQueue(int maxSize) {
        this.maxSize = maxSize;
        array = new Object[maxSize];
        front = 0;
        rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public int capacity() {
        return maxSize - 1;
    }
    
    public int size() {
    // 4,0  0,1  1,2  2,3  2,4->4  2,1 ->1
//        return rear == front ? 0
//                : rear > front
//                ? rear - front
//                : rear + maxSize - front;
    return (rear + maxSize - front) % maxSize;
}

    public boolean isFull() {
//        return rear > front
//                ? (rear == maxSize - 1 && front == 0)
//                : rear == front - 1;
        // 4,0  0,1  1,2  2,3
        return (rear + 1) % maxSize == front;
    }

    public boolean put(Z data) {
        if (isFull()) {
            return false;
        }
        array[rear] = data;
        rear = (rear + 1) % maxSize;
        return rear < maxSize;
    }

    public Z take() {
        if (isEmpty()) {
            return null;
        }
        Z data = (Z) array[front];
        array[front] = null;
        front = (front + 1) % maxSize;
        return data;
    }
    
    public void show() {
        StringBuilder sb = new StringBuilder(getClass().getSimpleName() + ": {");
        int fp = front;
        while (fp != rear) {
            Z data = (Z) array[fp];
            sb.append("arr[").append(fp).append("] -> ").append(data)
                    .append(", ");
            fp = (fp + 1) % maxSize;
        }
        int last = sb.lastIndexOf(",");
        if (last != -1) {
            sb.delete(last, last + 2);
        }
        sb.append("}").append("\n\t").append(this);
        System.out.println(sb);
    }

    @Override
    public String toString() {
        return new StringJoiner(", ",
                ArrayQueue.class.getSimpleName() + "[", "]")
                .add("front=" + front)
                .add("rear=" + rear)
                .add("maxSize=" + maxSize)
                .add("array=" + Arrays.toString(array))
                .toString();
    }

    public static void main(String[] args) {
        ArrayCycleQueue<Integer> queue = new ArrayCycleQueue<>(5);
        int num = 1;
        System.out.println("'''''''''''''''''''''''''");
        while (!queue.isFull()) {
            queue.put(num++);
            System.out.println("loop to put: " + queue);
        }
        System.out.println("------------");
        while (!queue.isEmpty()) {
            System.out.println("--### in loop-- " + queue.take() + ",,," + queue);
        }

        System.out.println("'''''''''''''''''''''''''xxx");
        while (!queue.isFull()) {
            queue.put(num++);
            System.out.println("loop to put: " + queue);
        }
        System.out.println("------------xxx");
        while (!queue.isEmpty()) {
            System.out.println("--### in loop-- " + queue.take() + ",,," + queue);
        }


        System.out.println("'''''''''''''''''''''''''yyy");
        while (!queue.isFull()) {
            queue.put(num++);
            System.out.println("loop to put: " + queue);
        }
        System.out.println("------------yyy");
        while (!queue.isEmpty()) {
            System.out.println("--### in loop-- " + queue.take() + ",,," + queue);
        }
    }
}

为了方便观察和验证正确性，添加了 toString 和 main 方法。（可选）

输出如下：

'''''''''''''''''''''''''
loop to put: ArrayQueue[front=0, rear=1, maxSize=5, array=[1, null, null, null, null]]
loop to put: ArrayQueue[front=0, rear=2, maxSize=5, array=[1, 2, null, null, null]]
loop to put: ArrayQueue[front=0, rear=3, maxSize=5, array=[1, 2, 3, null, null]]
loop to put: ArrayQueue[front=0, rear=4, maxSize=5, array=[1, 2, 3, 4, null]]
------------
--### in loop-- 1,,,ArrayQueue[front=1, rear=4, maxSize=5, array=[null, 2, 3, 4, null]]
--### in loop-- 2,,,ArrayQueue[front=2, rear=4, maxSize=5, array=[null, null, 3, 4, null]]
--### in loop-- 3,,,ArrayQueue[front=3, rear=4, maxSize=5, array=[null, null, null, 4, null]]
--### in loop-- 4,,,ArrayQueue[front=4, rear=4, maxSize=5, array=[null, null, null, null, null]]
'''''''''''''''''''''''''xxx
loop to put: ArrayQueue[front=4, rear=0, maxSize=5, array=[null, null, null, null, 5]]
loop to put: ArrayQueue[front=4, rear=1, maxSize=5, array=[6, null, null, null, 5]]
loop to put: ArrayQueue[front=4, rear=2, maxSize=5, array=[6, 7, null, null, 5]]
loop to put: ArrayQueue[front=4, rear=3, maxSize=5, array=[6, 7, 8, null, 5]]
------------xxx
--### in loop-- 5,,,ArrayQueue[front=0, rear=3, maxSize=5, array=[6, 7, 8, null, null]]
--### in loop-- 6,,,ArrayQueue[front=1, rear=3, maxSize=5, array=[null, 7, 8, null, null]]
--### in loop-- 7,,,ArrayQueue[front=2, rear=3, maxSize=5, array=[null, null, 8, null, null]]
--### in loop-- 8,,,ArrayQueue[front=3, rear=3, maxSize=5, array=[null, null, null, null, null]]
... yyy 里面的输出没有贴上...

简单说明一下实现逻辑：

因为是数组，所以长度是固定的；
定义索引值 front, 指向队列的第一个元素；
定义索引值 rear 最后一个元素的后面一个位置;

因为是要实现环形的效果，所以这个 rear 不是随着数据增加去无脑执行 rear++ 的操作的，因为数组的长度是固定的，一直 ++ 会导致数组越界；在取出数据的时候，front 也会往后移动，这样一来，数组前面的位置被腾空了，这些位置可以利用起来用于存放数据；想象一下，把数组从一个长方形弯成一个头尾相连接的环形，这样前面的被腾空的位置可以看成rear 后面的位置，这样就可以继续寸数据了，基于这种思路，就可以去实现环形数组了。

上面的代码只是一种实现方案，但不是唯一的实现方案。

非环形队列

下面再给一种非环形的，也是可以一直复用当前数组的实现方案；这种的思路就是，一旦队列为空，就把 rear 和 front 重置为初始化时候的状态。（这种实现更简单，也更容易理解）

import java.util.Arrays;
import java.util.StringJoiner;

/**
 * 使用数组实现定长队列;(非环形，可复用队列)
 * @param <Z>
 */
public class ArrayQueue<Z> {
    private int front;
    private int rear;
    private final int maxSize;
    private final Object[] array;

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        array = new Object[maxSize];
        front = 0;
        rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public int capacity() {
        return maxSize;
    }
    
    public int size() {
        return rear - front;
    }

    public boolean isFull() {
        return rear == maxSize;
    }

    public boolean put(Z data) {
        if (isFull()) {
            return false;
        }
        array[rear] = data;
        rear++;
        return rear <= maxSize;
    }

    public Z take() {
        if (isEmpty()) {
            return null;
        }
        Z data = (Z) array[front];
        array[front] = null;
        front++;
        resetIndex();
        return data;
    }

    private void resetIndex() {
        if (front == rear && rear != 0) {
            front = rear = 0;
        }
    }

    @Override
    public String toString() {
        return new StringJoiner(", ",
                ArrayQueue.class.getSimpleName() + "[", "]")
                .add("front=" + front)
                .add("rear=" + rear)
                .add("maxSize=" + maxSize)
                .add("array=" + Arrays.toString(array))
                .toString();
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);
        queue.put(4);
        queue.put(5);
        System.out.println(queue);
        System.out.println(queue.take());
        System.out.println(queue);
        System.out.println(queue.take());
         System.out.println(queue.take());
        queue.put(6);
        System.out.println("6---- " + queue);
        queue.put(7);
        queue.put(8);
        queue.put(9);
        queue.put(10);
        queue.put(11);
        System.out.println(queue);
    }
}

输出如下：

ArrayQueue[front=0, rear=2, maxSize=5, array=[4, 5, null, null, null]]
4
ArrayQueue[front=1, rear=2, maxSize=5, array=[null, 5, null, null, null]]
5
null
6---- ArrayQueue[front=0, rear=1, maxSize=5, array=[6, null, null, null, null]]
ArrayQueue[front=0, rear=5, maxSize=5, array=[6, 7, 8, 9, 10]]

两种的输出效果其实是不同的，因为环形的起始位置是一直在变的，而非环形的永远是 0 .

原文链接：https://blog.csdn.net/DucklikeJAVA/article/details/124053764

你可能也喜欢