Version: Next

循环队列

  • 循环队列底层使用数组实现
  • 循环双端队列是可以进行两端添加、删除操作的循环队列
  • 也可以使用动态数组实现，并且各接口可以优化到时间复杂度O(1)

实现

  • 因为使用了数组，所以定义一个成员变量size
  • 定义一个泛型数组E[] elements
  • 定义int front记录头节点对应的下标
方法实现思路
E front()返回队头元素直接返回elements[front]
enQueue(E element) 队尾入队不能直接在size下标位置插入元素，考虑到循环，下标应当是front + size; 考虑到front + size可能大于数组的最大下标，要折返，实现循环，使用取模实现下标应当为(front + size) % elements.length
E deuQueue()队头出队每次移除front指向的元素时，将front++，当front超出了最大下标，要折返，体现循环，即取模，即front = (front + 1) % elements.length

代码

/**
* 循环队列
*/
@SuppressWarnings("unchecked")
public class MyCycleQueue<E> {
private int front; // 头指针，指向头元素对应的下标
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public MyCycleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enQueue(E element) { // 队尾入队
elements[(front + size) % elements.length] = element; // 取模直返，体现循环
size++;
}
public E deQueue() { // 队头出队
E frontElement = elements[front];
elements[front] = null; // 清空当前队头
front = (front + 1) % elements.length; // 取模直返，体现循环
size--;
return frontElement;
}
public E front() { // 返回队头元素
return elements[front];
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("capacity = ").append(elements.length)
.append(", size = ").append(size)
.append(", front = ").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) stringBuilder.append(", ");
stringBuilder.append(elements[i]);
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}
JUnit测试1
@Test
public void test() {
MyCycleQueue<Integer> cycleQueue = new MyCycleQueue<>();
for (int i = 0; i < 10; i++) {
cycleQueue.enQueue(i);
}
System.out.println("cycleQueue => " + cycleQueue);
for (int i = 0; i < 5; i++) {
cycleQueue.deQueue();
}
System.out.println("cycleQueue => " + cycleQueue);
while (!cycleQueue.isEmpty()) {
System.out.println("cycleQueue.deQueue() => " + cycleQueue.deQueue());
}
}
运行结果
cycleQueue => capacity = 10, size = 10, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
cycleQueue => capacity = 10, size = 5, [null, null, null, null, null, 5, 6, 7, 8, 9]
cycleQueue.deQueue() => 5
cycleQueue.deQueue() => 6
cycleQueue.deQueue() => 7
cycleQueue.deQueue() => 8
cycleQueue.deQueue() => 9
JUnit测试2
@Test
public void test() {
MyCycleQueue<Integer> cycleQueue = new MyCycleQueue<>();
for (int i = 0; i < 10; i++) {
cycleQueue.enQueue(i);
}
System.out.println("cycleQueue => " + cycleQueue);
for (int i = 0; i < 5; i++) {
cycleQueue.deQueue();
}
System.out.println("cycleQueue => " + cycleQueue);
for (int i = 15; i < 20; i++) {
cycleQueue.enQueue(i);
}
System.out.println("cycleQueue => " + cycleQueue);
while (!cycleQueue.isEmpty()) {
System.out.println("cycleQueue.deQueue() => " + cycleQueue.deQueue());
}
}
运行结果
cycleQueue => capacity = 10, size = 10, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
cycleQueue => capacity = 10, size = 5, [null, null, null, null, null, 5, 6, 7, 8, 9]
cycleQueue => capacity = 10, size = 10, [15, 16, 17, 18, 19, 5, 6, 7, 8, 9]
cycleQueue.deQueue() => 5
cycleQueue.deQueue() => 6
cycleQueue.deQueue() => 7
cycleQueue.deQueue() => 8
cycleQueue.deQueue() => 9
cycleQueue.deQueue() => 15
cycleQueue.deQueue() => 16
cycleQueue.deQueue() => 17
cycleQueue.deQueue() => 18
cycleQueue.deQueue() => 19

