---

持续学习&持续更新中…

学习态度：脚踏实地

---

普通队列 （Queue）

public interface Queue<E> {
    int size();

    void enQueue(E element);

    E deQueue();

    // 获取队列头元素
    E front();

    void clear();

    boolean isEmpty();
}

双端队列 （Deque）Double Ended Queue

/*double ended queue 双端队列*/

public interface Deque<E> {

    int size();

    // 从队首入队
    void enQueueFront(E element);

    // 从队尾入队
    void enQueueRear(E element);

    // 从队首出队
    E deQueueFront();

    // 从队尾出队
    E deQueueRear();

    // 获取队列头元素
    E front();

    // 获取队列尾元素
    E rear();

    void clear();

    boolean isEmpty();

}

链表实现

使用链表来实现队列肯定要使用双向链表，因为涉及到首尾元素的操作。

普通队列

public class LinkedListQueue<E> implements Queue<E> {

    private final LinkedList<E> list = new LinkedList<>();

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public void enQueue(E element) {
        list.add(element);
    }

    @Override
    public E deQueue() {
        return list.remove(0);
    }

    @Override
    public E front() {
        return list.get(0);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

}

双端队列

public class LinkedListDeque<E> implements Deque<E> {

    private final LinkedList<E> list = new LinkedList<>();

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    @Override
    public void enQueueRear(E element) {
        list.add(element);
    }

    @Override
    public E deQueueFront() {
        return list.remove(0);
    }

    @Override
    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }

    @Override
    public E front() {
        return list.get(0);
    }

    @Override
    public E rear() {
        return list.get(list.size() - 1);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

}

循环队列

动态数组实现

使用动态数组来实现队列肯定要进行优化，优化为动态循环数组，不能直接使用ArrayList来直接实现队列。

当然，如果可以自己写一个底层使用循环数组的ArrayList，那么这时就可以直接使用ArrayList了。

普通队列

/*
    使用动态循环数组实现队列
*/

public class DynamicArrayQueue<E> implements Queue<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private int size;
    private int front;
    private E[] elements;

    public DynamicArrayQueue(int capacity) {
        capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }

    public DynamicArrayQueue() {
        this(DEFAULT_CAPACITY);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void enQueue(E element) {
        ensureCapacity();
        elements[index(size)] = element;
        size++;
    }

/*
	这样优化代码是经过充分考虑的，因为这里的代码无论何时都符合n >= 0, m > 0, n < 2m
*/
    private int index(int n) {
        n += front;
        return n < elements.length ? n : (n - elements.length);
//        return (n + front) % elements.length;
    }

    private void ensureCapacity() {
        if (size == elements.length) {
            final int len = elements.length + (elements.length >> 1);
            E[] newElements = (E[]) new Object[len];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[index(i)];
            }

            elements = newElements;
            front = 0;
        }
    }

    @Override
    public E deQueue() {
        E e = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return e;
    }

    @Override
    public E front() {
        return elements[front];
    }

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

        front = 0;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("CircleQueue { Capacity: ").append(elements.length).append(", ");
        sb.append("Size: ").append(size).append(", front: ").append(front).append(", elements: \n[");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) sb.append(", ");
            sb.append(elements[i]);
        }
        sb.append("]\n}");
        return sb.toString();
    }

}

双端队列

/*
    使用动态循环数组实现双端队列
*/

public class DynamicArrayDeque<E> implements Deque<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private int size;
    private int front;
    private E[] elements;

    public DynamicArrayDeque(int capacity) {
        capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }

    public DynamicArrayDeque() {
        this(DEFAULT_CAPACITY);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void enQueueFront(E element) {
        ensureCapacity();
        front = index(-1);
        elements[front] = element;
        size++;
    }

    @Override
    public void enQueueRear(E element) {
        ensureCapacity();
        elements[index(size)] = element;
        size++;
    }

    @Override
    public E deQueueFront() {
        E e = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return e;
    }

    @Override
    public E deQueueRear() {
        int rear = index(size - 1);
        E e = elements[rear];
        elements[rear] = null;

        size--;
        return e;
    }

    private int index(int n) {
        n += front;
        if (n < 0) {
            return elements.length + n;
        }
        return n < elements.length ? n : (n - elements.length);
    }

    private void ensureCapacity() {
        if (size == elements.length) {
            final int len = elements.length + (elements.length >> 1);
            E[] newElements = (E[]) new Object[len];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[index(i)];
            }

            elements = newElements;
            front = 0;
        }
    }


    @Override
    public E front() {
        return elements[front];
    }

    @Override
    public E rear() {
        return elements[index(size - 1)];
    }

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

        front = 0;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("CircleQueue { Capacity: ").append(elements.length).append(", ");
        sb.append("Size: ").append(size).append(", front: ").append(front).append(", elements: \n[");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) sb.append(", ");
            sb.append(elements[i]);
        }
        sb.append("]\n}");
        return sb.toString();
    }

}

%运算符优化

注意

1. 实现链表时，对数组的长度取模运算可以进行优化（代码中已经写了）
2. 上述代码完全可以使用Java的面向对象思想进行重构，比如再写一个AbstractQueue和AbstractDeque来优化精简代码，此处主要注重的是数据结构，因此就先不重构代码。

参考

小码哥李明杰老师课程: 恋上数据结构与算法 第一季.

---

本文完，感谢您的关注支持！

---