九种数据结构之双端队列与循环队列的比较

一、双端队列（Deque）

是能在头尾两端的队列
英文 deque 是 double ended queue 的简称

双端队列的接口设计

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) 的时间复杂度
这个用数组实现并且优化之后的队列也叫做：

/**
 * 循环队列
 */
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
那么 等价于 的前提条件：

因此之前的索引映射分装的代码可以这样改写；

代码地址