東大ニート

東大卒のニートが勉強したことをメモするブログ

<Java>Dequeインターフェースの使い方

深さ優先探索をする時にスタック使いたいなーと思ったので、Dequeインターフェースについて勉強してみました。Javaでスタックを実装する場合は、どうやらStackクラスを使うより、Dequeインターフェースを使ったほうがよいようです。

Dequeはデックと読みます。Double Ended Queueの略で、Collectionの前方と後方、双方に対して処理を実行できます。

ちなみにキューならQueueインターフェースがありますね。

 以下のサイトを参考にさせていただきました。

d.hatena.ne.jp

 

Dequeインターフェースの使い方

以下の例では、実装クラスとしてArrayDequeクラスを使用しています。

  1. import java.util.Deque;

  2. import java.util.ArrayDeque;

  3. public class TestDeque01 {

  4.        public static void main(String args[]){

  5.               Deque<Integer> ad = new ArrayDeque<Integer>();

  6.               ad.offerFirst(1);

  7.               ad.offerFirst(2);

  8.               ad.offerFirst(3);

  9.               for (Integer num: ad) {

  10.                      System.out.println(num);

  11.               }

  12.        }

  13. }

上記のコードを実行すると、以下の結果が出力されます。

3
2
1

ポイント1. Dequeインターフェースのインポート(1・2行目)

まず、java.utilパッケージに含まれるDequeインターフェースをインポートします。
「import java.util.Deque;」を記述します。

また、実装クラスを使用する場合は、「import java.util.ArrayDeque;」のようにクラスをインポートします。

ポイント2. ArrayDequeインスタンスの作成(6行目)

DequeインターフェースやArrayDequeクラスはコレクションフレームワークに含まれるため、ジェネリクス機能を持ちます。「<>」の中に型を指定しましょう。

Integer型の要素を持つArrayDequeインスタンス「ad」を作成する場合
「Deque<Integer> ad = new ArrayDeque<Integer>();」と記載します。

 

各実装クラスの特徴

  • ArrayDeque

配列構造でデータを持つ。両端への処理はLinkedListより高速。特殊な場合を除いて、ArrayDequeを使っていれば良さそう。

  • ConcurrentLinkedDeque

並行処理コレクション。複数スレッドから同時に操作できる。

  • LinkedBlockingDeque

容量制限がある。

  • LinkedList

リスト構造でデータを持つ。

 

Dequeインターフェースのメソッド

上記のコード例では「offerFirst」メソッド(7〜9行目)を使用しています。

代表的なメソッドを整理すると以下のようになります(Java Platform SE 8より引用)。

  最初の要素(先頭) 最後の要素(末尾)
例外のスロー 特殊な値 例外のスロー 特殊な値
挿入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
削除 removeFirst() pollFirst() removeLast() pollLast()
検査 getFirst() peekFirst() getLast() peekLast()

「例外のスロー」列のadd・remove・getは操作が失敗した時に例外をスローし、「特殊な値」列のoffer・poll・peekは操作に応じてnullまたはfalseを返します。

また、First/Lastのつかない、addとofferは末尾への処理、removeとpollとpeekは先頭への処理を行います(getメソッドはありません)。

スタックとして使う場合は挿入と削除(検査)について、同一の方向から処理を行えばいいので、例えばofferLastでデータを挿入し、pollLastでデータを処理します。

 

次回は深さ優先探索について書いてみます。