//循环双端队列
package com.weyan.circle;
@SuppressWarnings("unchecked")
public class CircleDeque<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[])new Object[DEFAULT_CAPACITY];
}
//元素个数
public int size() {
return size;
}
//队列是否为空
public boolean isEmpty() {
return size == 0;
}
//从队尾入队
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size ++;
}
//从队尾出队
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size -- ;
return rear;
}
//从队头入队
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size ++;
}
//从队头出队
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size --;
return frontElement;
}
//队头元素
public E front() {
return elements[front];
}
//队尾元素
public E rear() {
return elements[index(size - 1)];
}
public int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
}
return index % elements.length;
}
/**
* 保证要有capacity的容量
* @param capacity
*/
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[(i+front) % elements.length];
}
elements = newElements;
//重置front
front = 0;
System.out.println(oldCapacity + "扩容为" + newCapacity);
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuilder string = new StringBuilder();
string.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) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
验证结果：
//测试循环双端队列
static void test3() {
CircleDeque<Integer> queue = new CircleDeque<Integer>();
//头5 4 3 2 1 100 101 102 103 104 105 106 8 7 6 尾
//头8 7 6 5 4 3 2 1 100 101 102 103 104 105 106 107 108 109 null null 10 9 尾
for (int i = 0; i < 10; i++) {
queue.enQueueFront(i + 1);
queue.enQueueRear(i + 100);
}
System.out.println(queue);
while (!queue.isEmpty()) {
System.out.println(queue.deQueueFront());
}
}
-------------------------------------------------------------------------------------------------------
10扩容为15
15扩容为22
capacity=22,size=20,front=20,[8, 7, 6, 5, 4, 3, 2, 1, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, null, null, 10, 9]
10
9
8
7
6
5
4
3
2
1
100
101
102
103
104
105
106
107
108
109
测试2：
//测试循环双端队列
static void test3() {
CircleDeque<Integer> queue = new CircleDeque<Integer>();
//头5 4 3 2 1 100 101 102 103 104 105 106 8 7 6 尾
//头8 7 6 5 4 3 2 1 100 101 102 103 104 105 106 107 108 109 null null 10 9 尾
for (int i = 0; i < 10; i++) {
queue.enQueueFront(i + 1);
queue.enQueueRear(i + 100);
}
//头null 7 6 5 4 3 2 1 100 101 102 103 104 105 106 null null null null null null null 尾
for (int i = 0; i < 3; i++) {
queue.deQueueFront();
queue.deQueueRear();
}
//头11 7 6 5 4 3 2 1 100 101 102 103 104 105 106 null null null null null null 12 尾
queue.enQueueFront(11);
queue.enQueueFront(12);
System.out.println(queue);
while (!queue.isEmpty()) {
System.out.println(queue.deQueueFront());
}
}
----------------------------------------------------------------------------------------------------------
10扩容为15
15扩容为22
capacity=22,size=16,front=21,[11, 7, 6, 5, 4, 3, 2, 1, 100, 101, 102, 103, 104, 105, 106, null, null, null, null, null, null, 12]
12
11
7
6
5
4
3
2
1
100
101
102
103
104
105
106
总结：
用动态数组实现循环队列和循环双端队列的目的：是对动态数组的优化和另外一种思想（思路）实现队列。
