人生设计师
这是系列文章，每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现，从而对常用的数据结构和
java集合有个大概的了解。当然实现没有java集合的实现那么复杂，功能也没有那么强大，但是可以通过这些简单的实现窥探到底层的一些共性原理。
一. 顺序循环队列的描述
在上一篇文章中已经讲了顺序队列，因为顺序队列会出现假溢出问题，所以实际应用中更多使用的是顺序循环队列，顺序循环队列把顺序队列的存储单元在逻辑上构成一个首尾相连的循环队列。顺序循环队列在以下几个方面对顺序队列做了改动。
1. 队头，队尾下标按照循环规律变化
队头front，队尾rear分别按照如下规律变化，其中length表示数组的长度。
front=(front+1)%length;
rear=(rear+1)%length;
因此，front和rear的取值范围是0~length-1，不会出现假溢出问题。
2. 约定队尾下标rear的含义以及队列为空的条件
约定rear是下一个入队元素的位置，队列为空的条件是front=rear。设置初始化空队列为front=rear=0，入队操作只需要改变rear下标，出队操作只需要修改front下标，不需要同时改变两个下标。变化过程看下面的描述:
2.1 初始空队列，令front=rear=0。
2.2 元素10和20入队。
2.3 元素10和20出队，此时队列为空。
2.4 元素30,40,50,60入队后，队列满front=(rear+1)%length。
2.5 扩充数组容量后如下图所示：
二. 顺序循环队列的实现
1. 定义顺序循环队列
顺序循环队列类SeqCycleQueue实现队列接口QQueue，并实现队列接口中定义的方法，队列接口的定义参考前面文章自己实现集合框架(十四):队列接口，代码如下所示：
package org.light4j.dataStructure.linearList.queue.sequence.cycle;
import org.light4j.dataStructure.linearList.queue.QQueue;
/**
* 顺序循环队列
*
* @author longjiazuo
* @param <E>
*/
public class SeqCycleQueue<E> implements QQueue<E> {
private Object[] value;// 存储队列数据元素的数组
private int front;// 对头下标
private int rear;// 队尾下标
public SeqCycleQueue(int capacity) {// 构造指定容量的空循环队列
value = new Object[Math.abs(capacity)];
this.front = this.rear = 0;
}
public SeqCycleQueue() {// 构造默认空循环队列
this(16);
}
}
代码解释：
① 定义了两个构造函数，一个无参的构造函数，队列的容量默认是
16，另外一个有参的构造函数，可以指定队列的容量。②
Math.abs(capacity)取队列容量的绝对值，做容错处理，防止传入负数的情况。③ 初始化
front和rear的下标为0。
2. 判断队列是否为空
/**
* 判断队列是否为空，若为空返回true
*
* @return
*/
@Override
public boolean isEmpty() {
return this.front == this.rear;
}
代码解释:
① 判断队列是否为空的依据是队头，队尾的下标
front=rear=0。
3. 入队
/**
* 元素入队，操作成功返回true
*
* @param element
* @return
*/
@Override
public boolean enqueue(E element) {
if (element == null) {// 空元素不允许入队
return false;
}
if (this.front == (this.rear + 1) % this.value.length) {
Object[] temp = this.value;
this.value = new Object[temp.length * 2];// 扩充数组容量，扩充为原来容量的2倍
int i = this.front;
int j = 0;
while (i != this.rear) {// 循环拷贝元素到新的数组
this.value[j] = temp[i];// 元素复制
i = (i + 1) % temp.length;
j++;
}
this.front = 0;// 新队列的front为0
this.rear = j;// 新队列的rear从索引j开始
}
this.value[this.rear] = element;
this.rear = (this.rear + 1) % this.value.length;// rear下标变化规律
return true;
}
4.出队
/**
* 出队，返回当前对头元素，若队列为空则返回null
*
* @return
*/
@Override
public E dequeue() {
if (!isEmpty()) {// 队列不为空
@SuppressWarnings("unchecked")
E temp = (E) this.value[this.front];// 取对头元素
this.front = (this.front + 1) % this.value.length;// front下标变化规律
return temp;
}
return null;
}
5.重写toString()方法
/**
* 返回栈中各元素的字符串表示
*/
@Override
public String toString() {
String str = "(";
if (!isEmpty()) {// 判断是否非空
for (int i = this.front; i <= this.rear - 1; i++) {// 从对头 到队尾
if (i == this.rear - 1) {
str += this.value[i];
} else {
str += this.value[i] + ",";
}
}
}
return str + ")";
}
三. 测试
package org.light4j.dataStructure.linearList.queue.sequence.cycle;
import org.light4j.dataStructure.linearList.queue.QQueue;
public class Test {
public static void main(String[] args) {
QQueue<String> queue = new SeqCycleQueue<String>();
queue.dequeue();// 出栈
System.out.println(queue.toString());
queue.enqueue("A");// 元素在队尾入队
queue.enqueue("B");
queue.enqueue("C");
queue.enqueue("D");
System.out.println(queue.toString());
queue.dequeue();// 对头出队
System.out.println(queue.toString());
}
}
运行结果如下图所示：
四.时间复杂度分析
由于队列只能在队尾入队，在队头出队，所以入队enqueue()，出队dequeue()的时间复杂度为O(1)，当需要扩充容量时，入队操作enqueue()的时间复杂度为O(n)。
五.源代码示例
公众号ID：longjiazuoA
未经允许不得转载：人生设计师 » 自己实现集合框架(十四):顺序循环队列的实现