# 基本的なデータ構造：配列・連結リスト・スタック・キュー

> 配列と連結リストのメモリ配置の違いから検索・挿入・削除の計算量を導き、動的配列の償却 O(1) を証明する。スタックとキューを抽象データ型として定義し、リングバッファと 2 本のスタックによる実装を解析する。
> https://rikai.mugen-giken.com/computer-science/algorithms/data-structures

## 0. この記事の要点

- データ構造の優劣は「何ができるか」ではなく「どの操作がどれだけ速いか」で決まります。同じ列を表す配列と連結リストは、速い操作がちょうど正反対です。
- 配列は添字によるアクセスが $\Theta(1)$、途中への挿入・削除が $\Theta(n)$。連結リストは位置を指すノードが手元にあればその直後への挿入・削除が $\Theta(1)$、$k$ 番目へのアクセスが $\Theta(k)$ です（<Ref to="prop-array" />、<Ref to="prop-list" />）。
- 容量を 2 倍ずつ増やす動的配列は、1 回の push の最悪計算量が $\Theta(n)$ であっても、$n$ 回の合計は $3n$ 未満に収まります。償却計算量は $O(1)$ です（<Ref to="thm-dynamic-array" />）。
- 「償却 $O(1)$」は「平均的に速い」という意味ではありません。入力の確率分布を一切仮定せず、どんな操作列に対しても合計コストが保証されます。
- スタック（LIFO）とキュー（FIFO）は抽象データ型であり、実装に触れずに公理で規定できます。同じ公理を配列でも連結リストでも満たせます。
- キューはリングバッファで最悪 $\Theta(1)$（<Ref to="prop-ring-buffer" />）、2 本のスタックで償却 $O(1)$（<Ref to="thm-two-stack-queue" />）に実現できます。後者はポテンシャル法で解析します。

## 1. 動機

プログラムが扱うデータの多くは「列」です。テキストは文字の列、画像は画素の列、口座の履歴は取引の列です。列を計算機の中でどう並べるかには選択の余地があり、その選択によって処理時間が桁単位で変わります。

素朴な疑問から始めましょう。なぜ配列と連結リストという二つの表現が、どちらも半世紀以上使われ続けているのでしょうか。答えは、両者の得意な操作がちょうど正反対だからです。配列は「$i$ 番目を見せてほしい」に強く、「途中に割り込ませてほしい」に弱い。連結リストはその逆です。片方がすべての操作で勝っていれば、もう片方は歴史から消えていたはずです。

歴史的にも、この二つは別々の要求から生まれました。配列は最初期の高級言語 Fortran（1957 年）から言語機能として存在します。連結リストはやや遅れて、1956 年前後に Allen Newell、Cliff Shaw、Herbert Simon が定理証明プログラム Logic Theorist のために設計した情報処理言語 IPL で導入され、1958 年の LISP に受け継がれました。彼らが必要としたのは「途中に要素を割り込ませても、後ろ全体をずらさなくてよい表現」でした。

この記事では、前章 [計算量と O 記法](/computer-science/algorithms/complexity-and-big-o) の $O$・$\Theta$ 記法（<Ref to="computer-science/algorithms/complexity-and-big-o#def-big-o" />）を道具として使い、まず「何ができるか」（抽象データ型）と「どう実現するか」（データ構造）を分けます。そのうえで配列・連結リスト・スタック・キューを取り上げ、各操作の計算量を証明付きで求めます。

## 2. 準備：計算モデルと抽象データ型

計算量を「証明する」には、何を 1 単位時間とみなすかを先に決めなければなりません。この記事ではワード RAM モデルを使います。これは前章の <Ref to="computer-science/algorithms/complexity-and-big-o#def-ram" text="一様コスト RAM モデル" /> を、記憶領域の番地づけまで具体化したものです。

記憶領域は番地 $0, 1, 2, \ldots$ で添字づけられた語の列 $M[0], M[1], \ldots$ であり、1 語は整数か番地を 1 つ保持できます。番地 $i$ を指定した $M[i]$ の読み出し・書き込み、および語同士の加減乗除と比較は、いずれも 1 単位時間で実行できるものとします。この「番地を指定した読み書きが定数時間」という仮定が、後で見る「配列の添字アクセスが $\Theta(1)$」の根拠です。

<Remark id="rem-ram">
ワード RAM は理想化です。実際の計算機には階層的なキャッシュがあり、1 語のアクセス時間は一定ではありません。それでもこのモデルを使うのは、アルゴリズムの本質的な差（$\Theta(n)$ か $\Theta(\log n)$ か $\Theta(1)$ か）がキャッシュの有無に影響されないからです。同じ $\Theta(n)$ どうしの実測差はモデルの外にあり、<Ref to="rem-cache" /> で扱います。
</Remark>

次に、データ構造を論じるための基本的な区別を導入します。

<Definition id="def-adt" title="抽象データ型">
抽象データ型（abstract data type, ADT）とは、次の 3 つの組であって、値の内部表現を一切含まないものをいう。

1. 値の集合。
2. 操作の名前と、その引数および返り値の型。
3. 操作が満たすべき性質。事前条件と事後条件で書いてもよいし、操作どうしが満たす等式（公理）で書いてもよい。

抽象データ型を、具体的な記憶領域の配置と手続きによって実現したものをデータ構造という。
</Definition>

この区別が効くのは、同じ抽象データ型に複数のデータ構造がありうるからです。どれを選ぶかは「正しさ」では決まらず、どの操作を何回使うかと、その操作の計算量で決まります。

## 3. 配列と動的配列

<Definition id="def-array" title="配列">
長さ $n$ の配列とは、同じ大きさ $s$（語数）の $n$ 個の区画を、先頭番地 $b$ から連続した番地に並べたものをいう。$i$ 番目の要素（$0 \le i \le n-1$）を $A[i]$ と書き、その区画の先頭番地は
$$
\mathrm{addr}(A[i]) = b + s \cdot i
$$
で与えられる。
</Definition>

定義に現れるこの 1 本の式が、配列の強さと弱さの両方を決めています。番地が $i$ の一次式で書けるので、どの要素にも計算だけで到達できます。一方、要素を 1 つ割り込ませると、それ以降の要素の $i$ がすべて 1 ずつずれ、番地もすべてずれます。順に確認します。

<Proposition id="prop-array" title="配列の基本操作の計算量">
長さ $n$ の配列 $A$ について、ワード RAM モデルの下で次が成り立つ。

1. 添字 $i$（$0 \le i \le n-1$）を指定した要素の読み出しと書き込みは $\Theta(1)$ 時間で行える。
2. 与えられた値 $x$ が $A$ に現れるかどうかを判定する探索は、要素の並びに順序の仮定がない場合、最悪 $\Theta(n)$ 時間を要する。先頭から順に比較する線形探索がこの計算量を達成する。
3. 位置 $i$（$0 \le i \le n$）への挿入は既存要素の移動をちょうど $n - i$ 回、位置 $i$（$0 \le i \le n-1$）の要素の削除は $n - 1 - i$ 回必要とし、いずれも $\Theta(n-i)$ 時間で行える。とくに最悪（$i = 0$）は $\Theta(n)$ であり、挿入位置 $i$ が $0, 1, \ldots, n$ 上一様分布に従うときの平均移動回数は $n/2$ である。
</Proposition>

<Proof of="prop-array">
**1.** <Ref to="def-array" /> より $\mathrm{addr}(A[i]) = b + s \cdot i$ です。$b$ と $s$ は配列ごとに固定なので、この計算は乗算 1 回と加算 1 回。ワード RAM では算術演算と番地指定の読み書きがそれぞれ 1 単位時間なので、合計は定数時間、すなわち $\Theta(1)$ です。$n$ にも $i$ にも依存しない点が重要です。

**2.** 上界は線形探索が与えます。$i = 0, 1, \ldots, n-1$ の順に $A[i]$ を読んで $x$ と比較し、一致すれば真を返し、最後まで一致しなければ偽を返します。各反復は 1 の意味で定数時間なので、全体で $O(n)$ です。

下界を敵対者論法で示します。正しいアルゴリズム $\mathcal{B}$ が、$x$ を含まない入力 $A$ に対し、ある位置 $j$ を一度も読まずに「含まない」と答えたとします。$A$ の位置 $j$ だけを $x$ に置き換えた $A'$ を与えると、$\mathcal{B}$ は $j$ を読まないので同じ計算をたどり、やはり「含まない」と答えます。しかし $A'$ は $x$ を含むので誤りです。よって $n$ 箇所すべてを読む必要があり $\Omega(n)$、上界と合わせて $\Theta(n)$ です。

