deque java deque implementation
このチュートリアルでは、JavaのDequeまたは「両端キュー」について詳しく説明します。 Dequeインターフェース、APIメソッド、実装などについて学習します。
JavaのDequeまたは「両端キュー」は、両端から要素を挿入または削除できるデータ構造です。 dequeは、java.utilパッケージに属するJavaのインターフェースであり、java.queueインターフェースを実装します。
dequeは、スタック（後入れ先出し）構造またはキュー（先入れ先出し）として実装できます。 Dequeは、StackやLinkedListよりも高速です。 Dequeは、「カードのデッキ」と同様に「デッキ」と発音されます。
=> ここでJavaトレーニングチュートリアルのA〜Zを確認するには、ここをクリックしてください。
学習内容：
Javaについて
典型的なdequeコレクションは次のようになります。
YouTubeのビデオをmp3に変換するための最良の方法
Dequeは主に、スタック、キュー、またはリストのデータ構造を実装するために使用されます。また、優先キューを実装するために使用することもできます。 Webブラウザに主に存在する元に戻す機能または履歴の機能は、両端キューを使用して実装できます。
JavaDequeインターフェイス
次の図は、両端キューまたは両端キューの階層を示しています。次の図に示すように、DequeインターフェースはQueueインターフェースまで拡張され、QueueインターフェースはCollectionインターフェースを拡張します。
プログラムでdequeインターフェースを使用するには、以下に示すように、importステートメントを使用してdeque機能を保持するパッケージをインポートする必要があります。
import java.util.deque; または
import java.util.*; dequeはインターフェースであるため、dequeインターフェースの機能を実装するための具象クラスが必要です。
以下の2つのクラスは、dequeインターフェイスを実装します。
- ArrayDeque
- LinkedList
したがって、以下に示すように、これら2つのクラスを使用してdequeオブジェクトを作成できます。
Deque numdeque = new ArrayDeque (); Deque strDeque = new LinkedList (); したがって、上記のdequeオブジェクトが正常に作成されると、dequeインターフェイスの機能を使用できるようになります。
以下に、dequeについて注意すべきいくつかの重要なポイントを示します。
- Dequeインターフェースは、必要に応じて拡張できるサイズ変更可能な配列をサポートします。
- 配列両端キューでは、Null値を使用できません。
- Dequeは、複数のスレッドによる同時アクセスをサポートしていません。
- 外部同期が提供されない限り、Dequeはスレッドセーフではありません。
JavaのArrayDeque
ArrayDequeはjava.utilパッケージに属しています。 dequeインターフェースを実装します。内部的には、ArrayDequeクラスは、要素の数が増えるにつれて大きくなる動的にサイズ変更可能な配列を利用します。
次の図は、ArrayDequeクラスの階層を示しています。
図に示すように、ArrayDequeクラスはAbstractCollectionクラスを継承し、Dequeインターフェースを実装します。
Webサイトでddos攻撃を実行する方法
以下に示すように、ArrayDequeクラスを使用してdequeオブジェクトを作成できます。
Deque deque_obj = new ArrayDeque (); および例
次のJavaプログラムは、両端キューをよりよく理解するための簡単な例を示しています。ここでは、ArrayDequeクラスを使用してdequeインターフェイスをインスタンス化しました。 dequeオブジェクトにいくつかの要素を追加し、forEachループを使用してそれらを出力しました。
import java.util.*; public class Main { public static void main(String() args) { //Creat a Deque and add elements Deque cities_deque = new ArrayDeque(); cities_deque.add('Delhi'); cities_deque.add('Mumbai'); cities_deque.add('Bangaluru'); System.out.println('Deque Contents:'); //Traverse the Deque for (String str : cities_deque) { System.out.print(str + ' '); } } } 出力：
JavaAPIとメソッド
dequeインターフェイスはキューインターフェイスを実装しているため、キューインターフェイスのすべてのメソッドをサポートします。さらに、dequeインターフェースは、dequeオブジェクトでさまざまな操作を実行するために使用できる次のメソッドを提供します。
これらの方法を次の表にまとめましょう。
| 方法 | メソッドプロトタイプ | 説明 |
|---|---|---|
| getFirst | E getFirst（） | dequeの最初の要素を削除せずに取得します。 |
| 追加 | boolean add（E e） | 容量制限に違反することなく、指定された要素eを両端キュー（末尾）に追加し、成功した場合はtrueを返します。 dequeに使用可能なスペースがない場合、IllegalStateExceptionをスローします。 |
| addFirst | void addFirst（E e） | 容量制限に違反することなく、指定された要素eをキューの先頭に追加します。 |
| addLast | void addLast（E e） | 容量制限に違反することなく、要素eを両端キューの最後に追加します。 |
| 含まれています | boolean contains（Object o） | dequeに指定された要素oが含まれているかどうかを確認します。はいの場合はtrueを返します。 |
| 降順Iterator | イテレータdescendingIterator（） | このメソッドは、両端キューの逆順イテレータを返します。 |
| 素子 | E要素（） | dequeの最初の要素またはヘッドを返します。要素は削除されないことに注意してください。 |
| getLast | E getLast（） | dequeの最後の要素を削除せずに取得します。 |
| イテレータ | イテレータiterator（） | dequeの要素に対する標準のイテレータを返します。 |
| 提供 | ブールオファー（E e） | 容量制限に違反することなく、指定された要素eを（テールとして）両端キューに追加します。成功した場合はtrueを返し、失敗した場合はfalseを返します。 |
| オファーファースト | ブール値offerFirst（E e） | 容量制限に違反することなく、指定された要素eを両端キューの前に挿入します。 |
| オファーラスト | ブール値のオファー最後（E e） | 容量制限に違反することなく、指定された要素eを両端キューの最後に挿入します。 |
| ピーク | Eピーク（） | dequeの先頭（最初の要素）を返します。キューが空の場合はnullを返します。 **頭を削除しません |
| peekFirst | E peekFirst（） | dequeの最初の要素を削除せずに返します。 dequeが空の場合、nullを返します。 |
| peekLast | E peekLast（） | dequeの最後の要素を削除せずに取得します。 dequeが空の場合、nullを返します。 |
| 投票 | E投票（） | dequeのヘッドを削除して返します。 dequeが空の場合、nullを返します。 |
| pollFirst | E pollFirst（） | dequeの最初の要素を返し、削除します。 dequeが空の場合、nullを返します。 |
| pollLast | E pollLast（） | dequeの最後の要素を返し、削除します。 dequeが空の場合、nullを返します。 |
| ポップ | E pop（） | dequeを使用して表されるスタックから要素をポップします。 |
| 押す | ボイドプッシュ（E e） | 容量制限に違反することなく、指定された要素eをdequeを使用して表されるスタックにプッシュします。成功した場合はtrueを返し、両端キューに使用可能なスペースがない場合はIllegalStateExceptionを返します。 |
| 削除する | E remove（） | dequeのヘッドを取り外して戻します。 |
| 削除する | boolean remove（Object o） | 指定された要素oの最初の出現を両端キューから削除します。 |
| removeFirst | E removeFirst（） | dequeの最初の要素を削除して返します。 |
| removeFirstOccurrence | boolean removeFirstOccurrence（Object o） | 指定された要素oの最初の出現を両端キューから削除します。 |
| removeLast | E removeLast（） | dequeの最後の要素を取得して削除します。 |
| removeLastOccurrence | ブール値removeLastOccurrence（Object o） | 指定された要素oの最後の出現を両端キューから削除します。 |
| サイズ | int size（） | deque内の要素のサイズまたは数を返します。 |
そしてJavaでの実装
次に、Javaプログラムを実装して、上記で説明した主要な両端キューメソッドのいくつかを示します。
このプログラムでは、String型の両端キューを使用し、add、addFirst、addLast、push、offer、offerFirstなどのさまざまなメソッドを使用してこの両端キューに要素を追加します。次に両端キューを表示します。次に、両端キューの標準イテレータと逆イテレータを定義し、両端キューをトラバースして要素を出力します。
また、contains、pop、push、peek、poll、removeなどの他の方法も使用します。
import java.util.*; public class Main { public static void main(String() args) { //Declare Deque object Deque deque = new LinkedList(); // add elements to the queue using various methods deque.add('One'); //add () deque.addFirst('Two'); //addFirst () deque.addLast('Three'); //addLast () deque.push('Four'); //push () deque.offer('Five'); //offer () deque.offerFirst('Six'); //offerFirst () deque.offerLast('Seven'); //offerLast () System.out.println('Initial Deque:'); System.out.print(deque + ' '); // Iterate using standard iterator System.out.println('
Deque contents using Standard Iterator:'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Iterate using Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Deque contents using Reverse Iterator:'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek () method System.out.println('
Deque Peek:' + deque.peek()); System.out.println('
Deque,After peek:' + deque); // Pop () method System.out.println('
Deque Pop:' + deque.pop()); System.out.println('
Deque,After pop:' + deque); // contains () method System.out.println('
Deque Contains Three: ' + deque.contains('Three')); deque.removeFirst(); //removeFirst () deque.removeLast(); //removeLast () System.out.println('
Deque, after removing ' + 'first and last elements: ' + deque); } }出力：
よくある質問
Q＃1）DequeはスレッドセーフなJavaですか？
回答： ArrayDequeはスレッドセーフではありません。ただし、java.util.concurrentクラスのBlockingDequeインターフェースはdequeを表します。この両端キューはスレッドセーフです。
Q＃2） Dequeがスタックよりも速いのはなぜですか？
回答： dequeインターフェイスを実装するArrayDequeインターフェイスは、前または次のノードを追跡する必要がないため、メモリ効率が高くなります。また、サイズ変更可能な実装です。したがって、dequeはスタックよりも高速です。
Q＃3） Dequeはスタックですか？
回答： dequeは両端キューです。 LIFOの動作を許可するため、スタックではありませんが、スタックとして実装できます。
Q＃4） Dequeはどこで使用されますか？
回答： dequeは主に、元に戻す機能や履歴などの機能を実装するために使用されます。
Q＃5）Dequeは循環していますか？
回答： はい、Dequeは循環しています。
結論
これで、JavaのDequeインターフェースに関するチュートリアルは完了です。 dequeインターフェースは、両端から要素を挿入および削除できるコレクションであるdequeデータ構造によって実装されます。
ArrayDequeとLinkedListの2つのクラスは、dequeインターフェイスを実装します。これらのクラスを使用して、dequeインターフェースの機能を実装できます。
=> 独占的なJavaトレーニングチュートリアルシリーズについては、こちらをご覧ください。