数据结构 实现循环队列的三种方法

队列（Queue）可以通过顺序结构实现，也可以通过链式结构实现。本文将讲解如何通过顺序结构实现队列，要通过顺序结构实现队列，通常建议使用循环队列的方式，也就是使用循环数组，它解决了普通数组实现队列时的空间浪费问题，同时保证了入队和出队操作的高效性（均为 O (1) 时间复杂度）。

循环队列的核心思想：循环队列通过将数组视为一个环形结构，当队尾指针到达数组末尾时，会绕回数组的起始位置，从而充分利用数组空间。

每有一个元素入队列，rear就移动到下一个位置，front的位置不变；每有一个元素出队列，front就移动到下一个位置，rear的位置不变。

不过这里唯一的问题是：怎么判断队列满和空？

对于空的情况：主要队列头和队列尾相遇，就是空的。

对于满的情况：

我们有三种做法：

1.定义一个size用于储存队列元素的个数；

2.添加标记，定义一个boolean类型变量，当队列头和队列尾相遇并且这个标记发生改变了，就说明满了；

3.浪费一个空间，当队列尾的下一个位置如果是队列头，那么就说明满了。

队列的常见方法：

public class MyCircularQueue {private int[] arr;private int front;private int rear;private int size;//构造方法public MyCircularQueue() {}//入队列public int enQueue(int data) {}//出队列public int deQueue() {}//从队首获取元素。如果队列为空，返回 -1 。public int Front() {}//获取队尾元素。如果队列为空，返回 -1 。public int Rear() {}//检查循环队列是否为空public boolean isEmpty() {}//检查循环队列是否已满public boolean isFull() {}
}

那么，接下来就分别用这三种方法实现循环队列。

1.方法一：定义size用于储存队列元素个数

构造方法

//构造方法public MyCircularQueue(int k) {this.arr = new int[k];}

检查循环队列是否已满

当front与rear相遇，并且size == 数组长度时，我们可以认为队列满了。

//检查循环队列是否已满public boolean isFull() {return (this.front == this.rear) && (this.size == this.arr.length);}

检查循环队列是否为空

当front与rear相遇时，此时并没有size == 数组长度，那么就说明队列是空的。

//检查循环队列是否为空public boolean isEmpty() {return this.front == this.rear;}

入队列

进行入队列操作前，需要先判断队列满了没有，如果满了，就返回-1，没满就正常入队列并且返回data。不过需要注意的是，rear移动到下一个位置不能简单的++，否则会造成越界访问，应当这样操作：rear = (rear + 1) % arr.length，这样就能是它实现循环。

//入队列public int enQueue(int data) {if (isFull()) {return -1;}this.arr[this.rear] = data;this.rear = (this.rear + 1) % this.arr.length;this.size++;return data;}

出队列

进行出队列操作前，需要先判断队列是不是空的，如果是，就返回-1，不是就正常出队列并且返回队头元素。这里需要注意front的移动，与rear的移动一样。

//出队列public int deQueue() {if (isEmpty()) {return -1;}int val = this.arr[this.front];this.front = (this.front + 1) % this.arr.length;this.size--;return val;}

从队首获取元素。如果队列为空，返回 -1 。

//从队首获取元素。如果队列为空，返回 -1 。public int Front() {if (isEmpty()) {return -1;}return this.arr[this.front];}

获取队尾元素。如果队列为空，返回 -1 。

这里需要注意，与获取队首元素有点区别，就是rear的位置，我们不能直接通过return arr[rear - 1] 去获取队尾元素，因为当rear位于0位置时，rear - 1 = -1，这是不合法的！因此我们需要对这两种情况分别处理。

//获取队尾元素。如果队列为空，返回 -1 。public int Rear() {if (isEmpty()) {return -1;}int index;if (this.rear == 0) {index = this.arr.length - 1;}else {index = this.rear - 1;}return this.arr[index];}

到此，我们就使用方法一实现了循环队列。完整代码如下：

