ITP2_2 Basic Data Structures

A : Stack

問題（外部リンク）

Stack | Aizu Online Judge

実装の概要

Java.util.Stack内に必要なメソッドは既に容易されているのでこれを利用することでACできます。要素を取り出さないときはpeek()です。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);

		@SuppressWarnings("unchecked")
		Stack<Integer>[] stackArray = new Stack[n];
		for(int i = 0; i < n; i++){
			stackArray[i] = new Stack<Integer>();
		}

		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");

			//push
			if(tmpArray[0].equals("0")){
				int t = Integer.parseInt(tmpArray[1]);
				int x = Integer.parseInt(tmpArray[2]);

				stackArray[t].push(x);
			}
			//top
			else if(tmpArray[0].equals("1")){
				int t = Integer.parseInt(tmpArray[1]);

				if(!stackArray[t].isEmpty()){
					System.out.println(stackArray[t].peek());
				}
			}
			//pop
			else {
				int t = Integer.parseInt(tmpArray[1]);

				if(!stackArray[t].isEmpty()){
					stackArray[t].pop();
				}
			}
		}

	}
}

B : Queue

問題（外部リンク）

Queue | Aizu Online Judge

実装の概要

Java.util.Queueはインターフェースなのでこれをそのままインスタンス化することはできませんが、ArrayListがQueueを実装しておりenqueueやdequeueなどを行うことができます。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);

		@SuppressWarnings("unchecked")
		ArrayList<Integer>[] queue = new ArrayList[n];
		for(int i = 0; i < n; i++){
			queue[i] = new ArrayList<Integer>();
		}

		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");

			//enqueue
			if(tmpArray[0].equals("0")){
				int t = Integer.parseInt(tmpArray[1]);
				int x = Integer.parseInt(tmpArray[2]);

				queue[t].add(x);
			}
			//front
			else if(tmpArray[0].equals("1")){
				int t = Integer.parseInt(tmpArray[1]);

				if(!queue[t].isEmpty()){
					System.out.println(queue[t].get(0));
				}
			}
			//dequeue
			else {
				int t = Integer.parseInt(tmpArray[1]);

				if(!queue[t].isEmpty()){
					queue[t].remove(0);
				}
			}
		}

	}
}

C : Priority Queue

問題（外部リンク）

Priority Queue | Aizu Online Judge

実装の概要

Java.util.PriorityQueueを利用することで要求されている仕様を満たすことができます。
Javaの優先度付きキューはデフォルトの場合昇順になっているため、降順にしたい場合はコンストラクタにComparatorを渡してそのように設定します。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);

		@SuppressWarnings("unchecked")
		PriorityQueue<Integer>[] queue = new PriorityQueue[n];
		for(int i = 0; i < n; i++){
			//降順に設定
			queue[i] = new PriorityQueue<Integer>(new Comparator<Integer	>() {
				@Override
				public int compare(Integer a, Integer b) {
					return b - a;
				}
			});
		}

		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");

			//insert
			if(tmpArray[0].equals("0")){
				int t = Integer.parseInt(tmpArray[1]);
				int x = Integer.parseInt(tmpArray[2]);

				queue[t].add(x);
			}
			//getMax
			else if(tmpArray[0].equals("1")){
				int t = Integer.parseInt(tmpArray[1]);

				if(!queue[t].isEmpty()){
					System.out.println(queue[t].peek());
				}
			}
			//deleteMax
			else {
				int t = Integer.parseInt(tmpArray[1]);

				if(!queue[t].isEmpty()){
					queue[t].poll();
				}
			}
		}

	}
}

D : Splice

問題（外部リンク）

Splice | Aizu Online Judge

実装の概要

JavaのリストにはaddAll()メソッドが存在しますが、内部的に1つずつ要素を追加しているのかあまり高速では動作しません。Collections.addAll()も同様です。
そのため、spliceを高速で行うためには自分でリストを実装し手動でリンクをつなぎ替える必要があります。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);

		MyList[] lists = new MyList[n];
		for(int i = 0; i < n; i++){
			lists[i] = new MyList();
		}

		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");

			//insert
			if(tmpArray[0].equals("0")){
				int t = Integer.parseInt(tmpArray[1]);
				int x = Integer.parseInt(tmpArray[2]);

				lists[t].add(x);
			}
			//dump
			else if(tmpArray[0].equals("1")){
				int t = Integer.parseInt(tmpArray[1]);

				lists[t].dump();
			}
			//splice
			else {

				int s = Integer.parseInt(tmpArray[1]);
				int t = Integer.parseInt(tmpArray[2]);

				lists[t].splice(lists[s]);
				
			}
		}

	}
	
}

class MyList {
	MyNode head;
	MyNode tail;
	
	MyList (){
		head = new MyNode(0, null, null);
		tail = new MyNode(0, head, null);
		head.next = tail;
	}
	
	void add(int data){
		MyNode node = new MyNode(data, null, tail);
		
		node.prev = tail.prev;
		tail.prev = node;
		node.prev.next = node;
	}
	
	void dump(){
		MyNode current = head.next;
		
		StringBuffer sb = new StringBuffer();
		while(current.next != null){
			sb.append(current.data);
			if(current.next != tail){
				sb.append(" ");
			}
			
			current = current.next;
		}
		
		System.out.println(sb);
	}
	
	void splice(MyList list){
		MyNode first = list.head.next;
		MyNode last = list.tail.prev;
		
		first.prev = this.tail.prev;
		this.tail.prev.next = first;
		last.next = this.tail;
		this.tail.prev = last;
		
		list.head.next = list.tail;
		list.tail.prev = list.head;
	}
}

class MyNode {
	MyNode prev;
	MyNode next;
	int data;
	
	MyNode (int data, MyNode prev, MyNode next){
		this.data = data;
		this.prev = prev;
		this.next = next;
	}
}