动态扩容

info

如果容量满了，我们希望像动态数组一样，为它实现扩容功能

  • 在enQueue(E element)方法中，进行扩容
caution
  1. 遍历旧数组时，下标应为(front + i) % elements.length，头下标+偏移量的和，再对数组的长度取模
  2. 搬运到新数组后，循环队列的头指针front要重置为0
扩容：ensureCapacity
/**
* 扩容
*
* @param capacity 确保容量
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity > capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容到1.5倍
E[] newElements = (E[]) new Object[newCapacity];
// 循环队列中，注意 遍历elements数组使用的下标
// i + front 再对 整个数组的长度取模
for (int i = 0; i < size; i++) {
newElements[i] = elements[(i + front) % elements.length]; // 数组搬家
}
// 在循环队列中，还要将front指针，重新指向开头下标0
front = 0;
elements = newElements; // 指向新数组
}

修改入队方法

添加扩容

public void enQueue(E element) { // 队尾入队
// 扩容检查
ensureCapacity(size + 1);
elements[(front + size) % elements.length] = element; // 取模直返，体现循环
size++;
}

索引映射封装

至此，可以观察出，实际上循环队列的特殊之处，就是对数组下标的计算

(无折返循环时的最终下标 + front) % element.length

info
  • 可以封装一个方法，传入无折返循环时的最终下标，返回循环队列中对应的下标
  • 使用它，可以像书写正常队列一样书写下标，只需要在使用下标时，调用这个方法即可
索引映射方法
private int index(int oldIndex) {
return (front + oldIndex) % elements.length; // 取模，实现折返循环
}

完整代码

循环队列
/**
* 循环队列
*/
@SuppressWarnings("unchecked")
public class MyCycleQueue<E> {
private int front; // 头指针，指向头元素对应的下标
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public MyCycleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enQueue(E element) { // 队尾入队
// 扩容检查
ensureCapacity(size + 1);
// elements[(front + size) % elements.length] = element; // 取模直返，体现循环
elements[index(size)] = element; // 取模直返，体现循环
size++;
}
public E deQueue() { // 队头出队
E frontElement = elements[front];
elements[front] = null; // 清空当前队头
// front = (front + 1) % elements.length; // 取模直返，体现循环
front = index(1); // 取模直返，体现循环
size--;
return frontElement;
}
public E front() { // 返回队头元素
return elements[front];
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("capacity = ").append(elements.length)
.append(", size = ").append(size)
.append(", front = ").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) stringBuilder.append(", ");
stringBuilder.append(elements[i]);
}
stringBuilder.append("]");
return stringBuilder.toString();
}
/**
* 扩容
*
* @param capacity 确保容量
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity > capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容到1.5倍
E[] newElements = (E[]) new Object[newCapacity];
// 循环队列中，注意 遍历elements数组使用的下标
// i + front 再对 整个数组的长度取模
for (int i = 0; i < size; i++) {
// newElements[i] = elements[(front + i) % elements.length]; // 数组搬家
newElements[i] = elements[index(i)]; // 数组搬家
}
// 在循环队列中，还要将front指针，重新指向开头下标0
front = 0;
elements = newElements; // 指向新数组
}
private int index(int oldIndex) {
return (front + oldIndex) % elements.length; // 取模，实现折返循环
}
@Test
public void test() {
MyCycleQueue<Integer> cycleQueue = new MyCycleQueue<>();
for (int i = 0; i < 10; i++) {
cycleQueue.enQueue(i);
}
System.out.println("cycleQueue => " + cycleQueue);
for (int i = 0; i < 5; i++) {
cycleQueue.deQueue();
}
System.out.println("cycleQueue => " + cycleQueue);
for (int i = 15; i < 26; i++) {
cycleQueue.enQueue(i);
}
System.out.println("cycleQueue => " + cycleQueue);
while (!cycleQueue.isEmpty()) {
System.out.println("cycleQueue.deQueue() => " + cycleQueue.deQueue());
}
}
}