リスト・キュー・スタック
データ構造ごとの順序と計算量をバーの動きで比べます。
スタック
0 / 0 手順
速さ 速さ
回/秒
n = 要素数 * 償却
| 取り出す順 | 1 要素のメモリ | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| – | – | – | – | – | 後入れ先出し | 値のみ | ||||
| – | – | – | – | – | 先入れ先出し | 値のみ | ||||
| – | – | – | – | 両端から選択 | 値のみ | |||||
| 位置を選択 | 値のみ | |||||||||
| 位置を選択 | 値＋ポインタ 1 個 | |||||||||
| 位置を選択 | 値＋ポインタ 2 個 | |||||||||
| – | – | – | – | 先入れ先出し | 値のみ |
バー
要素数 要素数
個
実行順
追加する位置
取り出す位置
| 実行 | 計算量 | n = 32 |
|---|
- 読み書き
- 0回
- 読み取り
- 0
- 書き込み
- 0
- 現在の要素数
- 0
- 最大の要素数
- 0
- 平均の待ち回数
- –
- 最長の待ち回数
- –
- 追加順の維持率
- –
- 取り出す順
- 後入れ先出し（LIFO）
- 1 要素のメモリ
- 値のみ
- 利用例
- 操作の取り消し（Undo）・関数呼び出し・括弧の対応チェック
- 取り出す順
- 先入れ先出し（FIFO）
- 1 要素のメモリ
- 値のみ
- 利用例
- 印刷キュー・幅優先探索・通信バッファ
- 取り出す順
- 両端から選択
- 1 要素のメモリ
- 値のみ
- 利用例
- ワークスティーリング・スライディングウィンドウ
- 取り出す順
- 位置を選択
- 1 要素のメモリ
- 値のみ（予備領域あり）
- 利用例
- 表・画像・音声のデータ
- 取り出す順
- 位置を選択
- 1 要素のメモリ
- 値＋ポインタ 1 個
- 利用例
- ハッシュ表のチェイン法・空き領域の管理
- 取り出す順
- 位置を選択
- 1 要素のメモリ
- 値＋ポインタ 2 個
- 利用例
- LRU キャッシュ・テキストエディタ
- 取り出す順
- 先入れ先出し（FIFO）
- 1 要素のメモリ
- 値のみ（容量は固定）
- 利用例
- 音声の入出力・シリアル通信・ログの保持
音量 音量
dB
動作原理と式
スタックとキュー
- スタック: 同じ端で追加と取り出しを行う。最後に追加したバーが最初に出る [1]
- キュー: 一方の端で追加し、反対の端から取り出す。最初に追加したバーが最初に出る [1]
- 両端キュー: 両方の端で追加と取り出しを行う [1]
この 3 つは追加と取り出しの位置を決めたもので、メモリ上の並べ方は決めていません。配列でもリストでも実装できます [2]。
配列とリスト
- 配列: 連続した領域に並べる。n 番目の位置は計算で求まる。途中に追加すると後ろのバーをすべてずらす
- 片方向リスト: 各要素が次の要素の位置を持つ。ポインタのつなぎ替えだけで追加できるが、n 番目へは先頭からたどる
- 双方向リスト: 前の要素の位置も持つ。末尾を削除するときに 1 つ前をたどらなくてよい
- リングバッファ: 配列の両端をつないで輪として使う。バーをずらさず、先頭と末尾の位置だけを進める [1]
記号: は先頭の位置、 は容量です。
計算量
要素数 が増えたときに、1 回の操作の読み書きがどう増えるかを表します。 は要素数によらず一定で、 は要素数に比例します [2]。「–」はその操作がないことを表します。
| 先頭に追加 | 末尾に追加 | 先頭を削除 | 末尾を削除 | 途中に追加 | 途中を削除 | n 番目の読み取り | 値の探索 | |
|---|---|---|---|---|---|---|---|---|
| スタック | – | O(1) | – | O(1) | – | – | O(1) | – |
| キュー | – | O(1) | O(1) | – | – | – | O(1) | – |
| 両端キュー | O(1) | O(1) | O(1) | O(1) | – | – | – | – |
| 配列 | O(n) | 償却 O(1) | O(n) | O(1) | O(n) | O(n) | O(1) | O(n) |
| 片方向リスト | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 双方向リスト | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) |
| リングバッファ | O(1) | O(1) | O(1) | – | – | – | O(1) | – |
配列の再確保
配列が満杯になると、2 倍の容量の領域を確保してすべての要素をコピーします。この 1 回は要素数に比例します。ただし容量が倍々に増えるので、末尾への追加を 回続けても、コピーする要素数の合計は 未満に収まります。1 回あたりは一定なので、償却 と書きます [2]。
記号: は最後にコピーした要素数で、 より小さい値です。
同じ計算量でも速さは違う
先頭から順に読むだけなら、配列もリストも です。ただし CPU はメモリをキャッシュラインという単位で読むので、連続した配列では続きの要素がすでにキャッシュにあります。要素が散らばったリストではその効果が小さく、実際の時間は長くなりがちです [3]。
音
音の高さはバーの高さで決めます。 はバーの値（1〜1000）です。
出典
- スタック・キュー・両端キュー（2.2.1）、順次割り当て（2.2.2）、連結割り当て（2.2.3）D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997, Sections 2.2.1–2.2.3
- 配列によるスタックとキュー（10.1）、連結リスト（10.2）、動的テーブルの償却計算量（16.4）T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Sections 10.1, 10.2, 16.4
- キャッシュとメモリを読む順序による速さの違いU. Drepper, What Every Programmer Should Know About Memory, Red Hat, 2007
このツールで決めたこと
- 読み書きの回数は、値の読み書きとポインタの書き込みを数える
- 片方向リストの書き込みは追加 2 回、削除 1 回
- 双方向リストの書き込みは追加 4 回、削除 2 回
- リストの先頭と末尾の位置の更新は数えない
- スタック・キュー・両端キューは実装を決めず、追加と取り出しをそれぞれ 1 回と数える
- キューのバーが詰まって見えるのは図の表現で、回数には数えない
- 配列の容量の初期値は 4。削除しても縮めない
- リングバッファの容量は要素数＋4 で固定。満杯のときは追加できない
- 待ち回数は、追加してから取り出すまでに実行した操作の回数
- 追加順の維持率は、続けて取り出した 2 本のうち追加順を保っている組の割合
- 一覧の表から操作を選ぶと、要素数の 2/3 を追加した状態から始める
- 値の探索は末尾の要素を探す場合を数える