Javaのコレクション「Queue」「Deque」とは？便利な使い方も紹介！

ArrayDeque

一般的な両端キュー(FIFO・LIFO)

PriorityQueue

自然な順序付けで優先順位を決める優先キュー

マルチスレッドに対応したQueue

今回は紹介だけですが、マルチスレッドに対応したQueueも存在します。

「BlockingQueue」「BlockingDeque」「TransferQueue」というインターフェースで、
「LinkedBlockingQueue」「LinkedBlockingDeque」「LinkedTransferQueue」

「ArrayBlockingQueue」「SynchronousQueue」「DelayQueue」「PriorityBlockingQueue」
などと、なんかすごいいっぱいあります・・・。

もしマルチスレッドを使用する環境で使用するのであれば、こういう事を考慮しないといけません。

初期化する

Queueオブジェクトを初期化(生成)します。

基本的に引数は指定しなくてもいいですが、「初期容量」を指定できます。

何かというと、オブジェクト生成時にまず、初期容量分の保存領域を確保します。

そして要素を追加していく中で、初期容量の負荷係数個に到達すると、保存領域を拡張します。

この要領を拡張するという動作が非常に重たい動作になるので、できる限り最適に設定していきたいので、
最初からある程度量が分かっているのであれば、指定してあげるとパフォーマンスがよくなります。

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> deque1 = new ArrayDeque<>();
    // 初期容量100のインスタンスを生成
    Deque<String> deque2 = new ArrayDeque<>(100);
  }
}

要素を追加する

要素を追加するときは、最初か最後に追加することになります。

「add」は、追加に失敗した場合、例外が発生します。

「offer」は、追加に成功した場合はtrueを、失敗した場合はfalseを返却してくれます。

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCar = new ArrayDeque<>();
    // 先頭に追加(失敗時例外)
    // [車A]
    orderByCar.addFirst("車A");
    // 末尾に追加(失敗時例外)
    // [車A, 車B]
    orderByCar.addLast("車B");
    // 先頭に追加(成否結果返却)
    // [車C, 車A, 車B]
    orderByCar.offerFirst("車C");
    // 末尾に追加(成否結果返却)
    // [車C, 車A, 車B, 車D]
    orderByCar.offerLast("車D");
  }
}

要素を取得 & 削除する

要素の最初か最後を取得しつつ削除します。

「remove」は、取得(削除)に成功した場合は取得した値を返却し、失敗した場合は例外が発生します。

「poll」は、取得(削除)に成功した場合は取得した値を、追加に失敗した場合はnullを返却してくれます。

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCar = new ArrayDeque<>();
    // 追加 [車A, 車B, 車C, 車D, 車E]
    orderByCar.addLast("車A");
    orderByCar.addLast("車B");
    orderByCar.addLast("車C");
    orderByCar.addLast("車D");
    orderByCar.addLast("車E");
    // 先頭を取得&削除(失敗時例外) > 車A
    // [車B, 車C, 車D, 車E]
    orderByCar.removeFirst();
    // 末尾を取得&削除(失敗時例外) > 車E
    // [車B, 車C, 車D]
    orderByCar.removeLast();
    // 先頭を取得&削除(失敗時null) > 車B
    // [車C, 車D]
    orderByCar.pollFirst();
    // 末尾を取得&削除(失敗時null) > 車D
    // [車C]
    orderByCar.pollLast();
  }
}

要素を取得する

要素の最初か最後を取得します。

先ほどとは違い、取得するだけで削除はされません。

「get」は、取得に成功した場合は取得した値を返却し、失敗した場合は例外が発生します。

「peek」は、取得に成功した場合は取得した値を、追加に失敗した場合はnullを返却してくれます。

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCar = new ArrayDeque<>();
    // 追加 [車A, 車B, 車C]
    orderByCar.addLast("車A");
    orderByCar.addLast("車B");
    orderByCar.addLast("車C");
    // 先頭を取得(失敗時例外) > 車A
    orderByCar.getFirst();
    // 末尾を取得(失敗時例外) > 車C
    orderByCar.getLast();
    // 先頭を取得(失敗時null) > 車A
    orderByCar.peekFirst();
    // 末尾を取得(失敗時null) > 車C
    orderByCar.peekLast();
  }
}

