双端队列 – 玩算法

双端队列具有队列和栈两种数据结构的性质，在两边都能插入和删除，但不能在中间删除和插入，如下图所示。

我们前面讲的双向链表，如果不在中间执行添加和删除操作的话，也可以把他看作是一个双端队列。双端队列的实现有两种方式，一种是使用链表，一种是使用数组，使用链表可以参考前面讲的双向链表，这里我们来介绍使用数组的实现方式，如下图所示。

双端队列元素的添加：

双端队列元素的删除：

来看下代码：

public class Qeque<E> {

    private Object[] data;
    private final int maxSize;// 队列的最大容量。
    private int size; // 队列中元素的个数。
    private int head;// 队列不为空就存储头部元素的位置。
    private int tail;// 存储尾部元素的下一个应该存放的位置。

    public Qeque(int maxSize) {
        if (maxSize <= 0)
            throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
        this.maxSize = maxSize;
        data = new Object[this.maxSize];
    }

    // 在头部添加元素。
    public void addHead(E val) {
        if (isFull())
            throw new IllegalStateException("队列已经满了，无法再加入……");
        head--;
        head = (head + maxSize) % maxSize;// 防止 head 出现 -1 。
        data[head] = val;
        size++;
    }

    // 在尾部添加元素。
    public void addTail(E val) {
        if (isFull())
            throw new IllegalStateException("队列已经满了，无法再加入……");
        data[tail++] = val;
        tail = tail % maxSize;
        size++;
    }

    // 删除头部元素
    public E removeHead() {
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法删除……");
        E result = (E) data[head];// 获取头部元素的值。
        data[head++] = null;// 头部元素清空，清空之后 head 指针往右移一步。
        head = head % maxSize;
        size--;
        return result;
    }

    // 删除尾部元素。
    public E removeTail() {
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法删除……");
        tail--;
        tail = (tail + maxSize) % maxSize;
        E result = (E) data[tail];
        data[tail] = null;
        size--;
        return result;
    }

    // 获取头部元素。
    public E getHead() {
        if (isEmpty())
            throw new NoSuchElementException();
        return (E) data[head];
    }

    // 获取尾部元素。
    public E getTail() {
        if (isEmpty())
            throw new NoSuchElementException();
        return (E) data[(tail - 1 + maxSize) % maxSize];
    }

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

    public boolean isFull() {
        return size == maxSize;
    }

    public int size() {
        return size;
    }
}

参考：
ArrayDeque.java

相关链接

数组	数组，滚动数组，差分数组，树状数组
链表	链单向表，双向链表，循环链表，跳表，异或链表
队列	队列，循环队列，双端队列
栈	栈
散列表	散列表
树	二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树
堆	堆
图	图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序