基于Java数组实现循环队列的两种方法小结

接下来详细讲解一下“基于Java数组实现循环队列的两种方法小结”的内容。

标题

基于Java数组实现循环队列的两种方法小结

简介

在队列的实现中，循环队列是一种比较常用的方式。本文主要介绍了基于Java数组实现循环队列的两种方法，包括普通循环队列和双端循环队列。

普通循环队列实现

普通循环队列的实现思路是利用数组来存储队列元素，通过两个指针front和rear来记录队头和队尾，当队列满时可以覆盖最开始的元素。以下是基于Java数组实现普通循环队列的代码：

public class MyCircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;

    public MyCircularQueue(int k) {
        data = new int[k];
        front = -1;
        rear = -1;
        size = k;
    }

    public boolean enQueue(int val) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            front = 0;
        }
        rear = (rear + 1) % size;
        data[rear] = val;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (front == rear) {
            front = -1;
            rear = -1;
            return true;
        }
        front = (front + 1) % size;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[front];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[rear];
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return (!isEmpty() && (rear + 1) % size == front);
    }
}

示例说明一

创建一个容量为3的循环队列，并往里面添加3个元素。

MyCircularQueue queue = new MyCircularQueue(3);
queue.enQueue(1); // true
queue.enQueue(2); // true
queue.enQueue(3); // true
queue.enQueue(4); // false

示例说明：在循环队列容量为3时，添加4个元素，当添加第四个元素时，返回false。

示例说明二

创建一个容量为3的循环队列，并往里面添加2个元素，再移除一个元素。

MyCircularQueue queue = new MyCircularQueue(3);
queue.enQueue(1); // true
queue.enQueue(2); // true
queue.deQueue(); // true
queue.enQueue(3); // true

示例说明：在循环队列容量为3时，先添加2个元素，再移除一个元素，最后再添加一个元素，队列已经满了。

双端循环队列实现

双端循环队列是在普通循环队列的基础上，增加了可以在队列的两端插入或删除元素的操作。以下是基于Java数组实现双端循环队列的代码：

public class MyCircularDeque {
    private int[] data;
    private int front;
    private int rear;
    private int size;

    public MyCircularDeque(int k) {
        data = new int[k + 1];
        front = 0;
        rear = 0;
        size = k + 1;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + size) % size;
        data[front] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        data[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % size;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + size) % size;
        return true;
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return data[front];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return data[(rear - 1 + size) % size];
    }

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

    public boolean isFull() {
        return (rear + 1) % size == front;
    }
}

示例说明一

创建一个容量为3的双端循环队列，并往里面添加3个元素。

MyCircularDeque deque = new MyCircularDeque(3);
deque.insertLast(1); // true
deque.insertLast(2); // true
deque.insertFront(3); // true
deque.insertFront(4); // false

示例说明：在双端循环队列容量为3时，添加4个元素，当添加第四个元素时，返回false。

示例说明二

创建一个容量为3的双端循环队列，并往里面添加2个元素，再从两端移除一个元素。

MyCircularDeque deque = new MyCircularDeque(3);
deque.insertLast(1); // true
deque.insertFront(2); // true
deque.deleteLast(); // true
deque.deleteFront(); // true

示例说明：在双端循环队列容量为3时，先从两端各添加一个元素，再从两端各移除一个元素，队列已经为空。

总结

本文主要介绍了基于Java数组实现循环队列的两种方法，包括普通循环队列和双端循环队列。通过示例说明，介绍了它们的基本用法，希望能够帮助到读者。