Java Deque は、通常のキューとスタックを組み合わせたデータ構造です。Deque の先頭と末尾の両方に要素を追加したり削除したりできます。「従来の」キューでは、行の末尾 (最後の要素の後) に要素を追加し、キューの先頭から要素を削除します。この原則は先入れ先出し (FIFO) と呼ばれ、現実の通常の顧客の列と同様に機能します。Java では、キューはコレクション フレームワークの一部であるインターフェイスです。 Java Deque インターフェイス - 1 また、スタックと呼ばれる重要なデータ構造もあります。これは、完全に逆の原理、LIFO (後入れ先出し) で要素を操作するリストです。これはプレートの積み重ねに似ており、追加または削除は上部でのみ可能です。 Java Deque インターフェイス - 2

キューとデック

Deque はちょっと変わったタイプの Queue です。行の末尾と先頭の両方に新しい要素を追加できます。削除についても同じです。この構造から最後の要素または最初の要素を削除できます。したがって、スタックとキューが混在しているように見えます。 Java Deque インターフェイス - 3「Deque」という名前は「Double Ended Queue」を意味します。「Deque」はカードの「デッキ」のように発音されます。これは実際のトランプのデッキに似ています。デッキの一番下または一番上からカードを 1 枚取ります。線形構造の両側から要素を追加または削除したいですか? デクを使用します。Java 8 またはその他のほぼすべてのバージョンがこれをサポートしています。典型的なレゴ ブロックと、そのブロックで作られた 1 つの柱の「塔」を想像してください。新しいレンガをタワーの上部または下部に追加できます。両側からレンガを削除することもできます。ここに例があります。すべての黄色のレンガを上部に追加し、すべての赤色のレンガを下部に追加します。この例を Java コードを使用してすぐに説明します。 Java Deque インターフェイス - 4したがって、Java Deque の両端からエンキューとデキューを行うことができます。つまり、Deque をキューとスタックの両方として使用できることになります。Java のスタックについて読む: Java スタック 101: スタック クラスの詳細 Java のキューについて読む: Java キュー インターフェイスとその実装

デクの特徴

  • Java の Deque はインターフェイスであり、その実装によりサイズ変更可能な配列のサポートが提供されます。したがって、制限のない一連の容量があり、ニーズに応じて新しい要素を追加できます。
  • 複数のスレッドによる同時アクセスは Deque ではサポートされていません
  • 外部同期がない場合、Deque はスレッドセーフではありません。
  • 配列デキューでは Null 要素は許可されません。

Java インターフェース宣言のデキュー


public interface Deque<E> extends Queue<E>

Java Deque メソッド

java.util.Deque は、Java キュー インターフェイスを拡張するインターフェイスであり、両端のキューを表します。したがって、Deque の操作中にすべての Java Queue メソッドを使用できます。Deque は Stack インターフェイスを拡張しませんが、Deque インターフェイスは、 Push、Peak、Popなどの一般的なスタック操作を実行できるメソッドを定義します。
  • boolean add(element) は、 Deque の末尾に要素を追加します。成功した場合は true を返し、現在使用可能なスペースがない場合は IllegalStateException をスローします。
  • addFirst(element) は、 Deque の先頭に要素を追加します。
  • addLast(element) は、 Deque の末尾に要素を追加します。
  • offer(element)は要素を末尾に追加し、挿入が成功したかどうかを説明するブール値を返します。
  • offerFirst(element)は要素を head に追加し、挿入が成功したかどうかを説明するブール値を返します。
  • offerLast(element)は要素を末尾に追加し、挿入が成功したかどうかを説明するブール値を返します。
  • iterator() は両端キューのイテレータを返します。
  • decendingIterator() は、この両端キューに対して逆の順序を持​​つ反復子を返します。
  • Push(element)はheadに要素を追加します。
  • Pop(element) は、 head から要素を削除して返します。
  • RemoveFirst() は先頭の要素を削除します。
  • RemoveLast() は末尾の要素を削除します。
  • poll() は、この両端キューによって表されるキューの先頭 (つまり、この両端キューの最初の要素) を取得して削除します。この両端キューが空の場合は null を返します。
  • pollFirst() は、この両端キューの最初の要素を取得して削除します。この両端キューが空の場合は null を返します。
  • pollLast() は、この両端キューの最後の要素を取得して削除します。この両端キューが空の場合は null を返します。
  • Peak()は、この両端キューで表されるキューの先頭 (つまり、この両端キューの最初の要素) を取得しますが、削除はしません。この両端キューが空の場合は null を返します。
  • PeakFirst()は、この両端キューの最初の要素を取得しますが、削除はしません。この両端キューが空の場合は null を返します。
  • PeakLast()は、この両端キューの最後の要素を取得しますが、削除はしません。この両端キューが空の場合は null を返します。
