両端キューは先頭または末尾で要素を追加・削除できるキューです。
通常のキューは要素を追加するときは末尾からしかできず、取り出すときは先頭からしかできません。通常のリスト（C#のList<T>）は任意の場所で要素の加除ができますが、末尾以外の部分だと処理に時間がかかります。LinkedListは任意の場所で要素の加除を高速におこなうことができますが、ランダムアクセスができません。
ここでは先頭または末尾で要素を追加・削除とランダムアクセスが高速でできるデータ構造の実装を目標とします。
配列デック
ここでは内部処理に配列を使います。配列は定数時間でランダムアクセスが可能です。リングバッファのようなものを作り、ここに両端キューの内容を格納し、バッファが満杯になったときだけサイズを拡大するようにします。リングバッファとは配列の最後の次の要素が先頭になっている配列のことです。
ArrayDeque<T>クラス
クラス名はArrayDeque<T>とし、内部処理で使う配列 Array と格納されたデータの先頭に相当する部分を表す FirstIndex と 最後の次に当たる部分を表す NextToLastIndex を定義します。
Lengthプロパティとインデクサ
FirstIndex と NextToLastIndex から実際に格納されているデータの個数がわかります（Lengthプロパティ）。またFirstIndexからランダムアクセスするときはArrayのどの部分にアクセスすればいいかもわかります（インデクサ）。
AddFirst, AddLast, RemoveFirst, RemoveLastメソッド
要素の加除をおこなうときはArray[i]を更新するとともにFirstIndex と NextToLastIndex の値も変更します。これで両端部分であれば要素の加除が高速でできるようになるとともに、ランダムアクセスもできるようになりました。
Growメソッド
要素を追加した結果、Arrayのサイズでは足りなくなった場合はArrayを拡張します（もっと大きなサイズの新しい配列を生成してArrayに代える）。
実装
ArrayDequeクラスを以下のように定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
public class ArrayDeque<T> { T[] Array; int FirstIndex = 0; int NextToLastIndex = 0; int ArrayLength = 0; int GrowSize = 0; public ArrayDeque(int initSize, int growSize) { if (initSize < 8 || initSize > 1024 * 8) throw new Exception($"第一引数は 8 以上、1024 * 8 以下を指定してください。"); if (growSize < 8 || growSize > 1024 * 8) throw new Exception($"第二引数は 8 以上、1024 * 8 以下を指定してください。"); Array = new T[initSize]; ArrayLength = Array.Length; GrowSize = growSize; FirstIndex = 0; NextToLastIndex = 0; } public int Length { get { if (NextToLastIndex >= FirstIndex) return NextToLastIndex - FirstIndex; else return ArrayLength - (FirstIndex - NextToLastIndex); } } public T this[int index] { get { if (index < 0 || index >= Length) throw new ArgumentOutOfRangeException(nameof(index), index, null); index = FirstIndex + index; if (index >= ArrayLength) index -= ArrayLength; return Array[index]; } } void Grow() { T[] newArray = new T[Array.Length + GrowSize]; for (int i = 0; i < Length; i++) newArray[i] = this[i]; int len = Length; Array = newArray; FirstIndex = 0; NextToLastIndex = len; ArrayLength = newArray.Length; } public void AddFirst(T node) { FirstIndex--; if (FirstIndex < 0) FirstIndex += ArrayLength; Array[FirstIndex] = node; if (ArrayLength == Length + 1) Grow(); } public void AddLast(T node) { Array[NextToLastIndex] = node; NextToLastIndex++; if (NextToLastIndex >= ArrayLength) NextToLastIndex -= ArrayLength; if (ArrayLength == Length + 1) Grow(); } public T RemoveFirst() { if (Length == 0) return default(T); T node = Array[FirstIndex]; Array[FirstIndex] = default(T); FirstIndex++; if (FirstIndex >= ArrayLength) FirstIndex -= ArrayLength; return node; } public T RemoveLast() { if (Length == 0) return default(T); int lastIndex = NextToLastIndex - 1; if (lastIndex < 0) lastIndex += ArrayLength; T node = Array[lastIndex]; Array[lastIndex] = default(T); NextToLastIndex--; if (NextToLastIndex < 0) NextToLastIndex += ArrayLength; return node; } public T First { get { if (Length == 0) return default(T); return Array[FirstIndex]; } } public T Last { get { if (Length == 0) return default(T); int lastIndex = NextToLastIndex - 1; if (lastIndex < 0) lastIndex += ArrayLength; return Array[lastIndex]; } } } |
ためしにArrayDequeクラスを使ってみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
class Program { static void Main() { ArrayDeque <int> arrayDeque = new ArrayDeque<int>(8, 8); while (true) { Console.WriteLine("1:先頭に追加 2:末尾に追加 3:先頭を削除 4:末尾を削除 5:要素を確認 6:すべて表示 0:終了"); int v1 = int.Parse(Console.ReadLine()); if (v1 == 0) break; if (v1 == 1) { Console.WriteLine("追加する値を入力してください"); int v2 = int.Parse(Console.ReadLine()); arrayDeque.AddFirst(v2); } if (v1 == 2) { Console.WriteLine("追加する値を入力ください"); int v2 = int.Parse(Console.ReadLine()); arrayDeque.AddLast(v2); } if (v1 == 3) { int v2 = arrayDeque.RemoveFirst(); Console.WriteLine($"{v2} を削除しました"); } if (v1 == 4) { int v2 = arrayDeque.RemoveLast(); Console.WriteLine($"{v2} を削除しました"); } if (v1 == 5) { int len = arrayDeque.Length; if (len == 0) Console.WriteLine($"空です"); else { Console.WriteLine($"どこを確認しますか？[0-{len - 1}]"); int v2 = int.Parse(Console.ReadLine()); if(0 <= v2 && v2 < len) Console.WriteLine($"値は {arrayDeque[v2]} です"); else Console.WriteLine($"不正なアクセスです"); } } if (v1 == 6) { int len = arrayDeque.Length; if (len == 0) Console.WriteLine($"空です"); else { int[] vs = new int[len]; for (int i = 0; i < len; i++) vs[i] = arrayDeque[i]; Console.WriteLine($"値は [{string.Join(", ", vs)}] です"); } } } } } |