**3.** 挿入を示します。挿入後の配列 $A'$ は $A'[j] = A[j]$（$j < i$）、$A'[i] = x$、$A'[j+1] = A[j]$（$i \le j \le n-1$）を満たします。$j \ge i$ の要素は例外なく番地が $s$ だけ後ろにずれるので、少なくとも $n - i$ 回の書き込みが必要です。逆に、$j = n-1, n-2, \ldots, i$ の順に $A[j+1] \leftarrow A[j]$ と後ろから詰めれば、上書きによる損失なく $n-i$ 回の書き込みで済み、最後に $A[i] \leftarrow x$ を 1 回行えば完了します。1 回の移動は 1 の意味で定数時間なので、合計 $\Theta(n-i)$ です。削除も同様に、$j = i+1, \ldots, n-1$ の順に $A[j-1] \leftarrow A[j]$ と前へ詰めることで $n-1-i$ 回の移動、すなわち $\Theta(n-i)$ です。

最悪は $i = 0$ で移動回数 $n$、よって $\Theta(n)$ です。平均は
$$
\frac{1}{n+1}\sum_{i=0}^{n}(n-i) = \frac{1}{n+1}\sum_{k=0}^{n}k = \frac{1}{n+1}\cdot\frac{n(n+1)}{2} = \frac{n}{2}
$$
となり、これも $\Theta(n)$ です。平均を取っても $\Theta(n)$ から逃げられません。
</Proof>

配列の弱点はもう一つあります。長さを最初に決めなければならないことです。要素数が実行時に増えていく場合、配列そのままでは扱えません。この問題を解くのが動的配列（可変長配列）です。素朴に「1 つ増えるたびに長さ $+1$ の配列を確保して全部コピーする」と、$n$ 回の追加で $\sum_{k=1}^{n} k = \Theta(n^2)$ 回のコピーが発生します。ところが、増やし方を「$+1$」から「$2$ 倍」に変えるだけで、合計が線形に落ちます。

<Theorem id="thm-dynamic-array" title="動的配列の償却計算量">
次の規則で末尾追加 $\mathrm{push}$ を実現するデータ構造を考える。容量 $c$ の配列 $A$ と現在の要素数 $n$（$0 \le n \le c$）を保持し、初期状態を $n = 0$、$c = 1$ とする。$\mathrm{push}(x)$ は次のように動作する。

- $n < c$ ならば $A[n] \leftarrow x$ とし、$n \leftarrow n + 1$ とする。
- $n = c$ ならば、まず長さ $2c$ の配列を新たに確保して既存の $c$ 個の要素をそこへ移し、$c \leftarrow 2c$ としてから上の操作を行う。

このとき、空の状態から $\mathrm{push}$ を $n$ 回（$n \ge 1$）行うときの要素の書き込み回数の合計は $3n$ 未満である。したがって 1 回の $\mathrm{push}$ あたりの償却計算量は $O(1)$ である。ただし、個々の $\mathrm{push}$ の最悪計算量は $\Theta(n)$ である。
</Theorem>

<Proof of="thm-dynamic-array">
集約法（総コストを直接見積もり、操作回数で割る方法）で示します。

書き込みを 2 種類に分けます。$A[n] \leftarrow x$ という末尾への書き込みは、どの $\mathrm{push}$ でもちょうど 1 回起きるので合計 $n$ 回です。

残りは容量拡張に伴うコピーです。拡張が起きるのは $\mathrm{push}$ の直前に $n = c$ のときで、容量は $1, 2, 4, \ldots$ と 2 の冪をたどるので、これは直前の要素数が $2^k$（$k = 0, 1, 2, \ldots$）のときに限られ、コピー回数はちょうど $2^k$ です。$n$ 回の $\mathrm{push}$ の間に要素数が $2^k$ に達するのは $2^k < n$ を満たす $k$ に対してだけなので、$K$ をそのような最大の $k$ とすると、コピーの総数は
$$
\sum_{k=0}^{K} 2^{k} = 2^{K+1} - 1 < 2 \cdot 2^{K} \le 2n
$$
です。最後の不等号で $2^K < n$ を使いました。

以上より総書き込み回数は $n + 2n = 3n$ 未満です。$n$ 回の操作で総コストが $3n$ 未満なので、1 回あたりの償却コストは $3$ 未満、すなわち $O(1)$ です。

最悪計算量については、要素数が $n = c = 2^k$ の状態での $\mathrm{push}$ が $2^k = n$ 回のコピーを行うので、<Ref to="prop-array" /> の 1 より $\Theta(n)$ 時間かかります。
</Proof>

<Example id="ex-doubling" title="10 回の push を数え上げる">
空の状態から 10 回 $\mathrm{push}$ したときの書き込み回数を数えます。拡張が起きるのは直前の要素数が $1, 2, 4, 8$ のとき、すなわち 2・3・5・9 回目の $\mathrm{push}$ です。

| push 番号 | 直前の $(n, c)$ | 拡張後の容量 | コピー回数 | この回の書き込み合計 |
|---|---|---|---|---|
| 1 | $(0, 1)$ | — | 0 | 1 |
| 2 | $(1, 1)$ | 2 | 1 | 2 |
| 3 | $(2, 2)$ | 4 | 2 | 3 |
| 5 | $(4, 4)$ | 8 | 4 | 5 |
| 9 | $(8, 8)$ | 16 | 8 | 9 |
| 4, 6, 7, 8, 10 | — | — | 0 | 各 1 |

総書き込み回数は $10 + (1 + 2 + 4 + 8) = 25$ で、定理の保証する上界 $3 \times 10 = 30$ を下回っています。9 回目の $\mathrm{push}$ だけで 9 回の書き込みが必要ですが、平らにならせば 1 回あたり $2.5$ 回です。
</Example>

<Remark id="rem-amortized" title="償却と平均は別のもの">
償却計算量は確率をまったく含みません。<Ref to="thm-dynamic-array" /> が主張しているのは「どんな $\mathrm{push}$ の並びに対しても、合計が $3n$ 未満」という決定論的な保証です。ハッシュ表の平均計算量（<Ref to="computer-science/algorithms/searching#thm-chaining" />）のように「入力が一様分布なら」という仮定を置く議論とは、意味も強さも違います。この区別については <Ref to="computer-science/algorithms/searching#rem-three-averages" /> も参照してください。

また、この定理は増やし方が定数倍であること（コピー回数が幾何級数になること）に依存しています。「毎回 $+1$」にすると $k$ 回目の $\mathrm{push}$ で $k-1$ 個のコピーが発生し、合計 $\sum_{k=1}^{n}(k-1) = \Theta(n^2)$ となって償却 $O(1)$ は崩れます。逆に、比率が $1$ より大きい定数でありさえすれば $2$ 倍である必要はなく、$1.5$ 倍でも $1.125$ 倍でも同じ議論が通ります。
</Remark>

## 4. 連結リスト

配列の弱点は「番地が添字で決まってしまう」ことでした。ならば、番地を要素自身に持たせればよい、というのが連結リストの発想です。

<Definition id="def-linked-list" title="単方向連結リスト">
ノードとは、値を保持するフィールド $\mathrm{value}$ と、別のノードへの参照または $\mathrm{nil}$ を保持するフィールド $\mathrm{next}$ からなる区画をいう。ノード $p_0, p_1, \ldots, p_{n-1}$ が
$$
p_j.\mathrm{next} = p_{j+1} \quad (0 \le j \le n-2), \qquad p_{n-1}.\mathrm{next} = \mathrm{nil}
$$
を満たすとき、この列を単方向連結リストといい、先頭ノードへの参照 $\mathrm{head} = p_0$ によってリスト全体を表す。空のリストは $\mathrm{head} = \mathrm{nil}$ で表す。各ノードが $\mathrm{prev}$ フィールドも持ち $p_{j+1}.\mathrm{prev} = p_j$ を満たすものを双方向連結リストという。
</Definition>

ノードの番地には何の制約もありません。記憶領域のどこに散らばっていてもよく、つながりは $\mathrm{next}$ の値だけが表しています。この自由さが、そのまま計算量の特徴になります。

<Proposition id="prop-list" title="連結リストの基本操作の計算量">
$n$ 個のノードからなる単方向連結リストについて、ワード RAM モデルの下で次が成り立つ。

1. ノード $p$ への参照が与えられているとき、$p$ の直後への新しいノードの挿入、および $p$ の直後のノードの削除は、いずれも $\Theta(1)$ 時間で行える。
2. 先頭から数えて $k$ 番目（$0$ 始まり、$0 \le k \le n-1$）のノードへ到達するには、$\mathrm{next}$ の追跡がちょうど $k$ 回必要であり、$\Theta(k)$ 時間かかる。最悪は $\Theta(n)$ である。
3. 単方向連結リストでは、ノード $p$ への参照が与えられていても、$p$ 自身の削除には最悪 $\Theta(n)$ 時間かかる。双方向連結リストであれば $\Theta(1)$ 時間で行える。
</Proposition>

<Proof of="prop-list">
**1.** 挿入は、新しいノード $q$ を用意して
$$
q.\mathrm{next} \leftarrow p.\mathrm{next}, \qquad p.\mathrm{next} \leftarrow q
$$
の 2 回の書き込みで完了します。実行後、$p$ の直後は $q$、$q$ の直後は元の $p.\mathrm{next}$ となり、<Ref to="def-linked-list" /> の連結条件が保たれます。削除は、$p.\mathrm{next} \ne \mathrm{nil}$ のとき
$$
p.\mathrm{next} \leftarrow p.\mathrm{next}.\mathrm{next}
$$
の 1 回の書き込みで完了します。どちらも読み書きの回数が $n$ にも $k$ にも依存しないので $\Theta(1)$ 時間です。<Ref to="prop-array" /> の 3 では位置 $i$ の挿入に $n-i$ 回の移動が必要でしたが、ここでは要素をひとつも動かしていません。

