【Javaで】AOJ 「4.5 標準ライブラリのデータ構造」

操作	Stackと同名のメソッド	対応するメソッド
スタックに要素を追加	push(e)	addFirst(e)
スタックから要素を削除して取り出す	pop()	removeFirst()
スタックから要素を削除せずに取り出す	peek()	peekFirst()

スタックとして使うときのために、プッシュやポップが用意されていますが、
対応する○○Firstメソッドと全く同じ操作みたいです。

また、要素が何もなかったり満杯だったという理由で、
挿入や追加の操作が失敗した場合には、
「例外をスローする」または「戻り値でnullやfalseを返す」
2つの形式のメソッドがそれぞれの操作に用意されています。

操作	例外をスロー	戻り値で特殊な値を返す
スタックに要素を追加	push(e) addFirst(e)	offerFirst(e)
スタックから要素を削除して取り出す	pop() removeFirst()	pollFirst()
スタックから要素を削除せずに取り出す	getFirst()	peek() peekFirst()

Stackと同名のメソッドでいうと、
pushとpopの操作は失敗時に例外をスローしますが、
peekの操作では、例外は発生せずにnullが返ってきます。

ただし、後述のキューの方でもjavadocの説明を引用していますが、
戻り値で特殊な値を返すメソッドは、
「失敗が例外的ではなく通常のことである場合に使用する目的で設計されている」
とのことです。

これはどういうことかと言うと、
Dequeインターフェースの実装クラスは主に可変長なので、
要素の追加では失敗することがまずないそうで、
固定長のクラスで実装して使った場合の為だけに特別に用意されているそうです。
（Dequeの実装クラス4つの中では「LinkedBlockingDeque」だけがこれに該当する。）

だから、実際に使うのは太字のメソッドになると思います。

あと、キューの両端が空かどうかをnullで判定している為、
nullの追加は厳禁らしいです。

参考リンク

d.hatena.ne.jp

todai-neet.hateblo.jp

使ってみた

スタック | アルゴリズムとデータ構造 | Aizu Online Judge

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		// Dequeはインターフェースなので、実装クラスのArrayDequeで実装
		Deque<Integer> stack = new ArrayDeque<>();
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
			int curNum = 0;
			String curStr = "";
			if (sc.hasNextInt()) {
				curNum = sc.nextInt();
				// スタックに追加
				stack.push(curNum);
			} else {
				curStr = sc.next();
				// スタックから要素を削除して取り出し
				int a = stack.pop();
				int b = stack.pop();
				switch (curStr) {
				case "+":
					stack.push(b + a);
					break;
				case "-":
					stack.push(b - a);
					break;
				case "*":
					stack.push(b * a);
					break;
				}
			}

		}
		// スタックから取り出して表示
		System.out.println(stack.pop());

	}

}

キュー

キューは専用のインターフェースが用意されています。
こちらも上記のDequeと同じように、操作失敗時の挙動が異なるメソッドが、
それぞれ2つずつあります。

前述の通り、失敗時にnullやfalseを返す形式のメソッドは、
queueインターフェースを固定長のクラスで実装した場合を想定して設計しているそうです。

固定容量(バウンド)キューが原因で発生する場合のように、offerメソッドは、失敗が例外的ではなく通常のことである場合に使用する目的で設計されています。
───javadoc 「インタフェースQueue」より引用

そのため、固定長のクラスで実装する場合は、
挿入の操作はoffer()メソッドを使うことを推奨されていました。

また、こちらも同じくnullの追加は禁止されています。
キューの先頭の要素を取得するpollメソッドで、要素が存在しないときの戻り値のnullと見分けが付かなくなってしまうからだそうです。

java.util.Queue

Queue (Java Platform SE 8)

同じく、java.util.Collectionインターフェースを継承しているので、
要素数を調べるsize()メソッドと、要素がない場合にtrueを返すisEmpty()メソッドが使えます。

操作	例外をスロー	戻り値で特殊な値を返す
キューに要素を追加	add(E e)	offer(E e)
キューの先頭の要素を削除して取り出す	remove()	poll()
キューの先頭の要素を削除せずに取り出す	element()	peek()

参考リンク

www.sejuku.net

使ってみた

キュー | アルゴリズムとデータ構造 | Aizu Online Judge

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	public static void main(String[] args) {

		// Queueはインターフェースなので、実装クラスのArrayDequeで実装
		Queue<Process> queue = new ArrayDeque<>();

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
			String[] str = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int q = Integer.parseInt(str[1]);

			for (int i = 0; i < n; i++) {
				String[] tmp = br.readLine().split(" ");
				String name = tmp[0];
				int time = Integer.parseInt(tmp[1]);
				// キューに追加
				queue.add(new Process(name, time));
			}

			int total = 0;
			// peek()メソッドは要素がなくても例外をスローせずnullを返す
			while (queue.peek() != null) {
				// キューから取り出し
				Process curPrcs = queue.remove();
				int curTime = Math.min(q, curPrcs.time);
				total += curTime;
				curPrcs.time -= curTime;
				if (curPrcs.time > 0) {
					// キューに追加
					queue.add(curPrcs);
				} else {
					System.out.println(curPrcs.name + " " + total);
				}

			}

		} catch (IOException e) {
			e.printStackTrace();
		}

	}

}

// プロセスの情報
class Process {
	String name;// プロセス名
	int time;// 処理時間

	public Process(String name, int time) {
		this.time = time;
		this.name = name;

	}

}

動的な配列

JavaにもVectorクラスは存在しますが、
Vectorクラスはかなり古いクラスなので、現在はArrayListを使います。

