Deque [ AIZU ONLINE JUDGE ITP2_1_B ]

judge.u-aizu.ac.jp

LinkedList で解こうとしたら思い切り TLE を喰らいました。他の方の解答を見ると全員が自作のDequeクラスを作って解いているので、つまりはそういうことなんだと思います。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		Deque dq = new Deque();
		
		for (int i=0; i<n; i++) {
			int mode = sc.nextInt();
			if (mode == 0) {
				if (sc.nextInt() == 0) {
					dq.addFirst(sc.nextInt());
				}
				else {
					dq.addLast(sc.nextInt());
				}
			}
			else if (mode == 1) {
				System.out.println(dq.ar[dq.head+sc.nextInt()]);
			}
			else if (mode == 2) {
				if (sc.nextInt() == 0) {
					dq.removeFirst();
				}
				else {
					dq.removeLast();
				}
			}
		}
		
	}
}



class Deque {
	int ar[];
	int head = 500000, tail = 499999;
	Deque() {
		ar = new int[1000000];
	}
	
	void addFirst(int n) {head--; ar[head] = n;}
	void addLast(int n) {tail++; ar[tail] = n;}
	void removeFirst() {head++;}
	void removeLast() {tail--;}
}

このプログラムのDeque と LinkedList との最大の違いは、サイズが固定であるということです。メリットとして、内部に配列を使っているため、LinkedList と違ってランダムアクセス処理が速いことがあげられます。デメリットとしては、最初に要素数ぶんの配列を確保する必要があるので、メモリの消費量が大きいこと（？）でしょうか。メモリについてあまりわかっていないので、間違ったことを言っていたら申し訳ないです。

この問題を自作クラス以外のやり方で解こうとして、「先頭・末尾への挿入・削除処理が速く、かつランダムアクセス処理も速い」データ構造を探してみましたが、どうやら存在しないみたいです。だいたいの問題では LinkedList を使って事足りると思いますが、今回のように凶悪な制約の問題に出会ったときのために、自作の Deque の書き方は覚えておきたいです。