要素の数を取得する

QueueやDeque内の要素の数を取得します。

取得できる数は人間が数える数字と同じなので、1個・2個と数えるやり方と同じです。

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCar = new ArrayDeque<>();
    // 中身の数を取得 > 0
    orderByCar.size();
    // 追加 [車A]
    orderByCar.addLast("車A");
    // 中身の数を取得 > 1
    orderByCar.size();
    // 追加 [車A, 車B]
    orderByCar.addLast("車B");
    // 中身の数を取得 > 2
    orderByCar.size();
  }
}

要素があるか判定する

QueueやDequeに要素があるかどうかを判定します。

ただし完全一致しないと存在しないと判定されます。

例だと「車A」に「車」は含まれてはいますが、
完全一致はしないので、containsはfalseを返します。

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCar = new ArrayDeque<>();
    // 追加 [車A, 車B, 車C]
    orderByCar.addLast("車A");
    orderByCar.addLast("車B");
    orderByCar.addLast("車C");
    // 中身に存在するかを判定
    if (orderByCar.contains("車B")) {
      // 今回は存在するのでtrue
    }
    if (!orderByCar.contains("車")) {
      // 今回は完全一致しないのでtrue
    }
  }
}

Queueとして動かす

先ほどまでDequeで動かしていましたが、もちろんQueueとしてでも動かせます。

ただ最初か最後、どちらに追加されるかを意識しないと、少しわかりにくいです。

使い方は、Dequeで紹介したメソッドの「First」「Last」がないバージョンです。

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.Queue;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCarDeque = new ArrayDeque<>();
    // 末尾に追加(失敗時例外)
    // [車A]
    orderByCarDeque.add("車A");
    // 末尾に追加(成否結果返却)
    // [車A, 車B]
    orderByCarDeque.offer("車B");
    // LIFOに変換
    Queue<String> orderByCarQueue = Collections.asLifoQueue(orderByCarDeque);
    // 先頭に追加(失敗時例外)
    // [車C, 車A, 車B]
    orderByCarQueue.add("車C");
    // 先頭に追加(成否結果返却)
    // [車D, 車C, 車A, 車B]
    orderByCarQueue.offer("車D");
  }
}

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.Queue;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCarDeque = new ArrayDeque<>();
    // 追加 [車A, 車B, 車C, 車D, 車E]
    orderByCarDeque.addLast("車A");
    orderByCarDeque.addLast("車B");
    orderByCarDeque.addLast("車C");
    orderByCarDeque.addLast("車D");
    orderByCarDeque.addLast("車E");
    // 先頭を取得&削除(失敗時例外) > 車A
    // [車B, 車C, 車D, 車E]
    orderByCarDeque.remove();
    // 先頭を取得&削除(失敗時null) > 車B
    // [車C, 車D, 車E]
    orderByCarDeque.poll();
    // LIFOに変換
    Queue<String> orderByCarQueue = Collections.asLifoQueue(orderByCarDeque);
    // 先頭を取得&削除(失敗時例外) > 車C
    // [車D, 車E]
    orderByCarQueue.remove();
    // 先頭を取得&削除(失敗時null) > 車D
    // [車E]
    orderByCarQueue.poll();
  }
}

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.Queue;

public class QueueTest {
  public static void main(String[] args) {
    // インスタンスを生成
    Deque<String> orderByCarDeque = new ArrayDeque<>();
    // 追加 [車A, 車B, 車C]
    orderByCarDeque.addLast("車A");
    orderByCarDeque.addLast("車B");
    orderByCarDeque.addLast("車C");
    // 先頭を取得(失敗時例外) > 車A
    orderByCarDeque.element();
    // 先頭を取得(失敗時null) > 車A
    orderByCarDeque.peek();
    // LIFOに変換
    Queue<String> orderByCarQueue = Collections.asLifoQueue(orderByCarDeque);
    // 先頭を取得(失敗時例外) > 車A
    orderByCarQueue.element();
    // 先頭を取得(失敗時null) > 車A
    orderByCarQueue.peek();
  }
}