Java循环队列

落日映苍穹つ 2024-03-01 08:13 19阅读 0赞

**目录**

一、循环队列

二、设计循环队列

--------------------

## 一、循环队列 ##

**队列：**只能在一端进行插入数据操作，另一端进行删除数据操作的特殊线性表，是一种**先进先出**的存储结构

插入操作的一端为**队尾**，删除操作的一端为**队头**

![4065e9320e884059befa8fcc456d73ef.png][]

![f5f40ef554094dee98f5bd6f1dc33850.png][]

在线性队列中，一旦队列满了，即使队列的前面有空间，我们也不能插入下一个元素，这时，我们可以使用循环队列，来使用这些空间存储新的值

**循环队列：** 队头和队尾相连接的队列

![04b73ab2708a47ce94244590228c355e.png][]

## 二、设计循环队列 ##

我们使用数组来实现循环队列，通过构造器，来创建队列，并设置队列的大小为n

**在创建队列时，我们预留一个空间，以便判断队列满和计算队列元素个数**

**判断循环队列是否为空**

当队头和队尾指向同一位置时，队列是空的

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

**判断循环队列是否已满**

若队尾的下一个位置是队头，那么循环队列已满

![cc46e07cec72400d9a91d2d357dc4ce8.png][]

当rear指向最后一个位置时，+1会造成越界，此时我们通过取余（%），让其指向0位置处

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

**添加数据**

首先判断队列是否已满，若已满，添加失败，返回false，若没有，则在队尾rear位置添加数据，并将rear向后移动

public boolean enQueue(int value) {
        //判断队列是否满
        if(isFull()){
            return false;
        }else {
            elem[rear] = value;
            rear = (rear+1)%size;
            return true;
        }
    }

**删除数据**

首先判断队列是否为空，若为空，删除失败，返回false，若不为空，则将front向后移动

public boolean deQueue() {
            //队列是否为空
            if(isEmpty()){
                return false;
            }else {
                front = (front + 1) % size;
                return true;
            }
        }

**获取队头元素**

首先判断队列是否为空，若为空，队列中无元素，抛出异常，若不为空，返回队头元素，并将front向后移动

public int getFront() {
        if(isEmpty()){
            throw new RuntimeException("队列为空，无元素！");
        }else {
            int val = elem[front];
            front = (front + 1) % size;
            return val;
        }
    }

**计算队列中元素个数**

public int size(){
        return (rear + size - front) % size;
    }

**完整代码**

class MyCircularQueue {
        private int[] elem;
        private int front;
        private int rear;
        private int size;
        public MyCircularQueue(int n) {
            elem = new int[n+1];
            front = rear = 0;
            size = n + 1;
        }
        public boolean isEmpty() {
            return front == rear;
        }
    
        public boolean isFull() {
            return ((rear+1)%size == front);
        }
    
        public boolean enQueue(int value) {
            //判断队列是否满
            if(isFull()){
                return false;
            }else {
                elem[rear] = value;
                rear = (rear+1)%size;
                return true;
            }
        }
    
        public boolean deQueue() {
            //队列是否为空
            if(isEmpty()){
                return false;
            }else {
                front = (front + 1) % size;
                return true;
            }
        }
        public int getFront() {
            if(isEmpty()){
                throw new RuntimeException("队列为空，无元素！");
            }else {
                int val = elem[front];
                front = (front + 1) % size;
                return val;
            }
        }
        public int size(){
            return (rear + size - front) % size;
        }
    }

[4065e9320e884059befa8fcc456d73ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/8a2d2735a25842f7a0e6f1136b3863c6.png
[f5f40ef554094dee98f5bd6f1dc33850.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/211bbc2a618b4a759525169372bd81ce.png
[04b73ab2708a47ce94244590228c355e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/3774345721744fe8bdb933219c5873fa.png
[cc46e07cec72400d9a91d2d357dc4ce8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/19578a9f3e26445793ac1df0496838d8.png