**2.** 上界は、$\mathrm{head}$ から始めて $\mathrm{next}$ を $k$ 回たどる手続きが与えます。各追跡は 1 語の読み出しなので定数時間、合計 $\Theta(k)$ です。

下界については、このモデルでノードの番地を知る手段が「$\mathrm{head}$ を読む」「既に到達したノードの $\mathrm{next}$ を読む」の 2 つしかないことを使います。<Ref to="def-array" /> の配列と違い、$k$ 番目のノードの番地を $k$ から計算する式は存在しません。したがって到達済みノードの集合は 1 回の追跡で高々 1 個しか増えず、$p_k$ に至るには少なくとも $k$ 回の追跡が必要です。以上より $\Theta(k)$ です。

**3.** $p$ 自身の削除には、直前のノード $p'$ を見つけて $p'.\mathrm{next} \leftarrow p.\mathrm{next}$ とする必要があります。単方向リストでは $p$ から $p'$ をたどれないため、$\mathrm{head}$ から順に $\mathrm{next}$ が $p$ に一致するノードを探すしかなく、2 より最悪 $\Theta(n)$ です。双方向連結リストなら $p'= p.\mathrm{prev}$ が定数時間で得られるので、
$$
p.\mathrm{prev}.\mathrm{next} \leftarrow p.\mathrm{next}, \qquad p.\mathrm{next}.\mathrm{prev} \leftarrow p.\mathrm{prev}
$$
の 2 回の書き込みで済み、$\Theta(1)$ 時間です（両端の $\mathrm{nil}$ の場合分けは <Ref to="rem-sentinel" /> の番兵で消せます）。
</Proof>

<Example id="ex-list-ops" title="挿入と削除を実際に動かす">
Python で <Ref to="prop-list" /> の 1 を確かめます。

```python
class Node:
    __slots__ = ("value", "next")

    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def insert_after(p: Node, x) -> Node:
    """p の直後に値 x のノードを挿入して、そのノードを返す。"""
    q = Node(x, p.next)   # q.next <- p.next
    p.next = q            # p.next  <- q
    return q


def delete_after(p: Node) -> None:
    """p の直後のノードを削除する。直後が無ければ何もしない。"""
    if p.next is not None:
        p.next = p.next.next


def to_list(head: Node) -> list:
    out, cur = [], head
    while cur is not None:
        out.append(cur.value)
        cur = cur.next
    return out


head = Node(3, Node(1, Node(4)))
print(to_list(head))           # [3, 1, 4]
insert_after(head, 5)
print(to_list(head))           # [3, 5, 1, 4]
delete_after(head.next)
print(to_list(head))           # [3, 5, 4]
```

`insert_after` の本体は 2 行、`delete_after` は 1 行で、どちらもリストの長さに依存するループを含みません。これが $\Theta(1)$ の中身です。一方 `to_list` は末尾まで $\mathrm{next}$ をたどるので $\Theta(n)$ かかり、長さを知りたいだけでも全体の走査が要ります（要素数を別に保持すれば $\Theta(1)$ です）。
</Example>

<Remark id="rem-sentinel" title="番兵ノード">
実装では、値を持たないダミーのノード（番兵、sentinel）を先頭に 1 つ置き、$\mathrm{head}$ の代わりに番兵への参照を保持する手法がよく使われます。こうすると「先頭への挿入」「先頭の削除」が「番兵の直後への挿入・削除」に統一され、<Ref to="prop-list" /> の 1 がそのまま適用できます。空リストの判定は「番兵の $\mathrm{next}$ が $\mathrm{nil}$ かどうか」になります。場合分けが減るぶんバグも減るので、実装するときは番兵から始めるとよいでしょう。
</Remark>

## 5. 二つの表現の対比

ここまでの結果を並べます。まず、両者のメモリ上の姿を見比べてください。

<Figure caption="配列と連結リストのメモリ配置。配列は番地が添字から計算でき、連結リストは参照をたどるしかない。">
<svg viewBox="0 0 720 296" width="100%" role="img" aria-label="配列と連結リストのメモリ配置の比較">
  <text x="14" y="22" fill="currentColor" font-size="14" font-family="sans-serif">配列: 連続した番地に並ぶ。A[i] の番地は b + s·i と計算できる</text>
  <g stroke="currentColor" stroke-width="1.5" fill="none">
    <rect x="60" y="56" width="64" height="40" />
    <rect x="124" y="56" width="64" height="40" />
    <rect x="188" y="56" width="64" height="40" />
    <rect x="252" y="56" width="64" height="40" />
    <rect x="316" y="56" width="64" height="40" />
    <rect x="380" y="56" width="64" height="40" />
  </g>
  <g fill="currentColor" font-family="sans-serif" text-anchor="middle">
    <g font-size="14">
      <text x="92" y="82">3</text>
      <text x="156" y="82">1</text>
      <text x="220" y="82">4</text>
      <text x="284" y="82">1</text>
      <text x="348" y="82">5</text>
      <text x="412" y="82">9</text>
    </g>
    <g font-size="11">
      <text x="92" y="48">b</text>
      <text x="156" y="48">b+s</text>
      <text x="220" y="48">b+2s</text>
      <text x="284" y="48">b+3s</text>
      <text x="348" y="48">b+4s</text>
      <text x="412" y="48">b+5s</text>
      <text x="92" y="114">A[0]</text>
      <text x="156" y="114">A[1]</text>
      <text x="220" y="114">A[2]</text>
      <text x="284" y="114">A[3]</text>
      <text x="348" y="114">A[4]</text>
      <text x="412" y="114">A[5]</text>
    </g>
  </g>
  <text x="14" y="164" fill="currentColor" font-size="14" font-family="sans-serif">連結リスト: ノードの番地はばらばら。各ノードが値と「次への参照」を持つ</text>
  <g stroke="currentColor" stroke-width="1.5" fill="none">
    <rect x="100" y="196" width="90" height="44" />
    <path d="M 156 196 L 156 240" />
    <rect x="250" y="196" width="90" height="44" />
    <path d="M 306 196 L 306 240" />
    <rect x="400" y="196" width="90" height="44" />
    <path d="M 456 196 L 456 240" />
    <rect x="550" y="196" width="90" height="44" />
    <path d="M 606 196 L 606 240" />
    <path d="M 606 240 L 640 196" />
  </g>
  <g stroke="var(--sl-color-accent)" fill="var(--sl-color-accent)" stroke-width="2">
    <path d="M 58 218 L 92 218" />
    <path d="M 173 218 L 242 218" />
    <path d="M 323 218 L 392 218" />
    <path d="M 473 218 L 542 218" />
    <circle cx="173" cy="218" r="3.5" stroke="none" />
    <circle cx="323" cy="218" r="3.5" stroke="none" />
    <circle cx="473" cy="218" r="3.5" stroke="none" />
    <path d="M 100 218 L 92 213 L 92 223 Z" stroke="none" />
    <path d="M 250 218 L 242 213 L 242 223 Z" stroke="none" />
    <path d="M 400 218 L 392 213 L 392 223 Z" stroke="none" />
    <path d="M 550 218 L 542 213 L 542 223 Z" stroke="none" />
  </g>
  <g fill="currentColor" font-family="sans-serif">
    <g font-size="14" text-anchor="middle">
      <text x="128" y="223">3</text>
      <text x="278" y="223">1</text>
      <text x="428" y="223">4</text>
      <text x="578" y="223">1</text>
    </g>
    <text x="14" y="222" font-size="12">head</text>
    <g font-size="11" text-anchor="middle">
      <text x="128" y="262">値</text>
      <text x="196" y="262">次への参照</text>
      <text x="623" y="262">nil</text>
    </g>
  </g>
</svg>
</Figure>

<Ref to="prop-array" /> と <Ref to="prop-list" />、および <Ref to="thm-dynamic-array" /> をまとめると、次の表になります。連結リストは末尾ノードへの参照も保持しているものとします。

| 操作 | 動的配列 | 単方向連結リスト |
|---|---|---|
| $i$ 番目の読み書き | $\Theta(1)$ | $\Theta(i)$（最悪 $\Theta(n)$） |
| 値による探索（順序の仮定なし） | $\Theta(n)$ | $\Theta(n)$ |
| 値による探索（整列済み） | $\Theta(\log n)$（二分探索） | $\Theta(n)$ |
| 先頭への挿入・先頭の削除 | $\Theta(n)$ | $\Theta(1)$ |
| 末尾への追加 | 償却 $\Theta(1)$ | $\Theta(1)$ |
| 末尾の削除 | $\Theta(1)$ | $\Theta(n)$（直前ノードが必要） |
| 添字 $i$ で指定した位置への挿入・削除 | $\Theta(n-i)$ | $\Theta(i)$ |
| 手元にあるノードの直後への挿入・削除 | $\Theta(n-i)$ | $\Theta(1)$ |
| 要素以外に必要な記憶領域 | 未使用の容量（最大で要素数と同程度） | ノードごとに参照 1 個分 |

