线性表——循环队列

1、从“顺序队列”到“循环队列”

**虽然队列（Queue）最好是使用链表来实现，但其实队列底层也可以用动态数组来实现，**并且各接口的时间复杂度也可以优化到O(1)。

1.1、顺序队列

如果我们直接使用动态数组来实现队列，那么入队操作时：在动态数组尾部添加元素，时间复杂度为O(1)；出队操作时：删除动态数组头节点元素，后续节点元素从前往后依次前移一位，时间复杂度为O(n)。

为了优化使用动态数组实现的队列，降低它在元素出队时的时间复杂度。我们使用两个指针（front和rear）分别指向数组中存放的第一个元素和最后一个元素的下一个位置。其中：

• front指针指向第一个元素，被称为队头指针；
• rear指针指向最后一个元素的下一个位置（front+size），被称为队尾指针。

注：

• front和rear的初值在队列初始化时均应置为0；
• 入队时将新元素插入rear所指的位置，然后将rear加1；
• 出队时，删去front所指的元素，然后将front加1并返回被删元素。

由此可见：

• 当头尾指针相等时队列为空。
• 在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。

经过上述优化，队列的出队操作的时间复杂度也降为O(1)。这种基于数组实现并经过性能优化之后的队列我们称为“顺序队列”。

1.2、“假溢出”现象

当我们直接使用顺序队列时可能产生“假溢出”现象。

在普通顺序队列中，入队时将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。

像这样进行了一定数量的入队和出队操作后，可能会出现这样的情况：尾指针rear已指到数组的最后一个元素。此时若再执行入队操作，便会出现队满“溢出”。然而，由于在此之前可能也执行了若干次出队操作。因而数组的前面部分可能还有很多闲置的元素空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为**“假溢出”**。

因此，我们必须要解决顺序队列“假溢出”的问题，否则顺序队列就没有太多使用价值。

1.3、循环队列（CircleQueue）

为充分利用数组的内存空间，克服上述“假溢出”现象。我们可以将向量（泛型数组）空间想象为一个首尾相接的圆环，并称这种向量为循环向量。在原有顺序队列的基础上，如果数组的尾部满了，那么就从数组的头部开始依次插入，以达到重复利用空间的效果。这种基于数组实现并且被优化之后的队列，我们称作**“循环队列”**（CircleQueue）。

因此：

• 循环队列是基于数组实现的。
• 循环队列是存储在循环向量中的。
• 循环队列内部的元素是顺序存储的。
• 循环队列的首尾元素未必相连，是个逻辑上的循环。
• 循环队列本质上还是一个普通的队列。

**注：**由于循环队列的设计思维更像一个环，因此常使用一个环图来表示，但注意其不是一个真正的环，而是一个逻辑上的环。

与普通队列一样，循环队列：

（1）元素出入特点：

• 它也只能在队尾入队（添加元素）

• 它也只能在队头出队（删除元素）。

（2）元素出入原则：先进先出。

2、循环队列的设计

2.1、类的结构设计

在编程之前，我们需要先对循环队列类（CircleQueue）的结构进行设计。如下图所示：

循环队列类需要的成员主要包括：

• 循环队列存放元素的数量。

  private int size;

  size = 元素（Element）数目 = 循环队列长度 ≤ 循环队列容量（capacity）。

• 用来存放循环队列的泛型数组变量。

  private E[] elements;

  **注：**循环队列是存储在循环向量中的。

• 队头指针

  private int front;

  **注：**队尾指针rear我们可以不定义为成员变量。因为rear =（front + size）%capacity始终成立。

• 构造函数（有形参、无形参）

  通过构造函数，我们可以在新建循环队列时对其容量（capacity）进行初始化。一方面，我们要构建一个带形参的构造函数，让用户自定义循环队列的容量；另一方面，我们还要构建一个无形参的构造函数，用来处理用户未定义循环队列的容量时的情况。

• 析构函数（Java语言没有）

• 接口函数

2.2、接口设计

循环队列（CircleQueue）的接口与队列（Queue）的接口完全一样。

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• void enQueue (E element); //入队
• E deQueue (); //出队
• E front(); //获取队列的头元素
• void clear(); //清空队内元素

3、循环队列的实现

3.1、编程实现

在之前队列和双端队列项目的基础上：

①再新建一个名称为CircleQueue（包名为：com.atangbiji）的类，用来自己实现循环队列；

②仍然使用名称为Main（包名为：com.atangbiji）的类，来调用（测试）自己封装的循环队列。

③接口实现，我们这里直接考虑循环队列内部元素均为泛型的情况。

（1）定义私有成员变量

CircleQueue.java文件：

package com.atangbiji;

