スタック (push/pop) を実装する
取り消しは、必ず直前の操作から
エディタで文字を打ち、色を変え、画像を貼った。ここで取り消しを押したら、消えるのは画像です。もう一度押せば色、その次が文字。最後にやったことから順に戻る のであって、最初にやったことから戻ることはありません。ブラウザの戻るボタンも、関数の呼び出し履歴も、全部この順番です。
この「最後に入れたものが最初に出てくる」並べ方を スタック と呼びます。皿を積み上げて、上から取っていく形と同じです。
末尾を「上」にすると、積むのも取るのも一瞬
配列の 末尾 をスタックの上と決めてしまえば、積む操作も取る操作も、末尾だけを触れば済みます。
Python
history = []
history.append("太字にした")
history.append("画像を貼った")
print(history[-1]) # 画像を貼った 次に取り消されるのはこれ
history.pop()
print(history) # ['太字にした']append で末尾に積み、pop で末尾を外します。JavaScript の配列も push と pop で同じことができます。どちらも他の要素には一切触らないので、中身が何件あっても一定の時間で終わります。
先頭を「上」にすると、急に遅くなる
同じことを配列の 先頭 でやると、話が変わります。先頭に 1 つ入れるには、既に入っている全部を 1 つずつ後ろへずらす必要があります。取り出すときも同じで、残り全部を 1 つ前へ詰め直します。
Python
history = list(range(100000))
history.insert(0, "新しい操作") # 10 万個をずらす積む、取り出すという同じ意味の操作なのに、末尾なら O(1)、先頭なら O(n) です。どちらを上と決めるかだけで、性能が丸ごと変わります。迷ったら末尾にしてください。
何も積んでいないのに、取り出そうとする
取り消しを押し続けると、いつか戻るものが無くなります。そのときにどうするかを決めていないと、素直に落ちます。
Python
history = []
history.pop()
# IndexError: pop from empty listJavaScript の pop は落ちずに undefined を返しますが、そのまま次の処理へ流れていくぶん、原因の分かりにくいバグになりがちです。空かどうかを先に確かめて、空なら何もしない、と決めておくのが安全です。
もう 1 つ。渡された配列をそのまま積み下ろしすると、呼び出した側の配列まで書き換わります。手元で作業したいなら、最初にコピーを取ってください。
要件
- operations の各要素は ['push', N] (N は整数) か ['pop'] のいずれか
- 空スタックに対する pop は何もせず無視する
- 戻り値は最終的なスタック状態を表す整数配列 (底 → top の順)
入出力例
stackOps([1], [["push",5],["push",3],["pop"],["push",9]]) → [1,5,9]
stackOps([1,2], [["push",3],["pop"],["pop"]]) → [1]
stackOps([1,2], [["pop"],["pop"],["pop"],["pop"]]) → []
stackOps([7,8,9], []) → [7,8,9]
stackOps([0], [["push",1],["push",2],["push",3]]) → [0,1,2,3]
stackOps([10,20], [["pop"],["pop"],["pop"],["push",42]]) → [42]ヒント
