コーディングテスト頻出データ構造 - HashMap・スタック・キュー
📚 概要
コーディングテストの問題の多くは、適切なデータ構造を選択することで効率的に解けます。HashMap を使えば O(n^2) の全探索が O(n) になり、スタックを使えば括弧の対応チェックが簡潔に書けます。
この記事では、コーディングテストで最も頻出するHashMap、Set、スタック、キュー、連結リストを中心に、それぞれの特性と典型的な使い方を解説します。スライディングウィンドウや Boyer-Moore 投票アルゴリズムなど、データ構造を活用したテクニックも紹介します。
🕰️ 歴史的背景
ハッシュテーブルの誕生
ハッシュテーブルは 1953年 に IBM の Hans Peter Luhn によって考案されました。キーからハッシュ値を計算し、配列のインデックスとして使用することで、O(1) の高速なデータアクセスを実現しました。
スタックとキュー
スタック（LIFO）とキュー（FIFO）は、計算機科学の最も基礎的な抽象データ型です。1946年 に Alan Turing がサブルーチンの戻りアドレスを管理するためにスタックの概念を提唱しました。
現代のデータ構造
- 1950年代: ハッシュテーブル、連結リストの基本概念が確立
- 1960年代: 赤黒木、B木などの平衡二分探索木が開発
- 1970年代: ユニオンファインド、フィボナッチヒープが登場
- 現在: 標準ライブラリにより、これらのデータ構造が簡単に利用可能
🔧 技術解説
1. HashMap / Dictionary
HashMap はキーと値のペアを格納し、キーによる検索・挿入・削除を平均 O(1) で行えるデータ構造です。
HashMap の内部構造
graph TB
A["キー: 'apple'"] --> B["hash('apple') = 3"]
C["キー: 'banana'"] --> D["hash('banana') = 7"]
E["キー: 'cherry'"] --> F["hash('cherry') = 3"]
B --> G["バケット[3]"]
D --> H["バケット[7]"]
F --> G
G --> I["'apple' → 100"]
I --> J["'cherry' → 50"]
H --> K["'banana' → 75"]
style G fill:#ffa94d
style H fill:#51cf66HashMap の計算量
| 操作 | 平均 | 最悪 |
|---|---|---|
| 検索 | O(1) | O(n) |
| 挿入 | O(1) | O(n) |
| 削除 | O(1) | O(n) |
最悪ケースは全てのキーが同じバケットに衝突した場合ですが、実用上は O(1) と考えて問題ありません。
パターン1: 出現回数のカウント
// 配列内の各要素の出現回数を数える
function count_frequency(arr):
freq = {}
for x in arr:
if x in freq:
freq[x] += 1
else:
freq[x] = 1
return freq
// Python では Counter を使える
// from collections import Counter
// freq = Counter(arr)
// 例: 最頻出要素を見つける
function most_frequent(arr):
freq = count_frequency(arr)
max_count = 0
result = None
for key, count in freq.items():
if count > max_count:
max_count = count
result = key
return result
パターン2: Two Sum（ペア探索）
// 配列から合計が target になるペアのインデックスを見つける
// HashMap を使えば O(n)
function two_sum(arr, target):
seen = {} // 値 → インデックス
for i, num in enumerate(arr):
complement = target - num
if complement in seen:
return (seen[complement], i)
seen[num] = i
return None
// 例
two_sum([2, 7, 11, 15], 9) // → (0, 1) 2 + 7 = 9
graph LR
A["i=0: num=2
complement=7
seen={2:0}"] --> B["i=1: num=7
complement=2
2 in seen → 発見!"]
style B fill:#51cf66パターン3: アナグラム判定
// 2つの文字列がアナグラムかどうかを判定する
function is_anagram(s1, s2):
if len(s1) != len(s2):
return False
freq = {}
for c in s1:
freq[c] = freq.get(c, 0) + 1
for c in s2:
freq[c] = freq.get(c, 0) - 1
for count in freq.values():
if count != 0:
return False
return True
// 例
is_anagram("listen", "silent") // → True
is_anagram("hello", "world") // → False
パターン4: 重複チェック
// 配列に重複があるかチェック
function has_duplicate(arr):
seen = {}
for x in arr:
if x in seen:
return True
seen[x] = True
return False
2. Set（集合）
Set は重複のない要素の集合を管理するデータ構造です。存在確認が O(1) で行えます。
// 重複除去
function unique_elements(arr):
return list(set(arr))
// 2つの配列の共通要素（積集合）
function intersection(arr1, arr2):
set1 = set(arr1)
result = []
for x in arr2:
if x in set1:
result.append(x)
set1.remove(x) // 重複を防ぐ
return result
// 例
intersection([1, 2, 2, 3], [2, 2, 3, 4]) // → [2, 2, 3]
3. スタック（Stack）
スタックは**後入れ先出し（LIFO: Last In, First Out）**のデータ構造です。
graph TB
subgraph Stack["スタックの操作"]
direction TB
A["push(3)"] --> B["| 3 |"]
B --> C["push(7)"]
C --> D["| 7 |
| 3 |"]
D --> E["push(1)"]
E --> F["| 1 |
| 7 |
| 3 |"]
F --> G["pop() → 1"]
G --> H["| 7 |
| 3 |"]
end
style F fill:#ffa94d
style H fill:#51cf66| 操作 | 計算量 | 説明 |
|---|---|---|
| push | O(1) | スタックの先頭に要素を追加 |
| pop | O(1) | スタックの先頭から要素を取り出す |
| peek/top | O(1) | 先頭の要素を確認（取り出さない） |
| isEmpty | O(1) | スタックが空かどうか確認 |
パターン: 括弧の対応チェック
// 括弧文字列が正しく閉じているかチェックする
function is_valid_brackets(s):
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for c in s:
if c in '({[':
stack.append(c)
elif c in ')}]':
if not stack or stack[-1] != bracket_map[c]:
return False
stack.pop()
return len(stack) == 0
// テスト
is_valid_brackets("({[]})") // → True
is_valid_brackets("({[}])") // → False
is_valid_brackets("(()") // → False
graph LR
A["入力: '( { [ ] } )'"] --> B["'(' → push"]
B --> C["'{' → push"]
C --> D["'[' → push"]
D --> E["']' → pop '[' ✅"]
E --> F["'}' → pop '{' ✅"]
F --> G["')' → pop '(' ✅"]
G --> H["スタック空 → True"]
style H fill:#51cf66スタックの応用: DFS（深さ優先探索）
// スタックを使った DFS
function dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
4. キュー（Queue）
キューは**先入れ先出し（FIFO: First In, First Out）**のデータ構造です。
graph LR
subgraph Queue["キューの操作"]
A["enqueue(A)"] --> B["| A |"]
B --> C["enqueue(B)"]
C --> D["| A | B |"]
D --> E["enqueue(C)"]
E --> F["| A | B | C |"]
F --> G["dequeue() → A"]
G --> H["| B | C |"]
end
style F fill:#ffa94d
style H fill:#51cf66| 操作 | 計算量 | 説明 |
|---|---|---|
| enqueue | O(1) | キューの末尾に要素を追加 |
| dequeue | O(1) | キューの先頭から要素を取り出す |
| front | O(1) | 先頭の要素を確認 |
| isEmpty | O(1) | キューが空かどうか確認 |
パターン: BFS（幅優先探索）
// キューを使った BFS
function bfs(graph, start):
visited = set()
queue = [start] // deque を使うとより効率的
visited.add(start)
while queue:
node = queue.pop(0) // 先頭から取り出す
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
graph TB
A["1"] --> B["2"]
A --> C["3"]
B --> D["4"]
B --> E["5"]
C --> F["6"]
style A fill:#51cf66
style B fill:#74c0fc
style C fill:#74c0fc
style D fill:#ffa94d
style E fill:#ffa94d
style F fill:#ffa94dBFS の訪問順序: 1 → 2, 3 → 4, 5, 6（レベル順）
5. 連結リスト（Linked List）
Floyd の循環検出アルゴリズム（ウサギとカメ）
連結リストに循環（ループ）があるかどうかを O(n) 時間、O(1) 空間で検出するアルゴリズムです。
graph LR
A["1"] --> B["2"]
B --> C["3"]
C --> D["4"]
D --> E["5"]
E --> C
style C fill:#ffa94d
style E fill:#ff6b6b// Floyd のサイクル検出
function has_cycle(head):
slow = head // カメ: 1歩ずつ
fast = head // ウサギ: 2歩ずつ
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True // サイクルあり
return False // サイクルなし
graph TB
subgraph Step1["ステップ1"]
A1["slow=1, fast=1"]
end
subgraph Step2["ステップ2"]
A2["slow=2, fast=3"]
end
subgraph Step3["ステップ3"]
A3["slow=3, fast=5"]
end
subgraph Step4["ステップ4"]
A4["slow=4, fast=4 → 一致!"]
end
Step1 --> Step2 --> Step3 --> Step4
style Step4 fill:#51cf66サイクルの開始地点を見つける
// サイクルの開始ノードを見つける
function find_cycle_start(head):
slow = head
fast = head
// 1. サイクル内で出会う地点を見つける
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None // サイクルなし
// 2. head と出会い地点から同時に1歩ずつ進む
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow // サイクルの開始地点
6. スライディングウィンドウ
固定長または可変長の「窓」を配列上でスライドさせて、部分配列に関する問題を効率的に解く手法です。
graph LR
A["配列: [1, 3, 2, 6, -1, 4, 1, 8, 2]
ウィンドウサイズ: 5"] --> B["[1,3,2,6,-1] 合計=11"]
B --> C["[3,2,6,-1,4] 合計=14"]
C --> D["[2,6,-1,4,1] 合計=12"]
D --> E["[6,-1,4,1,8] 合計=18"]
E --> F["[-1,4,1,8,2] 合計=14"]
style E fill:#51cf66// 固定長スライディングウィンドウ: サイズ k の部分配列の最大合計
function max_subarray_sum(arr, k):
if len(arr) < k:
return None
// 最初のウィンドウの合計
window_sum = sum(arr[0:k])
max_sum = window_sum
// ウィンドウをスライド
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] // 右端を追加、左端を除去
max_sum = max(max_sum, window_sum)
return max_sum
// 計算量: O(n)（各要素を1回だけ処理）
// 可変長スライディングウィンドウ: 異なる文字が k 種類以下の最長部分文字列
function longest_substring_k_distinct(s, k):
freq = {}
left = 0
max_len = 0
for right in range(len(s)):
// 右端の文字を追加
freq[s[right]] = freq.get(s[right], 0) + 1
// 種類が k を超えたらウィンドウを縮小
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
7. Boyer-Moore 投票アルゴリズム
配列の中で**過半数を占める要素（多数決要素）**を O(n) 時間、O(1) 空間で見つけるアルゴリズムです。
// Boyer-Moore 投票アルゴリズム
function majority_element(arr):
candidate = None
count = 0
for x in arr:
if count == 0:
candidate = x
count = 1
elif x == candidate:
count += 1
else:
count -= 1
return candidate
// 例: [2, 2, 1, 1, 1, 2, 2]
// candidate=2, count=1 → count=2 → count=1 → count=0
// candidate=1, count=1 → count=0
// candidate=2, count=1 → count=2
// 結果: 2
graph LR
A["[2,2,1,1,1,2,2]"] --> B["candidate=2
count=1"]
B --> C["2 → count=2"]
C --> D["1 → count=1"]
D --> E["1 → count=0"]
E --> F["candidate=1
count=1"]
F --> G["2 → count=0"]
G --> H["candidate=2
count=1"]
H --> I["2 → count=2"]
I --> J["答え: 2"]
style J fill:#51cf66注意: このアルゴリズムは「過半数要素が存在する」という前提が必要です。存在しない場合は、結果を検証するために2回目の走査が必要です。
💡 実践例
例題1: グループアナグラム
文字列の配列が与えられたとき、アナグラム同士をグループ化する。
// 入力: ["eat", "tea", "tan", "ate", "nat", "bat"]
// 出力: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
function group_anagrams(strs):
groups = {} // ソート済み文字列 → 元の文字列リスト
for s in strs:
key = ''.join(sorted(s)) // "eat" → "aet"
if key not in groups:
groups[key] = []
groups[key].append(s)
return list(groups.values())
// 計算量: O(n * k log k) n=文字列数, k=最長文字列長
例題2: 最長の括弧列
括弧文字列が与えられたとき、正しく閉じている最長の部分文字列の長さを求める。
// 入力: ")()())"
// 出力: 4 → "()()"
function longest_valid_parentheses(s):
stack = [-1] // 直前の「未対応」位置を記録
max_len = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i) // 新しい「未対応」位置
else:
max_len = max(max_len, i - stack[-1])
return max_len
例題3: 重複しない最長部分文字列
// 入力: "abcabcbb"
// 出力: 3 → "abc"
function length_of_longest_substring(s):
char_index = {} // 文字 → 最後に出現したインデックス
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1
char_index[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
// スライディングウィンドウ + HashMap の組み合わせ
// 計算量: O(n)
📊 データ構造の選択ガイド
操作別の計算量比較
| 操作 | 配列 | 連結リスト | HashMap | スタック | キュー |
|---|---|---|---|---|---|
| インデックスアクセス | O(1) | O(n) | - | - | - |
| 先頭に挿入 | O(n) | O(1) | - | - | - |
| 末尾に挿入 | O(1)* | O(1)** | O(1) | O(1) | O(1) |
| 検索 | O(n) | O(n) | O(1) | O(n) | O(n) |
| 削除 | O(n) | O(1)*** | O(1) | O(1)**** | O(1)**** |
* 動的配列の場合、償却 O(1) ** 末尾ポインタがある場合 *** 削除対象ノードへの参照がある場合 **** 先頭/末尾の削除のみ
いつどのデータ構造を使うか
graph TB
A["問題の要件"] --> B{"キーで高速に検索?"}
B -->|Yes| C["HashMap / Set"]
B -->|No| D{"順序が重要?"}
D -->|"LIFO (後入先出)"| E["スタック"]
D -->|"FIFO (先入先出)"| F["キュー"]
D -->|"ソート順"| G["ソート済み配列 / ヒープ"]
D -->|No| H{"頻繁な挿入削除?"}
H -->|Yes| I["連結リスト"]
H -->|No| J["配列"]
style C fill:#51cf66
style E fill:#74c0fc
style F fill:#ffa94d
style G fill:#b197fc| 問題の特徴 | 推奨データ構造 | 典型例 |
|---|---|---|
| ペア探索、出現回数 | HashMap | Two Sum, アナグラム |
| 重複排除、存在チェック | Set | 共通要素、一意な値 |
| 対応関係、入れ子構造 | スタック | 括弧チェック、DFS |
| レベル順探索 | キュー | BFS、最短経路 |
| サイクル検出 | 2ポインタ | 連結リストのループ |
| 連続部分列 | スライディングウィンドウ | 最長部分文字列 |
| 多数決要素 | Boyer-Moore | 過半数要素 |
🎯 ベストプラクティス
1. まず HashMap を検討する
O(n^2) の二重ループが必要に見える問題は、HashMap で O(n) にできることが多いです。
// Bad: O(n^2) の二重ループ
for i in range(n):
for j in range(i+1, n):
if arr[i] + arr[j] == target:
return (i, j)
// Good: O(n) の HashMap
seen = {}
for i, num in enumerate(arr):
if target - num in seen:
return (seen[target - num], i)
seen[num] = i
2. スタックを使うべきサイン
- 「対応する」「入れ子になった」「最近の」といったキーワードが出たらスタックを検討
- 括弧の対応、HTMLタグの入れ子、直前の要素との比較
3. BFS vs DFS の使い分け
| 特性 | BFS (キュー) | DFS (スタック/再帰) |
|---|---|---|
| 探索順序 | レベル順 | 深さ優先 |
| 最短経路 | 重みなしグラフで最適 | 保証なし |
| メモリ使用量 | O(幅) | O(深さ) |
| 適するケース | 最短距離、レベル探索 | 全探索、パス列挙 |
4. スライディングウィンドウのテンプレート
// 可変長ウィンドウのテンプレート
function sliding_window(arr):
left = 0
result = 初期値
for right in range(len(arr)):
// 1. 右端の要素をウィンドウに追加
ウィンドウを更新(arr[right])
// 2. ウィンドウが条件を満たさなくなったら左端を縮小
while ウィンドウが条件を満たさない:
ウィンドウから除去(arr[left])
left += 1
// 3. 結果を更新
result = 最良値(result, right - left + 1)
return result
🔍 関連する問題
この記事に関連するクイズ問題:
- Q1: HashMap を使ったデータ検索
- Q6: スタックの基本操作
- Q12: 括弧の対応チェック
- Q13: キューと BFS
- Q15: 連結リストの操作
- Q20: アナグラム判定
- Q25: スライディングウィンドウ
- Q28: 重複検出
- Q45: Boyer-Moore 投票アルゴリズム
📝 まとめ
- HashMap: キーによる O(1) 検索。Two Sum、出現回数カウント、アナグラム判定の定番
- Set: 重複排除と O(1) の存在チェック。積集合・和集合の計算にも使える
- スタック: LIFO 構造。括弧チェック、DFS、入れ子構造の処理に必須
- キュー: FIFO 構造。BFS によるレベル順探索、最短経路問題に使う
- Floyd のアルゴリズム: 2つのポインタ（速度差）で連結リストのサイクルを O(1) 空間で検出
- スライディングウィンドウ: 連続部分配列の問題を O(n) で解くテクニック
- Boyer-Moore 投票: 過半数要素を O(n) 時間、O(1) 空間で発見
次のステップ: HashMap と スタック を使う問題を多く解き、「この問題にはこのデータ構造」という直感を養いましょう！