DequeとStackと

最近、JavaでStackを使ったプログラムを書こうとして、「Concurrent系のStackってないんだっけ？」と思ってふと調べたら、そもそももっと大きな見落としをしていることを知りました…。

Java SE 6から、Stackの代替としてDequeというものを使うようになってたんですね。

Javadocを見てる時に、Queueは使っていたので「なんか隣にいるなぁ〜」くらいに思っていたのですが、Stackの代替として使えるものができていたとは。

Stackって、今のJDKだと古いクラスですからねぇ。

java.util.Dequeインターフェース
http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

Queueとしても使うことができ、Stackとしても使うことができるクラスだそうな。実装は、JDK 7だと以下の4つ。

java.util.ArrayDeque
java.util.LinkedList
java.util.cuncurrent.ConcurrentLinkedDeque
java.util.concurrent.LinkedBlockingDeque

ConcurrentLinkedDequeは、JDK 7からです。

ArrayDequeがある種の標準実装？キューとして使う場合はLinkedListよりも高速で、スタックとして使用する場合はStackよりも高速なのだそうです。

QueueおよびStackとのメソッドの比較は先のJavadocに載っているのですが、こちらにも説明があります。
http://itpro.nikkeibp.co.jp/article/COLUMN/20070831/280866/

では、ちょっと使ってみます。

Stackとの比較

Stackの代替として使うことが目的だったので、ドキュメントに沿ってStackとして使ってみます。

Stackのpush／popの代わりには、DequeのaddFirst／removeFirstを使用します。

        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();

        System.out.printf("stack = %s, deque = %s%n", stack, deque);

        stack.push("Java");
        stack.push("Groovy");
        stack.push("Scala");

        deque.addFirst("Java");
        deque.addFirst("Groovy");
        deque.addFirst("Scala");

        System.out.printf("stack = %s, deque = %s%n", stack, deque);

        System.out.printf("Stack#pop = %s, Deque#removeFirst = %s%n", stack.pop(), deque.removeFirst());
        System.out.printf("Stack#pop = %s, Deque#removeFirst = %s%n", stack.pop(), deque.removeFirst());
        System.out.printf("Stack#pop = %s, Deque#removeFirst = %s%n", stack.pop(), deque.removeFirst());

        System.out.printf("stack = %s, deque = %s%n", stack, deque);

        try {
            stack.pop();
        } catch (EmptyStackException e) {
            System.out.printf("Stack#pop = %s%n", e);
        }

        try {
            deque.removeFirst();
        } catch (NoSuchElementException e) {
            System.out.printf("Deque#removeFirst = %s%n", e);
        }

stack = [], deque = []
stack = [Java, Groovy, Scala], deque = [Scala, Groovy, Java]
Stack#pop = Scala, Deque#removeFirst = Scala
Stack#pop = Groovy, Deque#removeFirst = Groovy
Stack#pop = Java, Deque#removeFirst = Java
stack = [], deque = []
Stack#pop = java.util.EmptyStackException
Deque#removeFirst = java.util.NoSuchElementException

DequeがLIFOスタックとして機能していることが分かりますが、格納される順番は逆ですね。まあ、前に追加していって前から抜いていくのでそうですよねー。

Stack#peekの代わりには、Deque#peekFirstを使います。

        stack.push("Java");
        stack.push("Groovy");
        stack.push("Scala");

        deque.addFirst("Java");
        deque.addFirst("Groovy");
        deque.addFirst("Scala");

        System.out.printf("stack = %s, deque = %s%n", stack, deque);
        System.out.printf("Stack#pop = %s, Deque#peekFirst = %s%n", stack.peek(), deque.peekFirst());
        System.out.printf("stack = %s, deque = %s%n", stack, deque);

Stack#pop、Deque#peekFirstでは、要素の数は変わりません。

stack = [Java, Groovy, Scala], deque = [Scala, Groovy, Java]
Stack#pop = Scala, Deque#peekFirst = Scala
stack = [Java, Groovy, Scala], deque = [Scala, Groovy, Java]

offerFirst、pollFirst、getFirst

ここからは、スタックとしてのDequeのメソッドの中でも、直接Stackと対比されていないものについて。

Stackとの比較として

Stack	Deque
push	addFirst
pop	removeFirst
peek	peekFirst

と言っているものの、Stack#pushはAPIドキュメント上失敗については書かれていませんが、Deque#addFirstは容量制限のために追加できなかった場合は、IllegalStateExceptionがスローされるのだとか。

で、これ以外のものとしてofferFirst、pollFirst、getFirstがあります。それぞれ、addFirst、removeFirst、getFirstから少し動きが変わるものになります。

        deque.offerFirst("Java");    // 容量制限のあるDequeを使用する場合は、#addFirstよりこちらを使う
        deque.offerFirst("Groovy");  // 戻り値は成功時はtrue、失敗時はfalse
        deque.offerFirst("Scala");

        System.out.printf("deque = %s%n", deque);

        System.out.printf("Deque#pollFirst = %s%n", deque.pollFirst());  // #removeFirstと異なり、Dequeが空でも
        System.out.printf("Deque#pollFirst = %s%n", deque.pollFirst());  // 例外をスローせずnullを返却する
        System.out.printf("Deque#pollFirst = %s%n", deque.pollFirst());

        System.out.printf("deque = %s%n", deque);

        deque.clear();

        deque.offerFirst("Java");
        deque.pollFirst();

        try {
            deque.getFirst();  // #peekFirstと異なり、Dequeが空の場合は例外をスロー
        } catch (NoSuchElementException e) {
            System.out.printf("Deque#getFirst = %s%n", e);
        }

各メソッドの対比は、コメント中に書いておきました。

実行。

deque = [Scala, Groovy, Java]
Deque#pollFirst = Scala
Deque#pollFirst = Groovy
Deque#pollFirst = Java
deque = []
Deque#getFirst = java.util.NoSuchElementException

で、ここでいう「容量制限のあるDeque」とは、JDK 7では

java.util.concurrent.LinkedBlockingDeque

が該当します。

ところで、当初の目的であった「ConcurrentなStack」ですが、JDK 7で追加された以下のクラスが該当します。

java.util.cuncurrent.ConcurrentLinkedDeque

なんですけど、最終的にもうちょっとロックの範囲を広げる必要が出てきて、synchronizedを使うことになりましたとさ…。

それよりも、Java SE 6の時にDequeを知らなかったことがショックでしたー。