Javaのキューとスタック：sortメソッドによる並び替え

キューとスタック

コレクションに格納された要素の取り出し方としてデータを一時的に格納し、それを順番に取り出す方法として、Queue(キュー) と Stack(スタック) と呼ばれる２とおりの方法があり、データの処理の最も基本的な方法として広く用いられる。

・キュー：複数のオブジェクトを管理する方法の１つ。先に追加されたオブジェクトから順番に取り出すことができる。
・スタック：キューと対になる、複数のオブジェクトを管理する方法の１つ。後に追加されたオブジェクトから順番に取り出すことができる。

Queue(キュー)

キューは「先入れ先出し(First In FirstOut：FIFO) 」と呼ばれるオブジェクトの管理方法で、追加した順番にオブジェクトの取り出しを行う。
パッケージjava.utilのインタフェースQueueになる。

画像のように、追加したデータを古いものから順番に取り出して使用したい場合に使用する。

LinkedListクラスやLinkedTransferQueue、AbstractQueueクラスなどはQueueインタフェースが自動で実装されており、Queueインタフェースを実装しているクラスに対しては、次のようなメソッドを呼び出すことができる。

offerメソッド
要素を末尾に追加する。
peekメソッド
先頭の要素の参照を返し、キューが空のときにはnullが戻り値になる。
pollメソッド
先頭から要素を取り出し、取り出した要素の参照が戻り値になる。キューが空のときにはnullが戻り値になる。

例文

import java.util.*;

public class QueueExample{
  public static void main(String[] args) {
    Queue<String> queue = new LinkedList<String>();

    queue.offer("(1)");
    System.out.println("キューの状態:" + queue);
    queue.offer("(2)");
    System.out.println("キューの状態:" + queue);
    queue.offer("(3)");
    System.out.println("キューの状態:" + queue);
    queue.offer("(4)");
    System.out.println("キューの状態:" + queue);

    while (!queue.isEmpty()) {
      System.out.println("要素の取り出し:" + queue.poll());
      System.out.println("キューの状態:" + queue);
    }
  }
}

出力結果

キューの状態:[(1)]
キューの状態:[(1), (2)]
キューの状態:[(1), (2), (3)]
キューの状態:[(1), (2), (3), (4)]
要素の取り出し:(1)
キューの状態:[(2), (3), (4)]
要素の取り出し:(2)
キューの状態:[(3), (4)]
要素の取り出し:(3)
キューの状態:[(4)]
要素の取り出し:(4)
キューの状態:[]

５行目で、生成したLinkedListオブジェクトをQueue型の変数に代入している。このようにするのは、LinkedListクラスのメソッドのうち、Queueインタフェースに定義されているキューのためのメソッドしか呼び出せなくするため。

実行結果からは、offerメソッドによって追加された要素が、キューの末尾に格納されていることを確認できる。
pollメソッドではキューの先頭から順番に要素が取り除かれている。

isEmptyメソッドを利用することで、文字列が空であるかどうかを判定できる。１６行目にあるwhile (!queue.isEmpty())の条件式がtrueである間はキューに要素が空になるまで、処理を繰り返すことになる。

Stack(スタック)

スタックは「後入れ先出し (Last In First Out :LIFO)」と呼ばれるオブジェクトの管理方法で、最後にリストに追加したオブジェクトを最初に取り出していく。キューと対になるオブジェクトの管理方法。

キューと異なり、スタックのためのメソッドやインタフェースはないのでLinkedListクラスなどの一部のクラスに定義されているaddLastメソッド(末尾に要素を追加する)やgetLastメソッド(末尾の要素の参照を取得する)、removeLastメソッド(末尾の要素を削除する)を使って、スタックの機能を実現できる。

例文

import java.util.*;

