データ構造とそれに対する操作の複雑さ次第だとは思います。
WordのUNDOなんか凄いことやっていると思いますよ。

UNDOってインパクトそんなにも大きかったのですね。
わたしの今まで作ってきたアプリのUNDOなんてログビューに下から順に詰め込んでいって、UNDO押されたら一番上のログから取り出してただけです。
こんなのってやっぱりダメなんでしょうね…