Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.学ぶ Javaにおけるデックデータ構造 | Javaにおける高度なデータ構造
Javaデータ構造

bookJavaにおけるデックデータ構造

メニューを表示するにはスワイプしてください

両端キュー

Deque（両端キュー）は、キューの前方と後方の両方から操作を行うためのデータ構造。

DequeインターフェースはQueueインターフェースを拡張しているため、LinkedListのようなクラスもこのインターフェースを実装している。

そのため、再びLinkedListを使用するが、今回は新しいインターフェースで利用する。

Deque型でオブジェクトを宣言する方法は、Queueの場合と変わらない。

Main.java

Main.java

copy

              
1

            
Deque<T> deque = new LinkedList<>();

主な違いは、このインターフェースのメソッドに関して現れます。

Dequeは両端キューであり、キューの先頭と末尾の両方で要素を操作できるため、そのメソッドはこの特徴に合わせて設計されています。

メソッド

Dequeインターフェースの主なメソッドには以下があります：

  • addFirst(element): デックの先頭に要素を追加;
  • addLast(element): デックの末尾に要素を追加。

明らかに、デックには先頭と末尾に追加するためのメソッドが用意されています。これらのメソッド名は直感的です。 これらのメソッドをコードで確認します：

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addFirst("One");
        deque.addLast("Two");
        System.out.println("Deque: " + deque);
        deque.addFirst("Zero");
        System.out.println("Deque after the `addFirst()` method: " + deque);
    }
}

ご覧のとおり、addFirst() メソッドを使用すると、要素がデックの先頭に追加されます。これは addLast() メソッドとの違いです。

Deque には通常の add() メソッドもあり、これは addLast() メソッドと同じ動作をします。そのため、どのメソッドを使用するかは完全に任意です。

削除メソッド

先頭や末尾に要素を追加するメソッドがある場合、デックの先頭や末尾から削除するメソッドも存在します。

  • removeFirst(): デックの先頭から要素を削除して返す；
  • removeLast(): デックの末尾から要素を削除して返す。

addFirst() および addLast() メソッドは、デックの先頭や末尾から要素を削除します。

コードでの使用例を見てみましょう:

Main.java

Main.java

copy

              
1234567891011121314151617

            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.add("One");
        deque.add("Second");
        deque.add("Third");
        System.out.println("Deque: " + deque);
        deque.removeFirst();
        deque.removeLast();
        System.out.println("Deque after the removal methods method: " + deque);
    }
}

ご覧のとおり、デックから最初と最後の要素を削除し、2番目の要素だけが残っています。

シンプルで便利であり、メソッド名も直感的です。

取得メソッド

次に、デック内の要素へアクセスするメソッドについて説明します。

  • getFirst(): デックの先頭要素を取得しますが、削除はしません；
  • getLast(): デックの末尾要素を取得しますが、削除はしません。

これにより、両端キューの最初と最後の要素にアクセスできます。

それでは、コード例を見てみましょう:

Main.java

Main.java

copy

              
123456789101112131415161718

            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.add("One");
        deque.add("Second");
        deque.add("Third");
        System.out.println("Deque: " + deque);
        String first = deque.getFirst();
        String last = deque.getLast();
        System.out.println("The first element in the deque: " + first);
        System.out.println("The last element in the deque: " + last);
    }
}

getFirst() および getLast() メソッドを使用して、deque から最初と最後の要素を取得し、新しく作成した変数に代入しました。

Deque インターフェースには、peekFirst() および peekLast() メソッドもあり、例外がスローされる問題に対応しています。例外をスローしてプログラムを停止する代わりに、キューが空の場合は null を返します。

例を見てみましょう:

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        System.out.println("Deque: " + deque);
        String first = deque.peekFirst();
        System.out.println("The first element in the deque: " + first);
        String last = deque.getLast();
        System.out.println("The last element in the deque: " + last);
    }
}

この例から、peekFirst() や peekLast() よりも getFirst() および getLast() メソッドを使用する方がはるかに良いことが明らかになりました。これらはエラー時にプログラムを停止させません。

ただし、NullPointerException には注意が必要です。この例外はプログラムに多くの問題を引き起こす可能性があります。

addFirst()、addLast()、removeFirst()、removeLast() メソッドには、同等の代替メソッドも存在します。これらのメソッドの動作はすでに理解しているため、詳細な説明は省略しますが、以下に一覧を示します。

代替メソッド

Deque に要素を追加するためのメソッド：

  • offerFirst(E e): 可能であれば要素をデックの先頭に追加し、true を返します。追加できない場合は false を返します；
  • offerLast(E e): 可能であれば要素をデックの末尾に追加し、true を返します。追加できない場合は false を返します；
  • push(E e): 要素をデックの先頭に追加します。addFirst() と同様です。push() は Deque クラスのスタックメソッドでもあることに注意してください。

Deque から要素を削除するためのメソッド：

  • pollFirst(): デックの最初の要素を削除して返します。デックが空の場合は null を返します；
  • pollLast(): デックの最後の要素を削除して返します。デックが空の場合は null を返します；
  • pop(): デックの最初の要素を削除して返します。removeFirst() と同様です。

選択はプログラムの要件によって異なります。すべてを通常の配列で解決することも可能ですが、それは非常に困難であり、最適化もされません。そのため、さまざまなデータ構造が存在し、さまざまなプログラムの作成をより便利にしています。

1. 「Deque」は何の略ですか？

2. JavaでDequeを表すインターフェースはどれですか？

3. DequeにおけるaddFirst()メソッドの目的は何ですか？

4. Dequeの末尾要素を取得するが削除しないメソッドはどれですか？

question mark

「Deque」は何の略ですか？

正しい答えを選んでください

question mark

JavaでDequeを表すインターフェースはどれですか？

正しい答えを選んでください

question mark

DequeにおけるaddFirst()メソッドの目的は何ですか？

正しい答えを選んでください

question mark

Dequeの末尾要素を取得するが削除しないメソッドはどれですか？

正しい答えを選んでください

すべて明確でしたか？

どのように改善できますか？

フィードバックありがとうございます！

セクション 2. 章 2

AIに質問する

expand

AIに質問する

ChatGPT

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 2. 章 2
some-alt