public class CircleQueue<E> {	
	private int size;	//循环队列存放元素的数量
	private E[] elements;	//用来存放循环队列的泛型数组变量
	private int front;	//队头指针
}

**注：**队头指针front为int类型，它存储的是队内元素在数组中的秩。此外，Java中未赋值的整形默认值为0。

（2）创建构造函数

CircleQueue.java文件：

private static final int DEFAULT_CAPACITY =  10; //默认容量
/*
 * 构造函数
 * @param capacity初始容量
 * @return
 * */
@SuppressWarnings("unchecked")//注解
public CircleQueue(int capacity) {
	capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;//边界条件处理
	elements = (E[]) new Object[capacity];//创建循环队列
}
public CircleQueue() {
	this(DEFAULT_CAPACITY);//调用有形参的构造函数
}

**在构造函数中创建循环队列。**当用户自定义循环队列的容量时，调用带形参的构造函数，系统创建容量为capacity的循环队列；当用户未定义循环队列的容量时，调用无形参的构造函数，系统创建容量为默认值的循环队列。

注：

• 我们将默认容量设置为私有静态常量DEFAULT_CAPACITY。其中：

  • static为静态，保证变量的值只有一份；
  • final为常量，类似于C++中的const。

• Java中构造函数间的相互调用使用this对象完成。

• 若用户自定义容量小于默认值，我们这里仍然创建一个默认容量的循环队列。

**注：**此时会有一个警告。按“Ctrl + 1”键，在弹出菜单中选择uncheck选项，此时系统便自动生成@SuppressWarnings("unchecked")注解。

（3）实现size()接口

CircleQueue.java文件：

/*
 * 循环队列中元素的数量
 * @param
 * @return 
 * */
public int size() {
	//直接返回size成员变量即可
	return size;
}

（4）实现isEmpty()接口

CircleQueue.java文件：

/*
 * 循环队列是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	return size == 0;	//size为0为空，否则不为空
}

（5）★ 实现enQueue(E element)接口

a. 当size < capacity时

此时，循环队列未溢出，新元素入队只需：

①获取队尾指针位置；

②将新元素插入rear所指的位置；

③size自增。

注：rear =（front +size）% capacity始终成立。

CircleQueue.java文件：

/*
 * 入队
 * @param
 * @return 
 * */
public void enQueue(E element) {
	
	int capacity = elements.length;		//循环队列的容量
	//获取队尾指针位置
	int rear = (front + size) % capacity;	
	//将新元素插入rear所指的位置
	elements[rear] = element;	
	//size自增
	size++;
}

b. 当size = capacity时——扩容

与动态数组类似，当size=capacity（循环队列空间用完）时，如果我们需要再添加新的元素，那么就必须先对循环队列进行扩容。由于内存是在新建对象的时候就已经明确了的，我们是不能直接在原有数组的后面任意拼接一块新内存用来放新元素的。

此时我们的做法是：

①重新开辟一块更大的（如：1.5倍）内存空间；

②将之前的队内元素从队头到队尾逐一移到新的内存（注意元素移动顺序）；

③让用来存放数组的成员elements指向新的内存空间；

④重置队头指针；

⑤将之前的数组内存释放（Java垃圾自动回收）。

因此，我们需要对enQueue(E element)接口做如下修改。

CircleQueue.java文件：

/*
 * 入队
 * @param
 * @return 
 * */
public void enQueue(E element) {
	
	//确保容量充足
	ensureCapacity(size + 1);
	
	int capacity = elements.length;		//循环队列的容量
	//获取队尾指针位置
	int rear = (front + size) % capacity;	
	//将新元素插入rear所指的位置
	elements[rear] = element;	
	//size自增
	size++;
}
	
/*
 * 保证要有capacity的容量
 * @param: capacity
 * @return
 * */

@SuppressWarnings("unchecked")//注解
private void ensureCapacity(int capacity) {
	
	//若原数组容量够用，则返回
	int oldCapacity = elements.length;
	if(oldCapacity >= capacity)
		return;
	//若原数组容量不够用，则扩容1.5倍
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	//开辟新的内存空间
	E[] newElements = (E[]) new Object[newCapacity];
	//将之前的队内元素从队头到队尾逐一移到新的内存
	for (int i = 0; i < size; i++) {
		newElements[i] = elements[(front + i) % elements.length];//注意是从之前循环队列的队头开始移
	}
	//指向新内存
	elements = newElements;
	
	System.out.println("容量已从 " + oldCapacity + " 扩充到  " + newCapacity);
	
	//重置队头指针
	front = 0;
}

（6）实现deQueue()接口

循环队列出队，只需：

①获取队头元素；

②清空旧的队头；

③队头指针向后移一位；

④ size自减。

**注：**注意队头是数组最后一个元素时的情况。