表の最後から 2 行目が両者の性格をもっとも鋭く表しています。「今いる場所の隣に入れる」は連結リストでは $\Theta(1)$、配列では $\Theta(n-i)$。逆に「$i$ 番目に飛ぶ」は配列では $\Theta(1)$、連結リストでは $\Theta(i)$ です。選択は、この 2 種類の操作をそれぞれ何回使うかで決まります。

<Aside type="caution">
「配列は検索が $O(1)$」という言い方をときどき見かけますが、正確ではありません。$O(1)$ なのは**添字を指定したアクセス** $A[i]$ です。値 $x$ がどこにあるかを探す**探索**は、順序の仮定がなければ $\Theta(n)$ かかります（<Ref to="prop-array" /> の 2）。整列済みの配列なら二分探索で $\Theta(\log n)$ になりますが（<Ref to="computer-science/algorithms/searching#thm-binary-cost" />）、それが可能なのは「中央の要素に定数時間で到達できる」からで、連結リストでは同じ手が使えません。配列を整列済みに保つ方法は [ソートアルゴリズム](/computer-science/algorithms/sorting)、探索の詳細は [探索アルゴリズム](/computer-science/algorithms/searching) を参照してください。
</Aside>

<Remark id="rem-cache" title="定数因子とキャッシュ">
$\Theta$ 記法は定数因子を隠します。実測では、隠された部分が効くことがあります。現代の CPU は主記憶を語単位ではなくキャッシュライン単位（典型的には 64 バイト）で読み込むため、配列を先頭から走査すると 1 回の読み込みで複数の要素がキャッシュに載ります。連結リストの走査では、次のノードの番地が読んでみるまで分からず、ノードが記憶領域に散らばっているほどキャッシュミスが増えます。

結果として、「途中への挿入が多いから連結リスト」という判断が、要素数が数千程度までは実測で裏切られることがあります。迷ったら、まず動的配列で書いて測ってから考えるのがよいでしょう。
</Remark>

## 6. スタック

ここからは抽象データ型の側に移ります。スタックは、最後に入れたものが最初に出てくる（last in, first out, LIFO）という一点だけを規定した型です。

<Definition id="def-stack" title="スタック">
スタックとは、次の操作をもつ抽象データ型である。値の型を $X$、スタックの全体を $\mathcal{S}$ と書く。

- $\mathrm{empty} \in \mathcal{S}$（空のスタック）
- $\mathrm{push} : \mathcal{S} \times X \to \mathcal{S}$（積む）
- $\mathrm{pop} : \mathcal{S} \to \mathcal{S}$（頂上を取り除く）
- $\mathrm{top} : \mathcal{S} \to X$（頂上を読む）
- $\mathrm{isEmpty} : \mathcal{S} \to \{\mathrm{true}, \mathrm{false}\}$

これらは任意の $S \in \mathcal{S}$、$x \in X$ について次の公理を満たす。
$$
\begin{aligned}
&\mathrm{isEmpty}(\mathrm{empty}) = \mathrm{true}, \qquad \mathrm{isEmpty}(\mathrm{push}(S, x)) = \mathrm{false}, \\
&\mathrm{top}(\mathrm{push}(S, x)) = x, \qquad \mathrm{pop}(\mathrm{push}(S, x)) = S.
\end{aligned}
$$
$\mathrm{top}(\mathrm{empty})$ と $\mathrm{pop}(\mathrm{empty})$ は定義されない（実装ではエラーとする）。
</Definition>

公理 $\mathrm{pop}(\mathrm{push}(S, x)) = S$ が LIFO そのものです。$x$ を積んでから取り除くと、積む前の状態にぴったり戻る、と言っています。この 4 本の等式のどこにも配列やノードは現れません。実装が何であれ、これらを満たせばスタックです。実装は 2 通りあり、どちらも既に得た結果から計算量が読めます。

**動的配列による実装.** 要素を $A[0], \ldots, A[n-1]$ と並べ、頂上を $A[n-1]$ とします。$\mathrm{push}$ は末尾追加なので償却 $\Theta(1)$（<Ref to="thm-dynamic-array" />）、$\mathrm{pop}$ は $n \leftarrow n-1$、$\mathrm{top}$ は $A[n-1]$ の読み出しなので最悪 $\Theta(1)$ です（<Ref to="prop-array" /> の 1）。<Ref to="prop-array" /> の 3 が要求する要素の移動は、末尾での操作に限れば $n-i = 0$ となって発生しません。

**連結リストによる実装.** 頂上を先頭ノードとし、$\mathrm{push}$ を先頭への挿入、$\mathrm{pop}$ を先頭の削除とします。番兵を置けばどちらも <Ref to="prop-list" /> の 1 に帰着し、最悪 $\Theta(1)$ です。償却ではなく最悪で $\Theta(1)$ なので、1 回の応答時間に上限が要る場面ではこちらが有利です。代わりにノードごとに参照 1 個分の領域がかかります。

スタックの使い道を、証明のつく形で一つ見ておきます。括弧の対応判定です。

<Theorem id="thm-bracket" title="括弧列の判定">
記号の集合を $\Sigma = \{\,\texttt{(}\,,\,\texttt{)}\,,\,\texttt{[}\,,\,\texttt{]}\,\}$ とし、対応の取れた括弧列の集合 $B \subseteq \Sigma^{*}$ を、次の 3 つの規則で生成される最小の集合として定める。
$$
\varepsilon \in B, \qquad w \in B \implies \texttt{(} w \texttt{)} \in B \ \text{かつ}\ \texttt{[} w \texttt{]} \in B, \qquad u, v \in B \implies uv \in B.
$$
入力 $w \in \Sigma^{*}$ に対する次のアルゴリズム $\mathcal{A}$ を考える。空のスタック $S$ から始め、$w$ を左から 1 文字ずつ読む。

- 読んだ文字が開き括弧なら、それを $S$ に $\mathrm{push}$ する。
- 読んだ文字が閉じ括弧なら、$S$ が空であれば直ちに拒否し、そうでなければ $\mathrm{top}$ を見て $\mathrm{pop}$ し、取り出した文字がその閉じ括弧と同種の開き括弧でなければ拒否する。

全文字を読み終えた時点で $S$ が空なら受理、空でなければ拒否する。このとき、$\mathcal{A}$ が $w$ を受理することと $w \in B$ であることは同値である。また $\mathcal{A}$ の実行時間は $\Theta(|w|)$ である。
</Theorem>

<Proof of="thm-bracket">
**準備（スタックの相対性）.** $\mathcal{A}$ はスタックの頂上しか参照せず、空のスタックから $\mathrm{pop}$ しようとした時点で拒否します。したがって、初期スタックを $\sigma$ として $u$ を処理する実行と、空スタックから同じ $u$ を処理する実行は、後者が「空からの $\mathrm{pop}$」で拒否する場合を除いて、$\sigma$ より上の変化がまったく同じです。以下この事実を繰り返し使います。

**($\Rightarrow$) $w \in B$ ならば受理する.** 次の、より強い主張を $B$ の生成規則に関する構造帰納法で示します。

> $w \in B$ ならば、任意の初期スタック $\sigma$ から $w$ を処理したとき $\mathcal{A}$ は拒否せず、処理後のスタックは $\sigma$ に戻る。

