侧边栏壁纸
博主头像
Sir丶雨轩博主等级

一个90的萌新码农,热爱编程热爱生活 编程交流群:875477818

  • 累计撰写 53 篇文章
  • 累计创建 93 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

用数组实现简单的环形队列

Sir丶雨轩
2021-07-07 / 0 评论 / 2 点赞 / 294 阅读 / 1,163 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-12-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

首先我们定义一个类

class CircleArrayQueue {
}

四个成员变量

// 队列的最大容量
private int maxSize;
// 队列头,指向队列的第一个元素
private int front;
// 队列尾,指向队列最后一个元素的后一个位置
private int rear;
// 队列的数据
private int[] arr;
构造器

// 创建队列的构造器,这里应该还需与给头尾指针赋值,但头尾元素都是0,跟默认值一致就可以省略

public CircleArrayQueue(int maxSize) {
	this.maxSize = maxSize;
	arr = new int[maxSize];
}

判断队列是否为空

// 如果头尾指向相同的位置,就表示这个队列是空的
// rear 指向最后一个元素的后一个位置,由于没有元素,最后一个元素则为-1.在后一个即为0
// front 指向第一个元素 即为0
// 0 == 0 则队列为空

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

判断队列是否已满

// 这里的 rear+1 主要是为了让指针后移,特别是在队列尾部添加数据的时候,本来用rear也可以判断,但是一开始还没加数据的时候,
// 如果直接用rear % maxSize == front,结果是true,所以为了解决指针后*移和判断是否满,用来rear+1。其次,因为rear+1可能会导致数组指针越界,
// 所以用取模来控制它的范 * 围,同时保证他会在一个固定的范围循环变换,也利于环形队列的实现。

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

判断队列是否为空

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

添加数据到队列

// rear指向队列的最后一个元素的后一个位置,如果到达最后一个,则取模从新回到头部
public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满,无法添加数据");
            return;
        }
        // 直接加入数据
        arr[rear] = n;
        // 将rear后移,这里需要考虑取模
        rear = (rear + 1) % maxSize;
    }

获取队列数据

public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列已空,无法获取数据");
        }
        // 这里需要分析出 front是指向队列的第一个元素
        // 1. 先把front对应的值保存到一个临时变量
        // 2. 将front后移,考虑取模
        // 3. 将临时变量返回
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;

    }
2

评论区