1. 循环队列

1.1 循环队列

在这里插入图片描述

特殊的队列，首尾相连，空间可重复利用；
环形队列常使用数组实现，且为了方便队列的判空、判满处理，会浪费一个大小的空间，该空间不存储元素，比如待存储元素共n个，则开辟大小为n+1的数组实现循环队列；
循环队列，判空：head=tail；判满：(tail+1)%arr.length=head；
head、tail分别为头指针、尾指针，初始化时均指向index=0位置；
head指向队头元素，tail指向队尾元素的下一个位置；
元素出队时，front_val=arr[head]；
元素入队时，arr[tail]=val、tail=(tail+1)%n；
队尾元素位置为：lastIndex=(tail-1+n)%n；
队列中有效元素下标为：[head,lastIndex]；

初始化，队列为空：
在这里插入图片描述

队列满：
在这里插入图片描述

涉及到下标移动，有两个计算公式，其中offset=offset%arr.length：
1）下标最后再往后(offset 小于 array.length): index = (index + offset) % arr.length；
2）下标最前再往前(offset 小于 array.length): index = (index + arr.length - offset) % arr.length；

1.2 代码实现

public class LoopQueue{
    // 队列：存储数据
    private int[] data;
    // 队列实际长度，其中1个位置不存储数据
    private int n;
    // 头指针、尾指针
    private int head,tail;

    public LoopQueue(int size){
        data=new int[size+1];
        n=data.length;
        head=0;
        tail=0;
    }
    public boolean isEmpty() {
        return head==tail;
    }

    public boolean isFull() {
        return (tail+1)%n==head;
    }
    // 入队操作
    public boolean offer(int val) {
        if (isFull()){
            return false;
        }
        data[tail]=val;
        tail=(tail+1)%n;
        return true;
    }

    // 出队操作
    public int poll() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空，无法进行出队操作！");
        }
        int val=data[head];
        head=(head+1)%n;
        return val;
    }

    // 获取队头元素
    public int peek() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空，无法获取队头元素！");
        }
        return data[head];
    }

    // 遍历队列
    @Override
    public String toString() {
        StringBuilder content=new StringBuilder("[");
        int i=head;
        while (i!=tail){
            content.append(data[i]);
            if (i!=tail-1){
                content.append(",");
            }
            i=(i+1)%n;
        }
        content.append("]");
        return content.toString();
    }
}

1.3 力扣622. 设计循环队列

622. 设计循环队列
设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

class MyCircularQueue {
    int[] queue;
    int head;
    int tail;
    int n;
    public MyCircularQueue(int k) {
        queue=new int[k+1];
        head=0;
        tail=0;
        n=queue.length;
    }

    public boolean enQueue(int value) {
        if (isFull()){
            return false;
        }
        queue[tail]=value;
        tail=(tail+(1%n))%n;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()){
            return false;
        }
        head=(head+1)%n;
        return true;
    }

    public int Front() {
        if (isEmpty()){
            return -1;
        }
        int val=queue[head];
        return val;
    }

    public int Rear() {
        if (isEmpty()){
            return -1;
        }
        int val=queue[(tail-1+n)%n];
        return val;
    }

    public boolean isEmpty() {
        return head==tail;
    }

    public boolean isFull() {
        return (tail+1)%n==head;
    }
}