【Java】スタック・キューを実現するDeque<E>インターフェース

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メソッドを用いてリストの末端の要素を取り出しても、その要素はリストから削除されない。