Version: Next

循环双端队列

  • 使用一个变量front记录队头下标
  • 队尾下标通过计算得到：front + size - 1
  • 为了体现循环，需要对上面的队尾下标进行取模，(front + size - 1) % elements.length
info

只列出与循环队列有区别的部分

  • 从头部入队方法
  • 从尾部出队方法

循环队列下标转换方法

为了体现循环，进行折返下标计算的方法

  • 如果传入的下标是正数：加上front再对数组长度取模
  • 如果传入的下标是负数：加上front再加上数组长度
index()
/**
* 循环折返取模，下标转换
*/
private int index(int index) {
index = front + index;
if (index < 0)
return index + elements.length; // 相加实现折返循环
else
return index % elements.length; // 取模，实现折返循环
}

队头入队

  • 扩容检查
  • 在front指向的位置的前一个位置插入元素，计算下标时要考虑循环，相当于在队列-1的位置插入元素
  • 让front指向新的队头
  • size++
/**
* 头部入队
*
* @param element 入队元素
*/
public void enQueueFront(E element) {
int preFront;
ensureCapacity(size + 1); // 扩容
// 计算前位置
/* if (front == 0)
preFront = elements.length - 1;
else
preFront = front - 1;*/
// 相当于在 队列的-1位置 插入 , 调用下标转换的方法
preFront = index(-1);
elements[preFront] = element;
front = preFront; // 更新队头下标值
size++;
}

队尾出队

  • 将队尾的元素删除
  • 计算队尾坐标front + size - 1，考虑循环折返：index(size - 1)
/**
* 尾部出队
*
* @return 出队元素
*/
public E deQueueRear() {
int rearIndex = index(size - 1);
E rearElement = elements[rearIndex];
elements[rearIndex] = null; // 清空队尾;
size--;
return rearElement;
}

测试

@Test
public void tempTest() {
MyCycleDeque<Integer> cycleDeque = new MyCycleDeque<>();
// 头 10 9 8 7 6 5 4 3 2 1 101 102 103 104 105 106 107 108 109 110 尾
for (int i = 0; i < 10; i++) {
cycleDeque.enQueueFront(i + 1);
cycleDeque.enQueueRear(i + 100);
}
System.out.println("预期:头 10 9 8 7 6 5 4 3 2 1 101 102 103 104 105 106 107 108 109 110 尾");
System.out.println(cycleDeque);
while (!cycleDeque.isEmpty()) {
System.out.print(cycleDeque.deQueueFront() + " ");
}
}
运行结果
预期:头 10 9 8 7 6 5 4 3 2 1 100 101 102 103 104 105 106 107 108 109 尾
capacity = 22, size = 20, front = 19, [7, 6, 5, 4, 3, 2, 1, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, null, null, 10, 9, 8]
10 9 8 7 6 5 4 3 2 1 100 101 102 103 104 105 106 107 108 109

根据capacity = 22，可知数组进行了两次扩容

@Test
public void tempTest() {
MyCycleDeque<Integer> cycleDeque = new MyCycleDeque<>();
// 头 10 9 8 7 6 5 4 3 2 1 101 102 103 104 105 106 107 108 109 110 尾
for (int i = 0; i < 10; i++) {
cycleDeque.enQueueFront(i + 1);
cycleDeque.enQueueRear(i + 100);
}
// 头 7 6 5 4 3 2 1 100 101 102 103 104 105 106 尾
for (int i = 0; i < 3; i++) {
cycleDeque.deQueueFront();
cycleDeque.deQueueRear();
}
System.out.println("头 7 6 5 4 3 2 1 100 101 102 103 104 105 106 尾");
System.out.println(cycleDeque);
System.out.print("\n");
System.out.println("---------------------------------------------------");
}
运行结果
头 7 6 5 4 3 2 1 100 101 102 103 104 105 106 尾
capacity = 22, size = 14, front = 0, [7, 6, 5, 4, 3, 2, 1, 100, 101, 102, 103, 104, 105, 106, null, null, null, null, null, null, null, null]

下标转换方法的优化

info
  • 尽量避免使用* ,/, %, 浮点数计算，因为它们效率比较低
  • 通过位运算实现取模的效果，条件：n < 2m时以下结论成立
    • 设n = 13, m = 10
    • 取模：
      • 当 n >= m时，取模结果就是n - m
      • 当 n < m时，取模结果就是n，即 n - 0
    • 即: n - ((n >= m) ? m : 0)
  • 将元素下标视为n；数组长度视为m，则最大下标值为front + size，显然 (front + size)一定小于2 x elements.length，故可用位运算进行优化
private int index(int index)
/**
* 循环折返取模，下标转换
*/
private int index(int index) {
index = front + index;
if (index < 0)
return index + elements.length; // 相加实现折返循环
else
// return index % elements.length; // 取模，实现折返循环
return index - (index >= elements.length ? elements.length : 0); // 取模，实现折返循环
}

clear方法

public void clear() {
for (int i = 0; i < size; i++)
elements[index(i)] = null;
size = 0;
front = 0;
}