一目で思い出せるJavaのArrayDequeのキュー/スタックとしての使い方

Javaでキューやスタックの処理を行いたい

競技プログラミングなどで、キューやスタックの処理を行いたいことがよくあります。キューの処理については大概の場合優先度をつけて実行するPriorityQueueを使用することが多いですが、純粋にキューの処理を行いたい場合や、スタックの処理を行いたい場合はArrayDequeクラスを使用することができます。

このクラスは両端キュークラスなので、先入れ先出し(FIFO)のキューとしても、後入れ先出し(LIFO)のスタックとしても使用することができるのですが、似たような名前のメソッドが多くよく混乱するので、使い方を整理しておきます。

図解＋基本的な使い方

大概の場合は以下の図のメソッドを使えば処理できると思います。poll系のメソッドを使うと取り出した要素は削除されます。キューとスタックで違うのは、取り出すときに使うメソッドだけです。

キュー(先入れ先出し=FIFO)

ArrayDeque<Integer> queue = new ArrayDeque<>();
for ( int i = 0 ; i < 5 ; i++ ) queue.add(i);
while ( queue.size() > 0 ) {
    System.out.print(queue.poll() + " ");
}

実行結果

0 1 2 3 4 

スタック(後入れ先出し=FIFO)

ArrayDeque<Integer> stack = new ArrayDeque<>();
for ( int i = 0 ; i < 5 ; i++ ) stack.add(i);
while ( stack.size() > 0 ) {
    System.out.print(stack.pollLast() + " ");
}

実行結果

4 3 2 1 0 

性能

競技プログラミングで使う場合は性能が気になると思います。要素を100個追加して100個取り出す、というのを100万回繰り返して(つまり合計1億回の追加・取り出し)所要時間を測定してみました。

	所要時間(計1億回の追加・取り出し)
キュー	651ms
スタック	586ms

キューとして使ってもスタックとして使っても、このクラスが原因で性能問題が起きるようなものではなさそうです。
なお、測定に使用したコードと環境は以下の通りです。

static void timeCount() {
    long time = 0;
    for ( int i = 0 ; i < 100 ; i++ ) {
        time += exec(1000000, 100);
    }
    System.out.println(String.format("time: %d[ms]", time / 100));
}

static long exec(int N, int K) {
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    long a = 0;
    long start = System.currentTimeMillis();
    for ( int i = 0 ; i < N ; i++ ) {
        for ( int j = 0 ; j < K ; j++ ) {
            queue.add(i);
        }
        while ( queue.size() > 0 ) {
            a += queue.poll(); // スタックの場合はpollLast()
        }
    }
    long end = System.currentTimeMillis();
    return end - start;
}

• 測定マシン：Mac mini(2018)
  • CPU: 3.6 GHz クアッドコアIntel Core i3
  • メモリ: 16GB
• 実行環境
  • Java 8

メソッドの整理

ついでなので、その他のメソッドについても整理してみました。基本的にはDequeインターフェースのドキュメントにまとめられていますが、機能・位置・特殊値の取り扱いで整理すると見通しが良くなると思います。

メソッド	機能	位置	特殊値
addFirst(e)	追加	先頭	NullPointerException
addLast(e), add(e)	追加	末尾	NullPointerException
offerFirst(e)	追加	先頭	NullPointerException(※)
offerLast(e), offer(e)	追加	末尾	NullPointerException(※)
removeFirst(), remove()	取得＆削除	先頭	NoSuchElementException
removeLast()	取得＆削除	末尾	NoSuchElementException
pollFirst(), poll()	取得＆削除	先頭	null
pollLast()	取得＆削除	末尾	null
getFirst(), element()	取得	先頭	NoSuchElementException
getLast()	取得	末尾	NoSuchElementException
peekFirst(), peek()	取得	先頭	null
peekLast()	取得	末尾	null

「特殊値」の列は追加系は追加する値がnullだった場合、取得(+削除)系は取得すべき値が存在しない場合を表しています。混乱しがちなポイントを以下に整理しておきます。

• offer系で、null値を追加しようとした場合、Dequeのドキュメント上はfalseを返してきそうな雰囲気があるが、ArrayDequeのドキュメントをきちんと読むとわかるように例外となる(「※」を付けた部分)
• したがって、add系とoffer系は同じ動作
• First, Lastがつかないメソッドは、追加系はLast, 取得系はFirstとして動作(FIFOのキューの振る舞い)
• getだけは省略系がelement()

結論

結論としては、通常使用する範囲では以下を覚えておけば良いと思います。

• キュー(FIFO)として使用する場合
  • 追加：add(e)
  • 取得＆削除：poll()
  • 取得：peek()
• スタック(LIFO)として使用する場合
  • 追加：add(e)
  • 取得＆削除：pollLast()
  • 取得：peekLast()