問題 No.2826
テキストエディタの編集作業において、ユーザーが実行した直前の操作を取り消す「アンドゥ（元に戻す）」機能の内部処理において、操作履歴を順に積み上げて管理するのに最も適したデータ構造はどれか。
【正解の解説】
最後に追加された操作履歴から順に取り出される後入れ先出し（LIFO）の方式
これは狭い筒の中に本を1冊ずつ上へ積み上げていき、片付けるときには一番上（最後に入れたもの）から順に取り出す「本の積み重ね」のような仕組みです。テキストエディタで文字を入力したとき、直近の操作ほどすぐ取り消したいという私たちの自然な感覚と完全に一致するため、アンドゥ機能の内部処理にはこのデータ構造が選ばれています。
スポンサーリンク
【その他の選択肢の解説】
最初に追加された操作履歴から順に取り出される先入れ先出し（FIFO）の方式
こちらは遊園地のアトラクション待ちの列のように、最初に入った人から順番に処理されるキュー（Queue）と呼ばれる別のデータ構造です。もしこれをアンドゥ機能に使ってしまうと、直前の操作ではなく一番最初に行った古い操作から順に取り消されてしまい、アプリとして全く使い物にならなくなってしまいます。
登録された操作履歴がランダムな順序で自由にアクセス可能なハッシュの方式
キーを指定して一瞬でデータを探し出すのには非常に向いていますが、操作を行った「順番」を保持することができません。そのため、時系列で「直前の操作に戻る」というアンドゥ機能の要件を満たすことができず、順番の管理が必要な場面では全く不向きなデータ構造となります。
任意の操作履歴を双方向から自由に変更できるポインタ参照型の方式
データの途中の要素を自由に追加・削除するのには優れていますが、操作履歴を順序よく積み上げて効率よく出し入れするというスタック本来のシンプルな目的に対しては、構造が複雑すぎてオーバーヘッドが大きくなってしまいます。順番に特化したスタックを使う方が圧倒的にシンプルで高速に動作します。