public class StackExample{
  public static void main(String[] args) {
    LinkedList<String> stack = new LinkedList<String>();

    stack.addLast("(1)");
    System.out.println("スタックの状態:" + stack);
    stack.addLast("(2)");
    System.out.println("スタックの状態:" + stack);
    stack.addLast("(3)");
    System.out.println("スタックの状態:" + stack);
    stack.addLast("(4)");
    System.out.println("スタックの状態:" + stack);
   
    while (!stack.isEmpty()) {
      System.out.println("要素の取り出し:" + stack.removeLast());
      System.out.println("スタックの状態:" + stack);
    }
  }
}

　７、９、１１、１３行目のaddLastメソッドにより、要素がスタックの末尾に追加されている。
１６ー１９行目のwhile文では１７行目のremoveLastメソッドにより、後に格納されたものから順番に要素が取り除かれて、キューの例と同様に、スタックに要素がある場合は、isEmptyメソッドがfalseを返すので、while (!stack.isEmpty())の条件式がtrue になり、要素が空になるまで処理を繰り返すことになる。
　

sortメソッドによる並び替え

コレクションによって複数のオブジェクトを管理していると、その中の要素を値が小さい順、または値が大きい順に並べ替えたいことがあり、この並べ替えの操作はコレクションを扱うプログラムの多くで必要とされる。
そのため並べ替えを行うクラスメソッドsort がArraysクラス、Collectionsクラスで宣言されている。
このsortメソッドにListインタフェースを実装したクラス(ArrayListやLinkedListなど)のインスタンスを渡すと、その中に格納されているオブジェクトを順番に並べ替えが出来る。

Collections.sort(リスト名);

上記のように記述することで昇順に並べ替えることができ、逆に降順で並び替えるにはCollectionsクラスのreverseOrderメソッドをsortメソッドの第2引数に指定する。

Collections.sort(リスト名,  Collections.reverseOrder());

複数のオブジェクトの並べ替えを考えたときに、 「２つのインスタンスがあったときに、どちらを前にして、どちらを後ろにするか」 が明確に決まっていないと、オブジェクトを順番に並べることはできない。

そのためCollectionsクラスのsortメソッドで並べ替えを行うには、コレクションに格納されているオブジェクトが、その前後関係を明確にするためのインタフェースComparableを実装している必要がある。
Comparableインタフェースを実装するには、インスタンスが２つあったときに、その大小関係を整数で戻すcompareToメソッドを定義する必要がある。

例文

import java.util.*;

class Point implements Comparable<Point>{
  int x;
  int y;

  Point(int x, int y){
    this.x = x;
    this.y = y;
  }

  public int compareTo(Point p){
    return (this.x + this.y) - (p.x + p.y);
  }
}

public class SortExample{
  public static void main(String[] args) {
    ArrayList<Point> pointList = new ArrayList<Point>();
    pointList.add(new Point(0, 8));
    pointList.add(new Point(1, 6));
    pointList.add(new Point(2, 9));
    pointList.add(new Point(3, 3));

    Collections.sort(pointList);

    for(Point p : pointList){
      System.out.println("("+ p.x +","+ p.y +") ->" + (p.x + p.y));
    }
  }
}

出力結果

(3,3) ->6
(1,6) ->7
(0,8) ->8
(2,9) ->11

Pointクラス
「implements Comparable」でPointクラスにComparable インタフェースを実装し、型パラメータには比較する為のオブジェクトのクラス名にPointクラスを指定。

compareToメソッドには、型パラメータとして指定したPointクラスのインスタンスが引数に渡され、戻り値は、「自分自身と引数で渡されたオブジェクトの差」になる。このとき、自分自身の値のほうが大きいときに正の数をint型で返すようにしている。

SortExampleクラス
全てのデータ型がPoint型になったオブジェクトpointListを宣言し、addメソッド「pointList.add(new Point(0, 8));」でPointクラスにそれぞれ値を追加し、PointオブジェクトをArrayListに追加している。

「Collections.sort(pointList)」Collectionsクラスのsortメソッドの引数にオブジェクトpointListを渡して中身の順番が自動的に並べ替えられている。
拡張for分では並べ替えた結果をxとyを足した値も合わせて繰り返し出力している。

参考記事