循环队列和循环双端队列

循环队列:

通过一个数组进行模拟

//设计循环队列
class MyCircularQueue {

    private int[] elements;  //一个固定大小的数组，用于保存循环队列的元素。
    private int capacity;    //循环队列的容量，即队列中最多可以容纳的元素数量。
    private int front;       //队列首元素对应的数组的索引。
    private int rear;        //队列尾元素对应的索引的下一个索引。


    //初始化队列;
    public MyCircularQueue(int k) {
        elements = new int[k + 1];
        capacity = k + 1;
        front = 0;
        rear = 0;
    }


    //在队列的尾部插入一个元素
    public boolean enQueue(int value) {
        //如果队列满了则,直接返回false;
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    //从队首取出一个元素
    public boolean deQueue() {
        //如果队列为空的话,直接返回false;
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    //返回队首的元素
    public int Front() {
        //如果队列为空的话,直接返回-1;
        if (isEmpty()) {
            return -1;
        }
        return elements[front];

    }

    //返回队尾的元素
    public int Rear() {
        //如果队列为空的话,直接返回-1;
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];

    }

    //检测队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    //检测队列是否已满
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

循环双端队列:

循环双端队列其实就是一个双端队列，即可以在队头和队尾都进行入队或者出队操作的队列。

//设计循环双端队列;
public class MyCircularDeque {

    private int[] elements;  //一个固定大小的数组，用于保存循环队列的元素。
    private int capacity;    //循环队列的容量，即队列中最多可以容纳的元素数量。
    private int front;       //队列首元素对应的数组的索引。
    private int rear;        //队列尾元素对应的索引的下一个索引。


    //初始化队列
    public MyCircularDeque(int k) {
        elements = new int[k + 1];
        capacity = k + 1;
        front = 0;
        rear = 0;
    }

    //队列未满时，在队首插入一个元素
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        elements[front] = value;
        return true;
    }

    //队列未满时，在队列的尾部插入一个元素
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    //队列不为空时，从队首删除一个元素，并同时将队首的索引front更新为 (front + 1 + capacity) % capacity;
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    //队列不为空时，从队尾删除一个元素。并同时将队尾的索引rear更新为 (rear + capacity - 1) % capacity;
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    //返回队首的元素
    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    //返回队尾的元素
    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    //检测队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    //检测队列是否已满
    public boolean isFull() {
        return front == (rear + 1) % capacity;
    }

}