线性表——循环双端队列

1、循环双端队列（CircleDeque）

循环双端队列是在头尾两端都能添加和删除元素的循环队列。

• 与循环队列一样，循环双端队列：

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

• 与双端队列一样，循环双端队列：

  • 它可以在队头添加元素，也可以在队尾添加元素。
  • 它可以在队头删除元素，也可以在队尾删除元素。

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

2、循环双端队列的设计

2.1、类的结构设计

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

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

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

  private int size;

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

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

  private E[] elements;

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

• 队头指针

  private int front;

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

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

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

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

• 接口函数

2.2、接口设计

循环双端队列（CircleDeque）的接口与双端队列（Deque）的接口完全一样。

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• void enQueueRear (E element); //从队尾入队
• E deQueueFront (); //从队头出队
• void enQueueFront (E element); //从队头入队
• E deQueueRear (); //从队尾出队
• E front(); //获取队列的头元素
• E rear(); //获取队列的尾元素
• void clear(); //清空队内元素

3、循环双端队列的实现

3.1、编程实现

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

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

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

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

（1）定义私有成员变量

CircleDeque.java文件：

package com.atangbiji;

public class CircleDeque<E> {

	private int size;	//循环双端队列存放元素的数量
	private E[] elements;	//用来存放循环双端队列的泛型数组变量
	
	private int front;	//队头指针
}

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

（2）创建构造函数

CircleDeque.java文件：

private static final int DEFAULT_CAPACITY =  10; //默认容量

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

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

注：

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

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

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

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

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

（3）实现size()接口

CircleDeque.java文件：

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

（4）实现isEmpty()接口

CircleDeque.java文件：

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

（5）实现enQueueRear(E element)接口

a. 当size < capacity时

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

①获取队尾指针位置；

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

③ size自增。

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

CircleDeque.java文件：

/*
 * 从队尾入队
 * @param
 * @return 
 * */
public void enQueueRear(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垃圾自动回收）。

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

CircleDeque.java文件：

/*
 * 从队尾入队
 * @param
 * @return 
 * */
public void enQueueRear(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）实现deQueueFront()接口

循环双端队列从队头出队，只需：

①获取队头元素；

②清空旧的队头；

③队头指针向后移一位；

④ size自减。

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

CircleDeque.java文件：

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

（7）实现enQueueFront (E element)接口

与enQueueRear(E element)接口类似。

a. 当size < capacity时

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

①将front向前移一位；

②将新元素插入front新指向的位置；

③size自增。

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

CircleDeque.java文件：

/*
 * 从队头入队
 * @param
 * @return 
 * */
public void enQueueFront(E element) {
	
	//front向前移一位
	if (0 == front) {
		front = (front - 1 + elements.length);
	}else {
		front = front - 1;
	}
	//将新元素插入front新指向的位置
	elements[front] = element;
	//size自增
	size++;
}

b. 当size = capacity时——扩容

当size=capacity（循环双端队列空间用完）时，如果我们需要再添加新的元素，那么就必须先对循环双端队列进行扩容。且扩容方法与enQueueRear(E element)接口的扩容方法完全一样。因此，我们只需要对enQueueRear(E element)接口做如下修改。

CircleDeque.java文件：

/*
 * 从队头入队
 * @param
 * @return 
 * */
public void enQueueFront(E element) {
	
	//确保容量充足
	ensureCapacity(size + 1);
	
	//front向前移一位
	if (0 == front) {
		front = (front - 1 + elements.length);
	}else {
		front = front - 1;
	}
	//将新元素插入front新指向的位置
	elements[front] = element;
	//size自增
	size++;
}

（8）实现deQueueRear()接口

循环双端队列从队尾出队，只需：

①获取队尾元素；

②清空旧的队尾；

③size自减。

CircleDeque.java文件：

/*
 * 从队尾出队
 * @param
 * @return 
 * */
public E deQueueRear() {
	
	int rear = (front + size - 1) % elements.length;//获取队尾指针位置
	//获取队尾元素
	E rearElement = elements[rear];
	//清空旧的队尾
	elements[rear] = null;
	//size自减
	size--;
	
	return rearElement;
}

（9）实现front()接口

CircleDeque.java文件：

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

（10）实现rear()接口

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

CircleDeque.java文件：

/*
 * 获取队列的尾元素
 * @param
 * @return 
 * */
public E rear() {
	return elements[(front + size - 1) % elements.length];	//直接返回队尾指针所指向的元素即可
}

（11）实现clear()接口

CircleDeque.java文件：

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

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

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

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

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

CircleDeque.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("; rear = ").append((front + size) % elements.length).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文件）中新建一个CircleDeque对象，用来测试自己封装的循环双端队列。这里仅以入队和出队接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		CircleDeque<Integer> circleDeque = new CircleDeque<Integer>();
		
		for (int i = 0; i < 10; i++) {
			circleDeque.enQueueFront(i + 1);
			circleDeque.enQueueRear(i + 100);
		}
		System.out.println(circleDeque);
		
		for (int i = 0; i < 3; i++) {
			circleDeque.deQueueFront();
			circleDeque.deQueueRear();
		}
		System.out.println(circleDeque);
		
		circleDeque.enQueueFront(201);
		circleDeque.enQueueFront(202);
		System.out.println(circleDeque);
		
		while (!circleDeque.isEmpty()) {
			System.out.println(circleDeque.deQueueFront());
		}
	}
}

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

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

4.1、相同点

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

4.2、不同点

• 实现方式不同

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

• 存储方式不同

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

• 循环方式不同

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

需要说明的是：我们讲解循环双端队列的目的主要是为了介绍双端队列除了链表以外的第二种实现方式，即基于数组的实现。

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

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

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

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

如何获取源代码？

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

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