/*** Created with IntelliJ IDEA.* Description:* User: mirac* Date: 2025-08-16* Time: 18:05*/
public class MyCircularQueue {private int[] arr;private int front;private int rear;private int size;//构造方法public MyCircularQueue(int k) {this.arr = new int[k];}//入队列public int enQueue(int data) {if (isFull()) {return -1;}this.arr[this.rear] = data;this.rear = (this.rear + 1) % this.arr.length;this.size++;return data;}//出队列public int deQueue() {if (isEmpty()) {return -1;}int val = this.arr[this.front];this.front = (this.front + 1) % this.arr.length;this.size--;return val;}//从队首获取元素。如果队列为空，返回 -1 。public int Front() {if (isEmpty()) {return -1;}return this.arr[this.front];}//获取队尾元素。如果队列为空，返回 -1 。public int Rear() {if (isEmpty()) {return -1;}int index;if (this.rear == 0) {index = this.arr.length - 1;}else {index = this.rear - 1;}return this.arr[index];}//检查循环队列是否为空public boolean isEmpty() {return this.front == this.rear;}//检查循环队列是否已满public boolean isFull() {return (this.front == this.rear) && (this.size == this.arr.length);}
}

其实这三种方法都是大同小异的，只不过判断队列空和满的条件不一样罢了，因此使用方法二和方法三实现循环队列就不再过多赘述。

2.方法二：添加标记

package demo;public class MyCircularQueue {private int[] arr;private int front;private int rear;private boolean mark = true;//构造方法public MyCircularQueue(int k) {this.arr = new int[k];}//入队列public int enQueue(int data) {if (isFull()) {return -1;}this.arr[this.rear] = data;this.rear = (this.rear + 1) % this.arr.length;//如果本次入队列使得front与rear相遇的话，使标记发生改变if (this.rear == this.front) {this.mark = false;}return data;}//出队列public int deQueue() {if (isEmpty()) {return -1;}int val = this.arr[this.front];this.front = (this.front + 1) % this.arr.length;this.mark = true;return val;}//从队首获取元素。如果队列为空，返回 -1 。public int Front() {if (isEmpty()) {return -1;}return this.arr[this.front];}//获取队尾元素。如果队列为空，返回 -1 。public int Rear() {if (isEmpty()) {return -1;}int index;if (this.rear == 0) {index = this.arr.length - 1;}else {index = this.rear - 1;}return this.arr[index];}//检查循环队列是否为空public boolean isEmpty() {return this.front == this.rear;}//检查循环队列是否已满public boolean isFull() {return (this.front == this.rear) && (this.mark == false);}
}

解释：方法二不再定义用于记录队列元素的size，而是定义一个标记位mark。mark的初始值为true，当front与rear相遇，并且mark发生改变了，就说明队列满了；仅仅front与rear相遇，就说明队列是空的。mark发生改变的2处地方：1.入队列：若队列未满，并且成功入队列后，如果rear移动后的位置 == front的位置，那么mark就发生改变，mark = false。2.出队列：若队列不空，并且成功出队列后，不管怎么样，mark = true。

3.方法三：浪费一个空间

package demo1;public class MyCircularQueue {private int[] arr;private int front;private int rear;//构造方法public MyCircularQueue(int k) {this.arr = new int[k + 1];}//入队列public int enQueue(int data) {if (isFull()) {return -1;}this.arr[this.rear] = data;this.rear = (this.rear + 1) % this.arr.length;return data;}//出队列public int deQueue() {if (isEmpty()) {return -1;}int val = this.arr[this.front];this.front = (this.front + 1) % this.arr.length;return val;}//从队首获取元素。如果队列为空，返回 -1 。public int Front() {if (isEmpty()) {return -1;}return this.arr[this.front];}//获取队尾元素。如果队列为空，返回 -1 。public int Rear() {if (isEmpty()) {return -1;}int index;if (this.rear == 0) {index = this.arr.length - 1;}else {index = this.rear - 1;}return this.arr[index];}//检查循环队列是否为空public boolean isEmpty() {return this.front == this.rear;}//检查循环队列是否已满public boolean isFull() {return (this.rear + 1) % this.arr.length == this.front;}
}

解释：方法三不需要size，也不需要mark，它通过浪费一个空间来判断空与满，这实际上是一种变相的标记位，它判断队列满的条件为：当rear的下一个位置 == front的位置时，就说明队列满了。需要注意的是，因为我们浪费了一个空间作为标记位，因此在构造方法中，数组的容量应当是 k + 1。

到此，三种实现循环队列的方法已经一一罗列，感谢您的观看，如有错误，还请指出，欢迎讨论！