dequeも忘れないであげてね（＞＜）

Java 6 からdequeことArrayDequeが実装されています。
dequeって聞き慣れない！
とか思うかもしれないですが「Double Ended Queue」で両端キューです。
STLではvector,list,dequeはよく使われると思うのですが、Javaではなかったんですね。
特徴としては、

• 先頭への挿入（削除）
• 終端への挿入（削除）

がO(1)で出来ます。

LinkedListでも同様のことができますが、LinkedListより高速で省メモリです。
（ただし、先頭と終端以外への挿入はLinkedListより遅いO(n)になります）
また、ランダムアクセスも高速です。

アルゴリズム的にはリングバッファでvector（ArrayList）がわっかになっているようなイメージです。
headとtailの位置を覚えており、
配列（バッファ）の中のどこが先頭でどこが終端か、
を覚えているだけです。

    private transient E[] elements;
    private transient int head;
    private transient int tail;

だけで実装できてしまう簡単アルゴリズムでもあります。
Javaでは何も指定しないと最初に16のバッファを確保するのですが
例えば、

    deque.addFirst(1);
    deque.addFirst(2);
    
    deque.addLast(100);
    deque.addLast(200);

こう操作すると、

head:14,
tail:2,
capacity:16,
elements:
100, 200, null, null, null, null, null, null, null, null, null, null, null, null, 2, 1,
みたいな感じになります。
elementsをわっかに見なすわけですね。

addFirst

        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();

addLast

        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();

という感じです。
doubleCapacityはバッファが足りなくなった時に確保にいく処理で

private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = (E[])a;
        head = 0;
        tail = n;
}

と、配列を拡張したあとにコピーを行っています。

なので、最初にpublic ArrayDeque(int numElements) を使って必要な要素数を確保しておくとさらに効率がよくなります。
ArrayList
LinkedList
ArrayDeque
ここは一つトリオで是非。