「みんなのデータ構造」で学ぶデータ構造 〜 ArrayStack・ArrayQueue・ArrayDeque

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque 👈 この記事
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

弁護士ドットコムでは、エンジニア有志で本書の輪読会をしています。この本の内容をマスターして、競技プログラミングに挑戦するぞ！

この記事は、「ArrayStack、ArrayQueue、ArrayDeque」のまとめです。

関連記事

• SLList・DLList まとめ
• ChainedHashTable まとめ
• BinaryTree・BinarySearchTree まとめ

ArrayStack・ArrayQueue・ArrayDequeの感想・考察

• Stackはレジスタで使われるデータ構造。皿の積み重ねによく例えられる
• Queueはジョブの処理で使うデータ構造。店の行列によく例えられる
• 配列のresizeは隠れたコスト
• 要素をたくさん持つ配列の途中に要素の追加、削除をすると、計算量はO(1)ではなくO(1 + min{i, n-i})になるので、その際は別のデータ構造を使う方がベター（例えば後述のLinked-List）
• Rustで固定長の配列と可変長の配列が区別されていたのは、配列操作の計算量も関係あるんだな（動的言語ばかりやってると、固定長配列を意識できない）
• modである長さの中でindexを循環させるという発想は使えそう
• Dequeは幅優先探索、深さ優先探索で使えるので、基礎を知れてよかった。競技プログラミングではDequeを使えればStackやQueueとして扱える

コンピュータ・サイエンスの基礎を学びたい方や、競技プログラミングにチャレンジする方に「みんなのデータ構造」(Amazonリンク)はおすすめです。

Stack、Queueと言えば、会社の先輩が「仕事で差し込みの案件をStackとして積んでいくと、最初のタスク完了までに時間がかかる。すると、先に進んでるかわからなくなってしまう。そんな時は差し込みタスクをQueueとしてFIFOで処理すると前進している実感が湧く」と話していたのを思い出します。

配列を使ったリスト

ArrayStack: 配列を使った高速なスタック操作

ArrayStackは backing array を使ったListインターフェースを実装。

array<T> a;
int n;
int size() {
	return n;
}

get(i)/set(i, x) - O(1)

T get(int i) {
	return a[i];
}

T set(int i, T x) {
	T y = a[i];
	a[i] = x;
	return y;
}

add(i, x)/ remove(i) - O(1 + n - i)

addは、インデックスiの位置にxを追加する。

void add(int i, T x) {
	if (n + 1 > a.length) resize();
	for (int j = n; j > i; j--)
		a[j] = a[j - 1];

	a[i] = x;
	n++;
}

removeは、インデックスiの要素を削除する。

T remove(int i) {
	T x = a[i];
	for (int j = i; j < n - 1; j++)
		a[j] = a[j + 1];
	n--;
	if (a.length >= 3 * n) resize();
	return x;
}

空のArrayStackに対して、任意のm個のadd(i, x)およびremove(i)からなる操作の列を実行する。この時、resize()にかかる時間の合計はO(m)である。

void resize() {
	array<T> b(max(2 * n, 1));
	for (int i = 0; i < n; i++)
		b[i] = a[i];
	a = b;
}

resize()の実行にはO(n)の時間がかかる。

ArrayQueue: 配列を使ったキュー

ArrayQueueは、FIFO（先入れ先出し）キューを実装するデータ構造。

ArrayQueueは、FIFOのQueueインターフェースの実装である。resize()のコストを無視すると、ArrayQueueはadd(x)、remove()の実行時間はO(1)である。さらに、空のArrayQueueに対して長さmのadd(i, x)およびremove(i)からなる操作の列を実行するとき、resize()にかかる時間の合計はO(m)である。

jはqueueの先頭の位置。

array<T> a;
int j;
int n;

add(i, x)/ remove(i) - O(1)

FIFOなので、addは末尾に要素を追加する。

bool add(T x) {
	if (n+1 >= a.length) resize();
	a[(j+n) % a.length] = x;
	n++;
	return true;
}

removeは先頭の要素を削除する。

T remove() {
	T x = a[j]
	j = (j+1) % a.length;
	n--;
	if (a.length >= 3 * n) resize();
	return x;
}

resize()はArrayStackの実装に似ている。ただ、queueの先頭のインデックスjは0ではない点が異なる。

void resize() {
	array<T> b(max(2 * n, 1));
	for (int k = 0; k < n; k++)
		b[k] = a[(j+k) % a.length];
	a = b;
	j = 0;
}

ArrayDeque: 配列を使った高速な双方向キュー

Dequeは両端に対して追加と削除が効率的に実行できるデータ構造である。

ArrayDequeはListインターフェースを実装する。

• get(i)およびset(i, x)の実行時間はO(1)である
• add(i, x)およびremove(i)の実行時間はO(1 + min{i, n-i})である

array<T> a;
int j;
int n;

get(i)/set(i, x) - O(1)

get(i)、set(i, x)はシンプル。

T get(int i) {
	return a[(j+i) % a.length];
}

T set(int i, T x) {
	int k = (j+i) % a.length;
	T y = a[k];
	a[k] = x;
	return y;
}

add(i, x)/ remove(i) - O(1 + min{i, n - i})

add、removeは、i個の要素を左に、またはn-i個の要素を右にずらす。

resize()を無視すれば、計算量はO(1 + min{i, n - i})である。

void add(int i, T x) {
	if (n+1 >= a.length) resize();

	// a[0],...,a[i-1] を左に1つずつずらす
	if (i < n/2) {
		// jが0なら、indexが-1になってしまうため
		j = (j == 0) ? a.length - 1 : j - 1;
		for (int k = 0; k <= i-1; k++)
			a[(j+k) % a.length] = a[(j+k+1) % a.length];
	} else {
		// a[i],...a[n-1] を右に1つずつずらす
		for (int k = n; k > i; k--)
			a[(j+k) % a.length] = a[(j+k-1) % a.length];
	}

	a[(j+i) % a.length] = x;
	n++;
}

removeもaddと同様に実装できる。

T remove(int i) {
	T x = a[(j+i) % a.length];

	if (i < n/2) {
		for (int k = i; k > 0; k--)
			a[(j+k) % a.length] = a[(j+k-1) % a.length];
	} else {
		for (int k = i; k < n-1; k++)
			a[(j+k) % a.length] = a[(j+k+1) % a.length];
	}

	n--;
	if (3*n > a.length) resize();
	return x;
}