頭脳一式

人の記憶なんて曖昧なもの。すべての情報を頭に記憶するなんてナンセンス。困ったらここに来ればいいじゃん?というスタンスで最強のナレッジベースを目指すブログ

【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]

DEの出力位置に注目。
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メソッドで追加したGDよりも前へ挿入されることが分かりました。
つまり、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を追加すると、EDの後ろに挿入されます。
つまり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メソッドを用いてリストの末端の要素を取り出しても、その要素はリストから削除されないのです。