- $w = \varepsilon$ のとき。何も読まないので拒否せず、スタックは $\sigma$ のままです。
- $w = \texttt{(} u \texttt{)}$（$u \in B$）のとき。最初の $\texttt{(}$ を読むとスタックは $\sigma\texttt{(}$ になります。帰納法の仮定を初期スタック $\sigma\texttt{(}$ で $u$ に適用すると、拒否せず、処理後のスタックは $\sigma\texttt{(}$ に戻ります。次に $\texttt{)}$ を読むと、スタックは空でなく頂上は $\texttt{(}$ なので $\mathrm{pop}$ して種類が一致し、拒否しません。処理後のスタックは $\sigma$ です。$w = \texttt{[} u \texttt{]}$ も同じ議論です。
- $w = uv$（$u, v \in B$）のとき。帰納法の仮定を初期スタック $\sigma$ で $u$ に適用すると、拒否せずスタックは $\sigma$ に戻ります。続けて同じ仮定を $v$ に適用すれば、やはり拒否せずスタックは $\sigma$ です。

とくに $\sigma$ を空スタックとすれば、$\mathcal{A}$ は拒否せず、読み終えたときのスタックは空なので受理します。

**($\Leftarrow$) 受理するならば $w \in B$.** $|w|$ に関する強い帰納法で示します。$w = \varepsilon$ なら生成規則の第 1 条より $w \in B$ です。$|w| \ge 1$ とします。

$w_1$ が閉じ括弧だとすると、その時点でスタックは空なので $\mathcal{A}$ は拒否し、仮定に反します。よって $w_1$ は開き括弧です。これを $c$、対応する閉じ括弧を $\bar{c}$ と書きます。$c$ は 1 文字目で $\mathrm{push}$ され、受理時にはスタックが空なので、どこかで $\mathrm{pop}$ されます。それが $j$ 文字目を読んだときだとします。

$c$ はスタックの最下段にあり $j$ 文字目で初めて取り除かれるので、位置 $2, \ldots, j-1$ の処理中はスタックに $c$ が残り続けます。すなわち $u = w_2 \cdots w_{j-1}$ の処理は $c$ より上だけで完結し、$j$ 文字目の直前のスタックはちょうど $c$ 1 個です。準備の観察より、$u$ を空スタックから処理しても拒否せず、処理後は空になります。$|u| < |w|$ なので、帰納法の仮定より $u \in B$ です。

$j$ 文字目では $c$ が $\mathrm{pop}$ され、$\mathcal{A}$ が拒否しなかったので $w_j = \bar{c}$ です。残りの $v = w_{j+1} \cdots w_{|w|}$ の処理は空スタックから始まり、全体が受理されるので空スタックで終わります。$|v| < |w|$ より $v \in B$ です。以上より $w = c\,u\,\bar{c}\,v$ で、生成規則の第 2 条から $c u \bar{c} \in B$、第 3 条から $w \in B$ を得ます。

**計算量.** 各文字につき $\mathrm{push}$ か $\mathrm{pop}$ と $\mathrm{top}$ が高々 1 回ずつで、連結リスト実装ならこれらは最悪 $\Theta(1)$ です（<Ref to="prop-list" /> の 1）。よって全体で $\Theta(|w|)$ です。
</Proof>

<Example id="ex-bracket-trace" title="判定アルゴリズムを走らせる">
$w = \texttt{([])()}$ に対する $\mathcal{A}$ の実行を追います。スタックは左を底として書きます。

| 読んだ文字 | 動作 | 直後のスタック |
|---|---|---|
| $\texttt{(}$ | push | $\texttt{(}$ |
| $\texttt{[}$ | push | $\texttt{([}$ |
| $\texttt{]}$ | pop（$\texttt{[}$ と一致） | $\texttt{(}$ |
| $\texttt{)}$ | pop（$\texttt{(}$ と一致） | 空 |
| $\texttt{(}$ | push | $\texttt{(}$ |
| $\texttt{)}$ | pop（$\texttt{(}$ と一致） | 空 |

読み終えてスタックが空なので受理します。実際 $\texttt{([])} \in B$ かつ $\texttt{()} \in B$ で、生成規則の第 3 条から $w \in B$ です。一方 $w' = \texttt{(]}$ では、2 文字目で $\mathrm{pop}$ した結果が $\texttt{(}$ となり $\texttt{]}$ と種類が違うので拒否されます。$w'' = \texttt{(()}$ では拒否は起きませんが、読み終えたときスタックに $\texttt{(}$ が 1 個残るので拒否されます。実装は次のとおりです。

```python
def is_balanced(w: str) -> bool:
    partner = {")": "(", "]": "["}
    stack = []
    for c in w:
        if c in "([":
            stack.append(c)
        elif c in ")]":
            if not stack or stack.pop() != partner[c]:
                return False
        else:
            raise ValueError(f"unexpected symbol: {c!r}")
    return not stack


print(is_balanced("([])()"))   # True
print(is_balanced("(]"))       # False
print(is_balanced("(()"))      # False
```

最後の `return not stack` が「読み終えたときスタックが空」という受理条件に対応します。この 1 行を忘れると `"((("` を受理してしまいます。
</Example>

この判定は、深さ優先探索や再帰呼び出しの管理と同じ形をしています。「開いたものを、開いた順序の逆に閉じる」構造が現れる場所には、たいていスタックがあります。

## 7. キュー

キューは、最初に入れたものが最初に出てくる（first in, first out, FIFO）型です。窓口の行列と同じ規律で、待ち行列とも呼ばれます。

<Definition id="def-queue" title="キュー">
キューとは、次の操作をもつ抽象データ型である。値の型を $X$、キューの全体を $\mathcal{Q}$ と書く。

- $\mathrm{empty} \in \mathcal{Q}$（空のキュー）
- $\mathrm{enqueue} : \mathcal{Q} \times X \to \mathcal{Q}$（末尾に加える）
- $\mathrm{dequeue} : \mathcal{Q} \to \mathcal{Q}$（先頭を取り除く）
- $\mathrm{front} : \mathcal{Q} \to X$（先頭を読む）
- $\mathrm{isEmpty} : \mathcal{Q} \to \{\mathrm{true}, \mathrm{false}\}$

これらは任意の $Q \in \mathcal{Q}$、$x \in X$ について次の公理を満たす。
$$
\begin{aligned}
&\mathrm{isEmpty}(\mathrm{empty}) = \mathrm{true}, \qquad \mathrm{isEmpty}(\mathrm{enqueue}(Q, x)) = \mathrm{false}, \\[2pt]
&\mathrm{front}(\mathrm{enqueue}(Q, x)) =
\begin{cases}
x & (Q = \mathrm{empty}) \\
\mathrm{front}(Q) & (Q \ne \mathrm{empty})
\end{cases} \\[2pt]
&\mathrm{dequeue}(\mathrm{enqueue}(Q, x)) =
\begin{cases}
\mathrm{empty} & (Q = \mathrm{empty}) \\
\mathrm{enqueue}(\mathrm{dequeue}(Q), x) & (Q \ne \mathrm{empty})
\end{cases}
\end{aligned}
$$
$\mathrm{front}(\mathrm{empty})$ と $\mathrm{dequeue}(\mathrm{empty})$ は定義されない。
</Definition>

<Ref to="def-stack" /> と見比べてください。スタックでは $\mathrm{pop}(\mathrm{push}(S,x)) = S$ と、直前に積んだものがそのまま取れました。キューでは $\mathrm{dequeue}$ が $\mathrm{enqueue}$ をすり抜けて奥へ潜っていきます。この「すり抜け」が FIFO の正体で、公理の右辺に再帰が現れる理由です。

**素朴な配列実装はうまくいきません.** 先頭を常に $A[0]$ に置くと、$\mathrm{enqueue}$ は末尾追加なので償却 $\Theta(1)$ ですが、$\mathrm{dequeue}$ は位置 $0$ の削除であり <Ref to="prop-array" /> の 3 より $\Theta(n)$、$n$ 回で $\Theta(n^2)$ です。原因は先頭を $A[0]$ に固定したことなので、固定をやめれば解決します。

<Proposition id="prop-ring-buffer" title="リングバッファ">
容量 $m$ の配列 $A[0..m-1]$、先頭位置 $h$（$0 \le h \le m-1$）、要素数 $n$（$0 \le n \le m$）を保持し、次のように操作を定める。

- $\mathrm{enqueue}(x)$：$n < m$ のとき $A[(h + n) \bmod m] \leftarrow x$、$n \leftarrow n + 1$。
- $\mathrm{dequeue}()$：$n > 0$ のとき戻り値を $A[h]$ とし、$h \leftarrow (h + 1) \bmod m$、$n \leftarrow n - 1$。
- $\mathrm{front}()$：$n > 0$ のとき $A[h]$ を返す。

このとき、キューの内容を先頭から順に $q_0, q_1, \ldots, q_{n-1}$ とすると、常に $q_i = A[(h + i) \bmod m]$ が成り立ち、<Ref to="def-queue" /> の公理が満たされる。また 3 つの操作はいずれも最悪 $\Theta(1)$ 時間である。
</Proposition>

<Proof of="prop-ring-buffer">
主張の等式 $q_i = A[(h+i) \bmod m]$（$0 \le i \le n-1$）を不変条件として、操作回数に関する帰納法で示します。

初期状態は $n = 0$ なので、条件は空虚に成り立ちます。

$\mathrm{enqueue}(x)$ の場合。新しい内容は $q_0, \ldots, q_{n-1}, x$ で $h$ は変わりません。書き込み先 $(h+n) \bmod m$ が既存の位置 $(h+i) \bmod m$（$0 \le i \le n-1$）と重ならないことを確かめます。$0 \le i < n \le m-1$ より $i$ と $n$ の差は $m$ の倍数になり得ないので、$m$ を法として異なります。したがって既存要素は壊れず、新しい末尾要素は番号 $n$ の要素として等式を満たします。

$\mathrm{dequeue}()$ の場合。戻り値は $A[h] = q_0$ でキューの先頭です。新しい内容 $q_1, \ldots, q_{n-1}$ を改めて $q'_0, \ldots, q'_{n-2}$ と番号づけ、$h' = (h+1) \bmod m$ とすると
$$
q'_i = q_{i+1} = A[(h + i + 1) \bmod m] = A[(h' + i) \bmod m]
$$
となって不変条件が保たれます。

$\mathrm{front}()$ が $q_0$ を返すことは $i = 0$ の場合そのものです。以上より $\mathrm{dequeue}$ と $\mathrm{front}$ はつねに先頭要素に作用し、$\mathrm{enqueue}$ は末尾にのみ加えるので、<Ref to="def-queue" /> の公理が満たされます。計算量は、各操作が定数回の加算・剰余・比較と 1 回の配列アクセス（<Ref to="prop-array" /> の 1 より $\Theta(1)$）からなることから最悪 $\Theta(1)$ です。
</Proof>

<Example id="ex-ring-buffer" title="容量 4 のリングバッファ">
$m = 4$、初期状態 $h = 0$、$n = 0$ から始めます。$A$ の未使用区画を `_` と書きます。

| 操作 | 書き込み先 / 読み出し元 | $A$ | $h$ | $n$ |
|---|---|---|---|---|
| $\mathrm{enqueue}(a)$ | $A[(0+0) \bmod 4] = A[0]$ | `a _ _ _` | 0 | 1 |
| $\mathrm{enqueue}(b)$ | $A[1]$ | `a b _ _` | 0 | 2 |
| $\mathrm{enqueue}(c)$ | $A[2]$ | `a b c _` | 0 | 3 |
| $\mathrm{dequeue}()$ | $A[0] = a$ | `a b c _` | 1 | 2 |
| $\mathrm{enqueue}(d)$ | $A[(1+2) \bmod 4] = A[3]$ | `a b c d` | 1 | 3 |
| $\mathrm{enqueue}(e)$ | $A[(1+3) \bmod 4] = A[0]$ | `e b c d` | 1 | 4 |
| $\mathrm{dequeue}()$ | $A[1] = b$ | `e b c d` | 2 | 3 |

最後の状態でキューの内容は $c, d, e$ であり、不変条件どおり $A[(2+0) \bmod 4] = A[2] = c$、$A[3] = d$、$A[(2+2) \bmod 4] = A[0] = e$ です。$e$ を書き込むときに配列の右端を越えて左端へ回り込む点が「リング」の由来で、要素は一度も移動していません。
</Example>

<Remark id="rem-ring-full" title="満杯と空の区別、そして容量拡張">
$h$ と「末尾の次の位置」$t = (h+n) \bmod m$ だけを保持する実装もありますが、その場合 $n = 0$ と $n = m$ のどちらでも $t = h$ となり、空と満杯が区別できません。回避策は 2 つで、上の <Ref to="prop-ring-buffer" /> のように要素数 $n$ を明示的に持つか、区画を 1 つ常に空けておいて実質容量を $m-1$ とするかです。

満杯になったら容量 $2m$ の配列を確保して先頭から詰め直します。この拡張のコストと頻度は <Ref to="thm-dynamic-array" /> とまったく同じ形なので、$\mathrm{enqueue}$ は償却 $\Theta(1)$ に保たれます。連結リストで先頭と末尾の両方への参照を持つ実装なら、<Ref to="prop-list" /> の 1 より両操作とも最悪 $\Theta(1)$ です。
</Remark>

スタックが深さ優先探索を、キューが幅優先探索を駆動します。どちらも [グラフアルゴリズム](/computer-science/algorithms/graph-algorithms) の中核で、幅優先探索が最短距離を正しく求めることはキューの FIFO 規律から従い（<Ref to="computer-science/algorithms/graph-algorithms#thm-bfs-correctness" />）、深さ優先探索では処理中の頂点がちょうどスタックをなします（<Ref to="computer-science/algorithms/graph-algorithms#lem-dfs-stack" />）。また、配列を「表」として使い添字アクセスの $\Theta(1)$ に全面的に依存するのが [動的計画法](/computer-science/algorithms/dynamic-programming) です（<Ref to="computer-science/algorithms/dynamic-programming#thm-memo-cost" />）。

## 8. ポテンシャル法と 2 本のスタックによるキュー

<Ref to="thm-dynamic-array" /> では総コストを直接数え上げました（集約法）。操作が複数種類あって互いに影響し合うと、この数え上げは難しくなります。そこで使うのがポテンシャル法で、データ構造の「たまった仕事」を実数値の関数で表し、各操作でその増減を見ます。

<Lemma id="lem-potential" title="ポテンシャル法">
データ構造の状態の列 $D_0, D_1, \ldots, D_m$（$D_0$ は初期状態、$D_i$ は $i$ 番目の操作の直後の状態）と、$i$ 番目の操作の実コスト $c_i$ が与えられているとする。状態の集合上の実数値関数 $\Phi$ が
$$
\Phi(D_i) \ge \Phi(D_0) \qquad (i = 0, 1, \ldots, m)
$$
を満たすとする。償却コストを $\hat{c}_i := c_i + \Phi(D_i) - \Phi(D_{i-1})$ で定めると
$$
\sum_{i=1}^{m} c_i = \sum_{i=1}^{m} \hat{c}_i + \Phi(D_0) - \Phi(D_m) \le \sum_{i=1}^{m} \hat{c}_i
$$
が成り立つ。とくに、ある定数 $a$ がすべての $i$ について $\hat{c}_i \le a$ を満たすならば、$m$ 回の操作の総コストは $am$ 以下である。
</Lemma>

<Proof of="lem-potential">
定義から
$$
\sum_{i=1}^{m} \hat{c}_i = \sum_{i=1}^{m} c_i + \sum_{i=1}^{m}\bigl(\Phi(D_i) - \Phi(D_{i-1})\bigr)
$$
です。右辺の第 2 項は望遠鏡和で、隣接する項が打ち消し合って $\Phi(D_m) - \Phi(D_0)$ になります。よって
$$
\sum_{i=1}^{m} \hat{c}_i = \sum_{i=1}^{m} c_i + \Phi(D_m) - \Phi(D_0)
$$
であり、移項すれば等式を得ます。仮定より $\Phi(D_m) \ge \Phi(D_0)$ すなわち $\Phi(D_0) - \Phi(D_m) \le 0$ なので不等式が従います。最後の主張は $\sum \hat{c}_i \le am$ から明らかです。
</Proof>

$\Phi$ は「今の状態が抱えている借金」だと思ってください。安い操作で少しずつ借金を積み、高い操作でまとめて返済します。返済の瞬間は実コストが大きくても $\Phi$ が大きく減るので、償却コストは小さくなります。

<Theorem id="thm-two-stack-queue" title="2 本のスタックによるキュー">
全操作が最悪 $\Theta(1)$ 時間のスタック（例えば <Ref to="prop-list" /> の 1 に基づく連結リスト実装）を 2 本用意し、$\mathrm{in}$、$\mathrm{out}$ と呼ぶ。次のように操作を定める。

- $\mathrm{enqueue}(x)$：$\mathrm{in}$ に $x$ を $\mathrm{push}$ する。
- $\mathrm{dequeue}()$：$\mathrm{out}$ が空ならば、$\mathrm{in}$ が空になるまで「$\mathrm{in}$ から $\mathrm{pop}$ して $\mathrm{out}$ に $\mathrm{push}$」を繰り返す。その後 $\mathrm{out}$ が空ならエラー、そうでなければ $\mathrm{out}$ から $\mathrm{pop}$ して返す。
- $\mathrm{front}()$：同じ移送を行ったうえで $\mathrm{out}$ の $\mathrm{top}$ を返す。

このとき、この実装は <Ref to="def-queue" /> の公理を満たす。さらに、空の状態から始めた任意の $m$ 回の操作列の総コストは $3m$ 以下であり、1 操作あたりの償却計算量は $O(1)$ である。ただし個々の $\mathrm{dequeue}$ の最悪計算量は、そのときの要素数を $n$ として $\Theta(n)$ である。
</Theorem>

<Proof of="thm-two-stack-queue">
**正当性.** キューの内容を先頭から順に $q_0, \ldots, q_{n-1}$ とし、次を不変条件とします。

> ある $r$（$0 \le r \le n$）が存在して、$\mathrm{out}$ を頂上から底へ読むと $q_0, q_1, \ldots, q_{r-1}$ となり、$\mathrm{in}$ を底から頂上へ読むと $q_r, q_{r+1}, \ldots, q_{n-1}$ となる。

初期状態は $n = 0$、両方のスタックが空で、$r = 0$ として成立します。

$\mathrm{enqueue}(x)$ では $\mathrm{in}$ を底から読むと $q_r, \ldots, q_{n-1}, x$ となり、新しいキューの内容は $q_0, \ldots, q_{n-1}, x$ ですから、同じ $r$ で不変条件が保たれます。

移送が起きるのは $\mathrm{out}$ が空、すなわち $r = 0$ のときで、このとき $\mathrm{in}$ を底から読むと $q_0, \ldots, q_{n-1}$ です。$\mathrm{in}$ から $\mathrm{pop}$ される順序は $q_{n-1}, \ldots, q_0$ で、これを順に $\mathrm{out}$ に $\mathrm{push}$ するので、$\mathrm{out}$ を底から読むと $q_{n-1}, \ldots, q_0$、すなわち頂上からは $q_0, \ldots, q_{n-1}$ です。$\mathrm{in}$ は空なので $r = n$ として不変条件が成立します。順序が 2 度反転して元に戻る、というのがこの実装の仕掛けです。

$\mathrm{out}$ が空でないとき（$r \ge 1$）、その頂上は不変条件より $q_0$、すなわちキューの先頭です。よって $\mathrm{front}$ は $q_0$ を返し、$\mathrm{dequeue}$ は $q_0$ を取り除きます。取り除いた後は $\mathrm{out}$ の頂上から $q_1, \ldots, q_{r-1}$ が並ぶので、番号を付け替えれば $r' = r - 1$ で不変条件が保たれます。$n = 0$ のときは両方が空で、移送しても $\mathrm{out}$ は空のままなのでエラーとなり、<Ref to="def-queue" /> が $\mathrm{dequeue}(\mathrm{empty})$ を未定義としていることと整合します。

**償却計算量.** ポテンシャルを
$$
\Phi := 2 \cdot (\mathrm{in} \text{ の要素数})
$$
と定めます。$\Phi \ge 0$ で、初期状態では $\Phi(D_0) = 0$ なので、<Ref to="lem-potential" /> の仮定 $\Phi(D_i) \ge \Phi(D_0)$ が満たされます。コストは 1 回のスタック操作を 1 と数えます（仮定よりこれは最悪 $\Theta(1)$ 時間です）。

- $\mathrm{enqueue}$：実コストは $\mathrm{push}$ 1 回で $c = 1$。$\mathrm{in}$ の要素数が 1 増えるので $\Delta\Phi = 2$。よって $\hat{c} = 1 + 2 = 3$。
- $\mathrm{out}$ が空でないときの $\mathrm{dequeue}$：実コストは $\mathrm{pop}$ 1 回で $c = 1$。$\mathrm{in}$ は変わらないので $\Delta\Phi = 0$。よって $\hat{c} = 1$。
- $\mathrm{out}$ が空で $\mathrm{in}$ に $k \ge 1$ 個あるときの $\mathrm{dequeue}$：移送で $\mathrm{pop}$ が $k$ 回、$\mathrm{push}$ が $k$ 回、その後の $\mathrm{pop}$ が 1 回なので $c = 2k + 1$。$\mathrm{in}$ の要素数が $k$ から $0$ になるので $\Delta\Phi = -2k$。よって $\hat{c} = 2k + 1 - 2k = 1$。
- $\mathrm{front}$：$\mathrm{pop}$ の代わりに $\mathrm{top}$ を読むだけなので、上の 2 つと同じ計算で $\hat{c} = 1$。

いずれの場合も $\hat{c} \le 3$ です。<Ref to="lem-potential" /> より、$m$ 回の操作の総コストは $3m$ 以下であり、1 操作あたりの償却計算量は $O(1)$ です。

**最悪計算量.** $n$ 個すべてが $\mathrm{in}$ に積まれ $\mathrm{out}$ が空の状態での $\mathrm{dequeue}$ は $2n + 1$ 回のスタック操作を行うので $\Theta(n)$ です。償却が $O(1)$ であることと矛盾しません。この高価な $\mathrm{dequeue}$ が起きる前には、$n$ 個の要素を積むために $n$ 回の $\mathrm{enqueue}$ が必要だからです。
</Proof>

<Figure caption="2 本のスタックによるキュー。in から out へ移すときに順序が反転し、最も古い要素が out の頂上に来る。">
<Mermaid code={`flowchart LR
  E["enqueue x は in に push する"] --> I["スタック in（底から c, d, e）"]
  I -->|"out が空のとき in が空になるまで移す"| O["スタック out（頂上から c, d, e）"]
  O --> D["dequeue は out の頂上を pop する"]`} />
</Figure>

<Example id="ex-two-stack-trace" title="2 本のスタックを動かす">
実装と、$\Phi$ の変化を追った実行例を示します。

```python
class TwoStackQueue:
    def __init__(self):
        self._in = []    # 末尾が頂上
        self._out = []   # 末尾が頂上

    def enqueue(self, x):
        self._in.append(x)

    def _transfer(self):
        while self._in:
            self._out.append(self._in.pop())

    def dequeue(self):
        if not self._out:
            self._transfer()
        if not self._out:
            raise IndexError("dequeue from empty queue")
        return self._out.pop()

    def front(self):
        if not self._out:
            self._transfer()
        if not self._out:
            raise IndexError("front of empty queue")
        return self._out[-1]

    def __len__(self):
        return len(self._in) + len(self._out)


q = TwoStackQueue()
for x in "abc":
    q.enqueue(x)
print(q.dequeue(), q.dequeue())   # a b
q.enqueue("d")
print(q.dequeue(), q.dequeue())   # c d
```

各操作の実コスト $c$、ポテンシャル $\Phi = 2\,|\mathrm{in}|$、償却コスト $\hat{c} = c + \Delta\Phi$ は次のようになります。

| 操作 | 直後の $\mathrm{in}$（底から） | 直後の $\mathrm{out}$（頂上から） | $c$ | $\Phi$ | $\hat{c}$ |
|---|---|---|---|---|---|
| 初期状態 | — | — | — | 0 | — |
| $\mathrm{enqueue}(a)$ | $a$ | — | 1 | 2 | 3 |
| $\mathrm{enqueue}(b)$ | $a, b$ | — | 1 | 4 | 3 |
| $\mathrm{enqueue}(c)$ | $a, b, c$ | — | 1 | 6 | 3 |
| $\mathrm{dequeue}() = a$ | — | $b, c$ | 7 | 0 | 1 |
| $\mathrm{dequeue}() = b$ | — | $c$ | 1 | 0 | 1 |
| $\mathrm{enqueue}(d)$ | $d$ | $c$ | 1 | 2 | 3 |
| $\mathrm{dequeue}() = c$ | $d$ | — | 1 | 2 | 1 |
| $\mathrm{dequeue}() = d$ | — | — | 3 | 0 | 1 |

4 行目の $\mathrm{dequeue}$ は実コスト $7$（$\mathrm{pop}$ 3 回、$\mathrm{push}$ 3 回、$\mathrm{pop}$ 1 回）と飛び抜けていますが、$\Phi$ が $6$ から $0$ へ落ちるので償却コストは $1$ です。総実コストは $16$、操作回数は $8$ で、<Ref to="lem-potential" /> の上界 $3 \times 8 = 24$ を下回ります。
</Example>

## 9. 演習

<Exercise id="exr-queue-axiom" difficulty="易">
<Ref to="def-queue" /> の公理だけを使って、次の等式を導いてください。途中でどの公理を使ったかを明記してください。
$$
\mathrm{dequeue}\bigl(\mathrm{enqueue}(\mathrm{enqueue}(\mathrm{empty}, a), b)\bigr) = \mathrm{enqueue}(\mathrm{empty}, b)
$$
また、この結果と $\mathrm{front}$ の公理から、$a$、$b$ の順に入れたキューから 1 つ取り出すと $b$ が残ることを確かめてください。

<Solution>
$Q := \mathrm{enqueue}(\mathrm{empty}, a)$ と置きます。公理 $\mathrm{isEmpty}(\mathrm{enqueue}(Q', x)) = \mathrm{false}$ を $Q' = \mathrm{empty}$、$x = a$ に適用すると $Q \ne \mathrm{empty}$ です。よって $\mathrm{dequeue}$ の公理の第 2 の場合が使えて
$$
\mathrm{dequeue}(\mathrm{enqueue}(Q, b)) = \mathrm{enqueue}(\mathrm{dequeue}(Q), b)
$$
となります。次に $\mathrm{dequeue}(Q) = \mathrm{dequeue}(\mathrm{enqueue}(\mathrm{empty}, a))$ に、同じ公理の第 1 の場合（内側の引数が $\mathrm{empty}$）を適用すると $\mathrm{dequeue}(Q) = \mathrm{empty}$ です。代入して
$$
\mathrm{dequeue}(\mathrm{enqueue}(Q, b)) = \mathrm{enqueue}(\mathrm{empty}, b)
$$
を得ます。

さらに $\mathrm{front}$ の公理の第 1 の場合より $\mathrm{front}(\mathrm{enqueue}(\mathrm{empty}, b)) = b$ です。先に入れた $a$ が先に出ていったので、確かに FIFO です。<Ref to="def-stack" /> の公理で同じ計算をすると $\mathrm{pop}(\mathrm{push}(\mathrm{push}(\mathrm{empty}, a), b)) = \mathrm{push}(\mathrm{empty}, a)$ となり、残るのは $a$ です。公理の違いがそのまま挙動の違いになっています。
</Solution>
</Exercise>

<Exercise id="exr-list-reverse" difficulty="標準">
単方向連結リストを、$\Theta(n)$ 時間・$O(1)$ 追加領域で反転する手続きを書いてください。新しいノードを作らず、既存のノードの $\mathrm{next}$ を書き換えるだけで行うこと。ループ不変条件を述べ、それを使って正当性を示してください。

<Solution>
3 つの変数だけを使います。

```python
def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next     # 先に控えないと next を上書きした瞬間に迷子になる
        cur.next = prev    # 向きを反転
        prev = cur
        cur = nxt
    return prev
```

**不変条件.** 元のリストを $p_0, p_1, \ldots, p_{n-1}$ とします。ループの各反復の開始時点で、ある $k$（$0 \le k \le n$）について次が成り立ちます。

- `prev` は、$p_{k-1}, p_{k-2}, \ldots, p_0$ をこの順に連ねたリストの先頭（$k = 0$ のときは $\mathrm{nil}$）である。
- `cur` は $p_k$（$k = n$ のときは $\mathrm{nil}$）である。
- この 2 本のリストは互いに素で、合わせて元のノード全体をなす。

**初期化.** ループに入る直前は `prev = None`、`cur = head` $= p_0$ なので、$k = 0$ で成立します。

**維持.** 反復開始時に $k$ で成立し、`cur` $= p_k \ne \mathrm{nil}$ とします。`nxt` に $p_{k+1}$（存在しなければ $\mathrm{nil}$）を控えます。`cur.next = prev` により $p_k$ の直後が $p_{k-1}$ になり、`prev` から始まるリストは $p_k, p_{k-1}, \ldots, p_0$ になります。この代入で失われるのは $p_k$ から $p_{k+1}$ への参照だけですが、それは `nxt` に控えてあります。最後に `prev = cur`、`cur = nxt` とすれば、$k+1$ について不変条件が成り立ちます。

**終了.** ループは `cur` が $\mathrm{nil}$ になったとき、すなわち $k = n$ のときに終わります。不変条件より `prev` は $p_{n-1}, \ldots, p_0$ を連ねたリストの先頭で、これは元のリストの反転です。

**計算量.** ループは各ノードにつきちょうど 1 回、合計 $n$ 回まわり、1 回の本体は代入 4 個で定数時間です（<Ref to="prop-list" /> の 1 と同じ理由です）。よって $\Theta(n)$ 時間。追加で使う記憶領域は変数 3 個だけなので $O(1)$ です。

なお `nxt` の退避を省くと、`cur.next = prev` の直後に $p_{k+1}$ へ到達する手段が失われます。<Ref to="prop-list" /> の 2 の証明のとおり、ノードの番地は参照をたどってしか得られないからです。
</Solution>
</Exercise>

<Exercise id="exr-shrink" difficulty="難">
<Ref to="thm-dynamic-array" /> の動的配列に、要素の削除 $\mathrm{pop}$ と、記憶領域を返すための縮小規則を加えます。

1. 「$\mathrm{pop}$ の後、要素数が容量の半分以下になったら容量を半分にする」という規則を採用すると、償却 $O(1)$ が成り立たなくなります。$m$ 回の操作で総コストが $\Theta(m^2)$ になる操作列を具体的に構成してください。
2. 「要素数が容量の $1/4$ を下回ったら容量を半分にする」という規則なら、$\mathrm{push}$ と $\mathrm{pop}$ の償却コストが定数に保たれます。連続する 2 回の容量変更の間に少なくとも何回の操作が必要かを評価して、その理由を説明してください。

<Solution>
**1.** 容量 $c = m_0$、要素数 $n = m_0$（満杯）の状態から始め、$\mathrm{push}$ と $\mathrm{pop}$ を交互に繰り返します。

- $\mathrm{push}$：満杯なので容量が $2m_0$ に拡張され、$m_0$ 個がコピーされます。実行後は $n = m_0 + 1$、$c = 2m_0$。
- $\mathrm{pop}$：実行後 $n = m_0$ となり、$m_0 \le 2m_0/2 = m_0$ なので縮小規則が発動し、容量が $m_0$ に戻って $m_0$ 個がコピーされます。

これで最初の状態に完全に戻るので、以降同じことが繰り返されます。2 回の操作ごとに $2m_0$ 回のコピーが発生するので総コストは $\Theta(m \cdot m_0)$ となり、$m_0 = \Theta(m)$ と取れば $\Theta(m^2)$ です。原因は、拡張の閾値と縮小の閾値が同じ点にあることです。

**2.** 閾値をずらすと、容量変更の直後に境界から遠い場所に着地します。容量変更の直後の状態を見ます。

- 拡張の直後：容量 $c$、要素数 $n = c/2$。
- 縮小の直後：縮小前の容量を $2c$、そのとき要素数は $2c/4 = c/2$ を下回った直後なので $n = c/2$（$1$ 単位の誤差を除く）。容量は $c$。

どちらの場合も $n \approx c/2$ です。次に拡張が起きるには $n$ が $c$ に達する必要があるので $\mathrm{push}$ が少なくとも $c/2$ 回、次に縮小が起きるには $n$ が $c/4$ を下回る必要があるので $\mathrm{pop}$ が少なくとも $c/4$ 回必要です。したがって、連続する 2 回の容量変更の間には少なくとも $c/4$ 回の操作があります。

容量 $c$ の変更にかかるコストは $\Theta(c)$ ですから、これを直前の $c/4$ 回以上の操作に割り振ると 1 回あたり定数です。形式的には、<Ref to="lem-potential" /> のポテンシャルとして
$$
\Phi =
\begin{cases}
2n - c & (n \ge c/2) \\
c/2 - n & (n < c/2)
\end{cases}
$$
を取れば、拡張・縮小の有無による場合分けで償却コストが定数に抑えられることを確かめられます。どちらの式も容量変更の直後（$n = c/2$）で $0$ になり、境界へ近づくほど増える点が要点です。
</Solution>
</Exercise>

## 参考文献

- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, *Introduction to Algorithms*, 4th ed., MIT Press, 2022 — 第 10 章（Elementary Data Structures）に配列・連結リスト・スタック・キューが、第 16 章（Amortized Analysis）に集約法・課金法・ポテンシャル法があります。動的配列（table doubling）の解析も第 16 章です。
- D. E. Knuth, *The Art of Computer Programming, Volume 1: Fundamental Algorithms*, 3rd ed., Addison-Wesley, 1997 — §2.2（Linear Lists）。§2.2.1 がスタック・キュー・デック、§2.2.2 が逐次配置（配列）、§2.2.3 が連結配置（連結リスト）で、この記事の §3 から §7 に対応します。連結リストの歴史的経緯も §2.6 に記述があります。
- A. V. Aho, J. E. Hopcroft, J. D. Ullman, *Data Structures and Algorithms*, Addison-Wesley, 1983 — 第 2 章（Basic Abstract Data Types）。抽象データ型を先に定め、実装を後から与えるという本記事の構成は、この本の流儀に沿っています。
- R. E. Tarjan, "Amortized Computational Complexity", *SIAM Journal on Algebraic and Discrete Methods* 6 (1985), 306–318. [DOI: 10.1137/0606031](https://doi.org/10.1137/0606031) — 償却計算量とポテンシャル法を体系的に定式化した論文です。
- R. Sedgewick, K. Wayne, *Algorithms*, 4th ed., Addison-Wesley, 2011 — §1.3（Bags, Queues, and Stacks）。可変長配列と連結リストの両方でスタック・キューを実装し、実測値を比較しています。
- 石畑清『アルゴリズムとデータ構造』岩波書店（岩波講座 ソフトウェア科学 3）、1989 — 日本語で読める定評ある教科書です。線形リストの各種表現が詳しく扱われています。

## Appendix: 主要言語の標準ライブラリとの対応

この記事で扱ったデータ構造は、主要な言語の標準ライブラリにそのまま入っています。名前から実装が読み取れないことがあるので、対応を挙げておきます。

**動的配列と連結リスト.** C++ の `std::vector`、Java の `ArrayList`、Python の `list` が動的配列です。増加率は実装ごとに違い、Java の `ArrayList` はおよそ $1.5$ 倍、CPython の `list` はおよそ $1.125$ 倍（容量は $0, 4, 8, 16, 25, 35, 46, 58, 72, 88, \ldots$ と増えます）ですが、<Ref to="rem-amortized" /> のとおり $1$ より大きい定数であれば償却 $O(1)$ は保たれます。連結リストは C++ の `std::list`（双方向）と `std::forward_list`（単方向）、Java の `LinkedList`（双方向）です。Python の標準ライブラリに純粋な連結リスト型がないのは、必要になる場面が少ないためで、<Ref to="rem-cache" /> の事情も背景にあります。

**スタックとキュー.** C++ の `std::stack` と `std::queue` は、既存のコンテナに <Ref to="def-stack" />・<Ref to="def-queue" /> のインタフェースだけを見せるアダプタ（既定の土台は `std::deque`）で、抽象データ型と実装の分離がそのまま型に現れています。Java の `ArrayDeque` はリングバッファ（<Ref to="prop-ring-buffer" />）で、スタックにもキューにも使えます。Python ではスタックに `list`（`append` と `pop`）、キューに `collections.deque`（固定長ブロックの双方向連結リストで、両端の追加・削除が最悪 $O(1)$）を使います。`list` を `pop(0)` でキューとして使うと、<Ref to="prop-array" /> の 3 により 1 回あたり $\Theta(n)$、$n$ 回で $\Theta(n^2)$ になります。実務で頻繁に見かける速度低下の原因です。