CircleQueue.java文件：

/*
 * 出队
 * @param
 * @return 
 * */
public E deQueue() {

	//获取队头元素
	E frontElement = elements[front];
	//清空旧的队头
	elements[front] = null;
	//队头指针向后移一位
	front = (front + 1) % (elements.length);
	//size自减
	size--;
	
	return frontElement;
}

（7）实现front()接口

CircleQueue.java文件：

/*
 * 获取循环队列的头元素
 * @param
 * @return 
 * */
public E front() {
	return elements[front];	//直接返回队头指针所指向的元素即可
}

（8）实现clear ()接口

CircleQueue.java文件：

/*
 * 清空队内元素
 * @param
 * @return 
 * */
public void clear() {
	//清空数组中的所有元素（循环队列未使用的空间也清空了）
	for (int i = 0; i < elements.length; i++) {
		elements[i] = null;
	}
	//重置队头指针
	front = 0;
	size = 0;
}

（9）打印数组（循环向量）中的所有元素

为了更加直观地展示循环队列在数组（循环向量）中的存储位置，我们可以将数组（循环向量）中的所有元素打印出来。

在Java中，当我们要打印某一个对象时，系统内部其实是通过调用toString()方法来实现的。默认情况下，打印的该对象的类名。为了打印对象数组中的所有元素，我们只需重写（也称覆盖）toString()方法，并在其中完成字符串的拼接即可。

注：Java中字符串拼接建议使用StringBuilder类。

CircleQueue.java文件：

/*
 * 打印数组（循环向量）中的所有元素：重载toString()函数
 * @param
 * @return 数组元素
 * */
@Override
public String toString() {
	//新建StringBuilder
	StringBuilder string = new StringBuilder();
	
	//拼接字符串
	int capacity = elements.length;
	string.append("循环队列的容量 capacity = ").append(capacity).append("; 循环队列的长度 size = ").append(size).append("; front = ").append(front).append("; [");
	for (int i = 0; i < capacity; i++) {
		string.append(elements[i]);
		
		if (i != capacity - 1) {
			string.append(", ");
		}
	}
	string.append("]");
	
	return string.toString();
}

3.2、接口测试

在Main类（Main.java文件）中新建一个CircleQueue对象，用来测试自己封装的循环队列。这里仅以入队和出队接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		CircleQueue<Integer> circleQueue = new CircleQueue<Integer>();
		
		for (int i = 0; i < 10; i++) {
			circleQueue.enQueue(i);
		}
		System.out.println(circleQueue);
		
		for (int i = 0; i < 5; i++) {
			circleQueue.deQueue();
		}
		System.out.println(circleQueue);
		
		for (int i = 20; i < 25; i++) {
			circleQueue.enQueue(i);
		}
		System.out.println(circleQueue);
		
		for (int i = 0; i < 2; i++) {
			circleQueue.deQueue();
		}
		System.out.println(circleQueue);
		
		for (int i = 30; i < 40; i++) {
			circleQueue.enQueue(i);
		}
		System.out.println(circleQueue);
		
	}
}

运行该程序，输出结果为：

4、总结：循环队列VS单向循环链表

4.1、相同点

循环队列和单向循环链表底层都是有头（节点）有尾（节点）的。

4.2、不同点

• 实现方式不同

  循环队列底层是基于数组进一步优化来实现的；单向循环链表底层是用单向链表首尾直接相连来实现的。

• 存储方式不同

  循环队列是顺序存储的数据结构；单向循环链表是链式存储的数据结构。

• 循环方式不同

  循环队列的首尾元素未必相连，是个逻辑上的循环（伪循环）；单向循环链表的首尾节点一定相连，是个物理上的循环（真循环）。

需要说明的是：我们讲解循环队列的目的主要有以下两点：

• 一是为了介绍队列除了链表以外的第二种实现方式，即基于数组的实现（重点）；
• 二是我们可以通过循环队列的设计思想来进一步优化前面已经实现了的动态数组（了解）。

通过这种逻辑上的“伪循环”，我们同样可以将动态数组添加和删除头部元素操作的时间复杂度从O(n)降到O(1)，优化过程与循环队列的实现过程类似，这里不再赘述。

**注：**实际使用过程中，我们还是建议优先使用双向链表来实现队列。

（本讲完，系列博文持续更新中…… ）

参考文献：
[1] 《恋上数据结构与算法》，小码哥MJ

[2] 《数据结构与算法》，邓俊辉

如何获取源代码？

关注 “阿汤笔迹” 微信公众号，在后台回复关键词 “数据结构与算法设计与实现” ，即可获取项目源代码。

原文地址：http://www.atangbiji.com/2023/07/29/CircleQueue/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。