ただ、Vectorはスレッドセーフなのに対して、ArrayListは同期化されていません。
同期化されていない代わりに、Vectorより高速に動くそうです。

というわけですので、
スレッドセーフにしたい場合は、Vectorクラスを、
同期化が必要ない場合は、ArraysListクラスを使い分けることに……

なるかと思いきや、
Collections.synchronizedList メソッドを使用してラップすることで、
ArraysListも同期化を行えます。

結局の所、動的な配列はArraysListを使うということになるようです。

java.util.ArrayList

ArrayList (Java Platform SE 7)

操作	メソッド
リストに要素を追加	add(E e)
リストの特定の位置に要素を追加	add(int index, E element)
リストから○番目の要素を取り出す	get(int index)
リストの○番目の要素を削除	remove(int index)
リストのすべての要素を削除	removeAll(Collection c)

参考リンク

[Java] ArrayListとVectorの違いは何ですか？ | CODE Q&A [日本語]
Vector (Java Platform SE 8)
www.sejuku.net

操作	メソッド
リストに要素を追加	add(E e)
リストの先頭に要素を追加	addFirst(E e)
リストの最後に要素を追加	addLast(E e)
リストの特定の位置に要素を追加	add(int index, E element)
リストから○番目の要素を取り出す	get(int index)
リストから先頭の要素を削除せずに取り出す	getFirst()
リストから末尾の要素を削除せずに取り出す	getLast()
リストから先頭の要素を削除して取り出す	removeFirst()
リストから末尾の要素を削除して取り出す	removeLast()
リストの○番目の要素を削除	remove(int index)
リストのすべての要素を削除	clear()

LinkedList と ArrayList

LinkedListはArrayListと同じく、Listインターフェースの実装クラスの1つですが、

ArrayListのjavadocを見ると、addを除くほとんどの処理は、
ArrayListの方がLinkedListよりも速いようなことが書いてあります。

size、isEmpty、get、set、iterator、および listIterator の処理は、一定の時間で実行されます。add の処理も、一定の償却時間で実行されます。つまり、n 個の要素を追加するには O(n) 時間が必要です。ほとんどの場合、ほかのすべての処理も比例的な時間で実行されます。定数の係数は、LinkedList の実装の場合より小さくなります。
───javadoc 「クラス ArrayList」より引用

LinkedListは双方向連結リストなので、
「4.4 連結リスト」で学んだ通り、ノードと呼ばれる各要素は、
前後のノードと連結することで順番に辿れるようになっています。

それに対し、ArrayListは動的な"配列"です。
各要素にはそれぞれ番号が割り振られています。

配列であれば、例えば1万番目の要素が欲しいと思ったときに、
きちんと1万番目と指定すれば、ピンポイントで要素を取り出すことができますが、
LinkedListの場合、番号は割り振られていませんので、
先頭（または末尾）から1つずつ順番に、1万番目まで辿らなくてはなりません。

そのため、LinkedListでは、
get(i) のような特定の位置の要素を参照する操作は、不向きと言えます。

一方で、リスト内の途中の要素を操作する場合の処理に関しては、
LinkedListに軍配が上がります。

それは、ArrayListではそれぞれの要素に番号が割り振られてるが為に、
リストの途中に要素を追加されると、
それ移行の要素の番号を全てずらしてやる必要があるからです。

もし、1万件の要素のうち"先頭の要素だけ"を削除した場合でも、
後続の9999個の要素にも変更を加えなければなりません。

双方向リストであれば、リストの途中に要素を加えても、
修正を加えるのは、その前後2つのノードだけで済みます。

参考リンク

LinkedList と ArrayList の使い分け方
 軽い気持ちでLinkedListを使ったら休出する羽目になった話
 JavaのListについて
eng-entrance.com

使ってみた

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;

public class Main {
	public static void main(String[] args) {

		// LinkedList型としてインスタンス化
		LinkedList<Integer> list = new LinkedList<>();

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
			int n = Integer.parseInt(br.readLine());
			for (int i = 0; i < n; i++) {
				String[] cmd = br.readLine().split(" ");
				switch (cmd[0]) {
				case "insert":
					// リストの先頭に追加
					list.addFirst(Integer.parseInt(cmd[1]));
					break;

				case "delete":
					// parseIntの戻り値はint型である為、
					// そのまま渡すとremove(int index)が呼び出されてしまう。
					// 明示的にInteger型に変換することで、
					// remove(Object o)メソッドを呼び出す。
					list.remove((Integer) Integer.parseInt(cmd[1]));
					break;

				case "deleteFirst":
					// 先頭の要素を削除
					list.removeFirst();
					break;

				case "deleteLast":
					// 末尾の要素を削除
					list.removeLast();
					break;
				}
			}

			StringBuilder sb = new StringBuilder();

			// Iteratorを使って先頭の要素から順番に辿っていく
			for (Iterator<Integer> it = list.listIterator(); it.hasNext();) {
				sb.append(it.next());
				if (it.hasNext()) {
					sb.append(" ");
				}
			}
			System.out.println(sb);

		} catch (Exception e) {
			e.printStackTrace();
		}

	}

}

おわりに

恥ずかしながらArrayList以外は全く知らなかったので、
かなり勉強になりました。

ただ、ここらへんを勉強してると、
コレクションやジェネリクスをよく分かっていないのが浮き彫りになってしまったので、
そちらもちゃんと勉強する必要がありそうです。

そして、次章からはついに探索に入ります！

ここまではソートの仕方と構造体の仕組みだったので、
いよいよテクニックの部分に触れられると思うと楽しみです。