以下の表では、すべてのメソッドがグループごとに分類されています。ご覧のとおり、要素を追加および削除するにはさまざまな方法があります。たとえば、removeFirst() と Pop() はどちらも両端キューから最初の要素を削除します。2 番目のものはスタックから「来た」ものです。つまり、ArrayDeque をスタックとしてのみ使用する場合は、削除には Pop()、追加には Push()、検査には Peak() を使用します。これにより、コードが他の開発者にとってより賢明なものになります。
最初の要素 (頭) 最後の要素 (テール)
手術 例外をスローする 特別な価値 例外をスローする 特別な価値
挿入 addFirst(e)/push(e) オファーファースト(e) addLast(e) OfferLast()
削除 RemoveFirst()/pop() ポールファースト() 削除最後() ポールラスト()
診る getFirst() ピークファースト()/ピーク() getLast() ピークラスト()

デックの実装

Java Deque はインターフェースであり、Java Collections API に実装されています。
  • java.util.LinkedList //List と Deque の実装
  • java.util.ArrayDeque //Deque実装、Javaライブラリ
Java Deque インターフェイス - 5LinkedList クラスは、内部で二重リンク リストを使用してキューまたは両端キューをモデル化します。ArrayDeque クラスは要素を内部的に配列に格納します。要素の数が配列のボリュームを超える場合、新しい配列が割り当てられ、すべての要素が上に移動されます。つまり、ArrayDeque はニーズに応じて成長します。

ArrayDeque クラス

ArrayDeque <E>クラスは、AbstractCollection クラスから機能を継承し、Deque インターフェイスを使用する一般的な 2 方向のキューです。ArrayDeque は、deque とサイズ変更可能な配列を使用する機能を提供します。最初、配列はサイズ 16 で初期化されます。配列は双方向キューとして実装され、2 つのポインター、つまり先頭と末尾をサポートします。AbstractCollectionクラスを継承し、 Dequeインターフェイスを実装します。ArrayDeque クラスに関する重要な点は次のとおりです。
  • ArrayDeque の末尾と先頭の要素を追加または削除できます。
  • Null 要素は許可されません
  • ArrayDeque は、外部同期がない場合、スレッド セーフではありません。
  • ArrayDeque には容量制限はありません。

ArrayDeque クラスのコンストラクター

  • ArrayDeque() は空のキューを作成します。
  • ArrayDeque (Collection <? Extends E> コレクション) は、 Collection コレクション要素で満たされたキューを作成します。
  • ArrayDeque (int Capacity) は、初期容量のキューを作成します。初期容量を指定しない場合、デフォルトの容量は 16 です。

Java Deque の例 — ArrayDeque

記事冒頭のレゴタワーの例を覚えていますか? レゴ ブロックで 1 列のタワーを構築するクラスを作成しましょう。レンガは赤、黄色、青のいずれかになります。私たちのタワー建築ルール: 赤レンガを下に置き、黄色レンガを上に置きます。大きな Java Deque の例 

//enum with colors 
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color   
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}
これがタワークラスです。タワーを開始します。開始されるタワーは、赤と黄色の量によって異なります。タワーにレンガを追加したり、削除したりできます。レンガが黄色の場合は上に追加し、赤の場合は下にレンガを追加します。 

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here 
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}
このプログラムを実行した結果: 

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements: 
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0
待って、何?? なぜ赤が上にあるのですか？いいえ、そうではありません。最初 (下) から最後 (上) までコンソールに出力するだけです。したがって、上のレンガを使用した図のようなものを表示したい場合は、LegoTower クラスのdrawTower メソッドを変更するとよいでしょう。とても簡単な作業です！

リンクリスト

List インターフェイスは項目の追加順序を保持し、インデックスによる項目へのアクセスを許可します。Deque は双方向のキューであり、両側からの要素の追加と削除をサポートします。 Java Deque インターフェイス - 6LinkedList は主に List 実装として知られていますが、このクラスは Deque も実装しており、null を含む任意のオブジェクトで構成される双方向キューを作成できます。LinkedList は要素のコレクションです。これはクラスのコード ソースで確認できます。今回はフィールドに注目してください。ここでは 1 つの例を追加しますが、LinkedList について詳しく知りたい場合は、このCodeGym の記事へようこそ。

Java でのリンク リストの実装、要素の追加と削除。例

これらの操作を実際に試してみましょう。まず、Java LinkedList の実装です。文字列の LinkedList を作成し、そこに 3 つの要素を追加します。次に、1 つを削除し、真ん中に 1 つ追加します。 

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }
このプログラムを実行した結果: 

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]