Deque<E>インターフェース
とは
Queue
インターフェースを拡張したもので、「Double Ended Queue」両端キューと呼ばれる。
スタックやキューを実現するために用いられる。
特徴としては以下のとおり
- 両端から要素を挿入・削除することができるデータ構造を実現する。
- null要素を格納することが出来ない。
- Indexによる要素へのアクセスをサポートしていない。
つまり、先頭に要素を挿入したり、最後尾に要素を挿入することができる。
代表的な実装クラスは以下のとおり
ArrayDeque<E>クラス
LinkedList<E>クラス
まとめ
先に後述するArrayDeque<E>クラス
の各メソッドの役割を以下にまとめる。
操作 | メソッド |
---|---|
リストの先頭に要素を挿入する | addFirst()メソッド、push()メソッド |
リストの末端に要素を挿入する | addLast()メソッド、add()メソッド |
リストの先頭の要素を取得する (取得時に削除する) |
pop()メソッド、remove()メソッド、removeFirst()メソッド |
リストの末端の要素を取得する (取得時に削除する) |
removeLast()メソッド |
リストの先頭の要素を取得する (取得時に削除しない) |
getFirst()メソッド、element()メソッド |
リストの末端の要素を取得する (取得時に削除しない) |
getLast()メソッド |
ArrayDeque<E>クラス
の各メソッド
addメソッド
まずはArrayListと同じようにaddメソッド
で要素を挿入して出力してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println(deque); } 【実行結果】 [A, B, C]
ArrayListと同じようにA、B、Cの順番で出力される。
addFirstメソッド
次は、リストの先端に挿入するaddFirstメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); deque.addFirst("D");//addFirstメソッドを実行 deque.add("E"); System.out.println(deque); } 【実行結果】 [D, A, B, C, E]
D
とE
の出力位置に注目。
addFirstメソッド
で追加したD
は一番先頭へ挿入され、addメソッド
で追加したE
は後ろへ挿入されることが分かった。
じゃあ、addFirstメソッド
を2回使ったらどうなるのか?を次のコードで試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); deque.addFirst("D");//addFirstメソッドを実行 deque.add("E"); deque.add("F"); deque.addFirst("G");//addFirstメソッドを実行 System.out.println(deque); } 【実行結果】 [G, D, A, B, C, E, F]
2回目のaddFirstメソッド
で追加したG
はD
よりも前へ挿入されることが分かった。
つまり、addFirstメソッド
で挿入した要素は、後続でaddFirstメソッド
により別の要素を挿入しない限りずっと先頭に位置し続ける。
挿入順としては以下になる。
A //Aが挿入される。
A、B //最後尾にBが挿入される。
A、B、C //最後尾にCが挿入される。
D、A、B、C //先頭にDが挿入される。
D、A、B、C、E //最後尾にEが挿入される。
D、A、B、C、E、F //最後尾にFが挿入される。
G、D、A、B、C、E、F //先頭にGが挿入される。
pushメソッド
次は、pushメソッド
を試してみる。
pushメソッド
もaddFirstメソッド
と同様に、リストの先端に挿入するメソッドである。
先述のaddFirstメソッド
の例2と同じ要素で書いてみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); deque.push("D");//pushメソッドを実行 deque.add("E"); deque.add("F"); deque.push("G");//pushメソッドを実行 System.out.println(deque); } 【実行結果】 [G, D, A, B, C, E, F]
addFirstメソッド
で実行したときと同じ結果になった。
addLastメソッド
次は、リストの末端に挿入するaddLastメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); deque.addLast("D");//addLastメソッドを実行 deque.add("E"); System.out.println(deque); } 【実行結果】 [A, B, C, D, E]
addLastメソッド
でD
を追加した後に、addメソッド
でE
を追加すると、E
はD
の後ろに挿入される。
つまりaddFirstメソッド
のときと違ってaddLastメソッド
はずっと末端に位置し続けたりはしないので注意。
すなわち、addLastメソッド
はaddメソッド
と同等の動きをする。
次がaddLastメソッド
を2回使ってみたコード。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); deque.addLast("D");//addLastメソッドを実行 deque.add("E"); deque.add("F"); deque.addLast("G");//addLastメソッドを実行 System.out.println(deque); } 【実行結果】 [A, B, C, D, E, F, G]
popメソッド
次は、リストの先頭の要素を取り出すpopメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("pop実行前: " + deque); String str = deque.pop();//popメソッドを実行 System.out.println("pop実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行結果】 pop実行前: [A, B, C] pop実行後: [B, C] 取り出したstrの中身: A
popメソッド
実行前後の出力結果を見てみると、popメソッド
実行時にdequeの先頭の要素が削除されていることが分かる。
つまり、popメソッド
を用いてリストの先頭の要素を取り出すと、その要素はリストから削除される。
removeメソッド
次は、removeメソッド
を試してみる。
removeメソッド
もpopメソッド
と同様に、リストの先頭の要素を取り出すメソッドである。
以下のとおり、popの部分をremoveに書き換えて実行してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("remove実行前: " + deque); String str = deque.remove();//removeメソッドを実行。 System.out.println("remove実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行結果】 remove実行前: [A, B, C] remove実行後: [B, C] 取り出したstrの中身: A
popメソッド
と同様の結果になった。
つまり、リストの先頭の要素を取り出したタイミングでリストから削除された。
removeFirstメソッド
次は、removeFirstメソッド
を試してみる。
removeFirstメソッド
もpopメソッド
やremoveメソッド
と同様に、リストの先頭の要素を取り出すメソッドである。
以下のとおり、popの部分をremoveFirstに書き換えて実行してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("removeFirst実行前: " + deque); String str = deque.removeFirst();//removeFirstメソッドを実行 System.out.println("removeFirst実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行結果】 removeFirst実行前: [A, B, C] removeFirst実行後: [B, C] 取り出したstrの中身: A
popメソッド
やremoveメソッド
と同様の結果になった。
つまり、リストの先頭の要素を取り出したタイミングでリストから削除された。
removeLastメソッド
次は、リストの末端の要素を取り出すremoveLastメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("removeLast実行前: " + deque); String str = deque.removeLast();//removeLastメソッドを実行 System.out.println("removeLast実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行前】 removeLast実行前: [A, B, C] removeLast実行後: [A, B] 取り出したstrの中身: C
リストの末端の要素であるC
が取得と同時にリストから削除されていることが分かる。
getFirstメソッド
次は、リストの先頭の要素を取り出すgetFirstメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("getFirst実行前: " + deque); String str = deque.getFirst();//getFirstメソッドを実行 System.out.println("getFirst実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行結果】 getFirst実行前: [A, B, C] getFirst実行後: [A, B, C] 取り出したstrの中身: A
getFirstメソッド
実行前後の出力結果を見てみると、getFirstメソッド
実行時にdequeの先頭の要素が削除されていないことが分かる。
つまり、getFirstメソッド
を用いてリストの先頭の要素を取り出しても、その要素はリストから削除されない。
elementメソッド
次は、リストの先頭の要素を取り出すelementメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("element実行前: " + deque); String str = deque.element();//elementメソッドを実行 System.out.println("element実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行結果】 element実行前: [A, B, C] element実行後: [A, B, C] 取り出したstrの中身: A
elementメソッド
実行前後の出力結果を見てみると、elementメソッド
実行時にdequeの先頭の要素が削除されていないことが分かる。
つまり、elementメソッド
を用いてリストの先頭の要素を取り出しても、その要素はリストから削除されない。
getLastメソッド
次は、リストの末端の要素を取り出すgetLastメソッド
を試してみる。
public static void main(String args[]){ Deque<String> deque = new ArrayDeque<String>(); deque.add("A"); deque.add("B"); deque.add("C"); System.out.println("getLast実行前: " + deque); String str = deque.getLast();//getLastメソッドを実行 System.out.println("getLast実行後: " + deque); System.out.println("取り出したstrの中身: " + str); } 【実行結果】 getLast実行前: [A, B, C] getLast実行後: [A, B, C] 取り出したstrの中身: C
getLastメソッド
実行前後の出力結果を見てみると、getLastメソッド
実行時にdequeの末端の要素が削除されていないことが分かる。
つまり、getLastメソッド
を用いてリストの末端の要素を取り出しても、その要素はリストから削除されない。