スタック (push/pop) を実装する

取り消しは、必ず直前の操作から

エディタで文字を打ち、色を変え、画像を貼った。取り消しを押すと消えるのは画像です。もう一度押せば色、その次が文字。最後にやったことから順に戻ります。ブラウザの戻る操作や、関数の呼び出しから戻る順序にも同じ考え方が現れます。

最後に入れたものが最初に出る入れ物をスタックと呼びます。皿を積み、上から取る形です。英語では LIFO といい、後入れ先出しという意味です。追加を push、取り出しを pop と呼びます。

配列の末尾を「上」にする

配列の末尾を上と決めると、追加も取り出しも同じ端を触ります。Python の append は末尾への追加、pop は末尾の取り出しです。

history = []
history.append("太字にした")
history.append("画像を貼った")
print(history[-1])   # 画像を貼った
history.pop()
print(history)       # ['太字にした']

添字の -1 は末尾を指します。末尾を見るだけでは要素は消えません。pop は要素を取り除き、その値を返す操作です。JavaScript の配列でも push と pop で同じ順序になります。

配列の先頭で出し入れすると、残りの件数に比例する O(n) の処理になります。末尾の取り出しは O(1)、追加は容量を広げる回もありますが、多数の追加を平均すると O(1) です。この平均の考え方を償却と呼びます。

空のときの取り決めも必要

取り消しを押し続けると、戻す操作がなくなります。空の配列に Python の pop を使うとエラーになり、JavaScript では undefined が返ります。取り消しボタンを無効にするなど、空のときの振る舞いも決めます。

元の配列を直接出し入れすると、その配列の中身も変わります。履歴を残して別の結果を調べたい場面では、コピーを使うかどうかも確認します。

例題で確かめる

履歴に操作番号を積みます。左が底、右が上です。空から 4、8、12 を積み、1つ取り出し、16 を積んで、もう1つ取り出します。

取り出した順は12、16で、残るのは [4, 8] です。次に取り消すなら8が出ます。最初の4が先に出ることはありません。