一、双端队列（Deque）
是能在头尾两端
的队列
英文 deque 是 double ended queue 的简称
双端队列（Deque）
双端队列的接口设计
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueueRear(E element); // 从队尾入队
E deQueueFront(); // 从队头出队
void enQueueFront(E element); // 从队头入队
E deQueueRear(); // 从队尾出队
E front(); // 获取队列的头元素
E rear(); // 获取队列的尾元素
双端队列代码实现
/**
* 双端队列
*/
public class Deque<E> {
private List<E> list = new LinkedList<>();
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 从队尾入队
* @param element
*/
public void enQueueRear(E element) {
list.add(element);
}
/**
* 从队头入队
* @param element
*/
public void enQueueFront(E element) {
list.add(0,element);
}
/**
* 从队尾出队
* @return
*/
public E deQueueRear() {
return list.remove(size() -1);
}
/**
* 从队头出队
* @return
*/
public E deQueueFront() {
return list.remove(0);
}
/**
* 获取队列的头元素
* @return
*/
public E front() {// 官方的是peekFirst()
return list.get(0);
}
/**
* 获取队列的尾元素
* @return
*/
public E rear() {// 官方的是peekFirst()
return list.get(size() -1);
}
public void clear() {
list.clear();
}
}
二、循环队列（Circle Queue）
其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度
这个用数组实现并且优化之后的队列也叫做：
循环队列（Circle Queue）
/**
* 循环队列
*/
public class CircleQueue<E> {
private static final int DEFAULT_CAPACITY = 10;
private E[] elements;
private int size;
private int front;
public CircleQueue() {
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 sb = new StringBuilder();
sb.append("capcacity=").append(elements.length)
.append(",size=").append(size).append(",front=").append(front)
.append(",[");
for(int i = 0;i < elements.length;i++) {
if(i != 0)
sb.append(",");
sb.append(elements[I]);
}
sb.append("]");
return sb.toString();
}
}
但是现在这个循环队列暂时还不能扩容。
动态扩容
/**
* 循环队列
*/
public class CircleQueue<E> {
private static final int DEFAULT_CAPACITY = 10;
private E[] elements;
private int size;
private int front;
public CircleQueue() {
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[index(size)] = element;
size++;
}
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[index(i)];
}
elements = newElements;
// 重置front
front = 0;
System.out.println(oldCapacity + "扩容为" + newCapacity);
}
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
//索引映射分装
private int index(int index) {
return (front + index) % elements.length;
}
public E front() {
return elements[front];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("capcacity=").append(elements.length)
.append(",size=").append(size).append(",front=").append(front)
.append(",[");
for(int i = 0;i < elements.length;i++) {
if(i != 0)
sb.append(",");
sb.append(elements[I]);
}
sb.append("]");
return sb.toString();
}
}
三、循环双端队列
：可以进行两端添加、删除操作的循环队列
/**
* 循环双端队列
*/
public class CircleDeque<E> {
private static final int DEFAULT_CAPACITY = 10;
private E[] elements;
private int size;
private int front;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 从队尾入队
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size +1);
elements[index(size)] = element;
size++;
}
/**
* 从队头入队
* @param element
*/
public void enQueueFront(E element) {
ensureCapacity(size +1);
front = index(-1);
elements[front] = element;
size++;
}
/**
* 从队尾出队
* @return
*/
public E deQueueRear() {
int rearIndex = index(size -1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
/**
* 从队头出队
* @return
*/
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
/**
* 获取队列的头元素
* @return
*/
public E front() {// 官方的是peekFirst()
return elements[front];
}
/**
* 获取队列的尾元素
* @return
*/
public E rear() {// 官方的是peekLast()
return elements[index(size -1)];
}
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[index(i)];
}
elements = newElements;
// 重置front
front = 0;
System.out.println(oldCapacity + "扩容为" + newCapacity);
}
//索引映射分装
private int index(int index) {
index += front;
if(index < 0) {
return index + elements.length;
}
return index % elements.length;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("capcacity=").append(elements.length)
.append(",size=").append(size).append(",front=").append(front)
.append(",[");
for(int i = 0;i < elements.length;i++) {
if(i != 0)
sb.append(",");
sb.append(elements[I]);
}
sb.append("]");
return sb.toString();
}
}
四、%运算符优化
尽量避免使用运算，效率低下。
上面会经常用到(front + index) % elements.length;这种操作(n % m)，其实这种操作在满足：m >0,n >=0,n < 2m条件下可以进行。
如下图操作：
总结：已知
n >= 0，m > 0那么
因此之前的索引映射分装的代码可以这样改写；
