永続的なデータ構造とは、構造が変更されるたびに、この構造の以前のすべてのバージョンへのアクセスが維持されるような構造を指します。 当然のことながら、オプションの1つ（もちろん最善ではありません）として、変更ごとに構造全体の完全なコピーを検討できます。 これは、メモリとランタイムの両方で非常に非効率的ですが、この方法は、たとえば、より複雑な構造組織をテストする段階で適用できます。 それにもかかわらず、そのような実装にはほとんど意味がないため、さらに、とりわけ、さまざまな構造に対してより最適な実装を検索します。
今日は、永続スタックの実装とアプリケーションを見ていきます。 後続の記事では、永続キュー、デカルトツリー、およびセグメントのツリーについて説明し、これらの永続構造を使用して解決するいくつかのタスクを分析します。
永続スタック
問題の声明。 最初は、番号0の空のスタックが1つあり、n（スタックの数）は最初は1です。 次の操作を実装する必要があります。
- push（i、x）-要素xをスタック番号iに追加します。 結果のスタックはn + 1になります。
- pop（i）-スタック番号iの最後の要素を返し、「スタックからそれを捨てる」。 結果のスタックはn + 1になります。
簡単に言うと、各操作の後、古いスタックを損なうことなく「新しい」スタックを作成する必要があります。
解決策。 この問題の最も簡単で明白な解決策は、説明されているプロセスをシミュレートすることです。 各操作でのスタックの正直なコピー。 明らかに、これは最も効果的なソリューションではありません。 1つの操作の複雑さはO（n）であり、必要なメモリの量はO（n * n）です。
最適なソリューションのアイデアに近づくために、頂点がその要素であるグラフの形でスタックを想像してみてください。次に、各頂点（テールを除く）からスタックの前の要素にエッジを置きます。 「1」、「2」、「3」、「4」、「5」が順番に追加されたスタックの例：
スタック全体を復元するには、スタックの「ヘッド」を知るだけで十分です。 スタックのn個のコピーではなく、n個の最初の要素を保存してみましょう。 プッシュおよびポップ操作は次のようになります。
- push（x、i）-値xを持つ新しい要素を作成します。これは、スタック上の前の要素として番号iを持つ要素を参照します。
- pop（i）-番号iの要素に保存されている値を返し、その前の要素をコピーします。
わかりやすくするために、アルゴリズムの例を考えてみましょう。 最初に空のスタックを1つ用意します。 便宜上、空のスタックでマークされた「ヘッド」として保存します。
次に、プッシュ（1、5）を実行します。 1を参照して、値5の新しい頂点が作成されます。
push（2、10）とpush（1、6）を同じ方法でやってみましょう：
明らかに、4つのスタックはすべて正しく構築され、簡単に復元できます。 操作pop（2）とpop（3）を順番に実行してみましょう。
pop（2）は5を返し、最初の頂点をコピーします。 結果の5番目のスタックは空です。
pop（3）は10を返し、2番目の頂点をコピーします。6番目のスタックを取得します。
明らかに、1つの要求がO（1）に対して機能し、合計O（n）のメモリが必要です。これは喜ばしいことです。
アプリケーション。 私が覚えている限りでは、永続スタックを使用して解決できるいくつかの問題に遭遇しました。 いくつかの原始性のために、これらの構造はあまりにも難しいとは考えられないが、それでも存在することは明らかです。 例：
N人の子供が交互に雪だるまを作っています。 最初の子供は、半径R1の1つのボールから雪だるまを作りました。 後続の各子は前の子と同じ雪だるまを作りましたが、少し考えた後、彼は半径Riのボールを追加するか、既存の上部のボールを破壊しました。 すべての雪だるまが厳密に正の数のボールを持っていることが保証されています。 入力はNで、最後のボールを破壊したか、自分のボールを追加したか（それぞれの半径も表示されます）についての各子に関する情報です。 以下は、1からNの範囲のKの数字のセットです。それぞれについて、この数字で雪だるまのボールのシーケンスを導き出す必要があります。 NとKの制限は100万です。
永続スタックの実装に関するセクションを読んだ後、この問題の解決策が明らかになります。
おわりに 今日は、永続スタックなどのデータ構造とその効果的な実装について検討しました。 これは、他の永続構造とその実装の原則をさらに理解するという観点から有用でした。 既に述べたように、次の記事では、永続キュー、デカルトツリー、セグメントツリーなど、より複雑な構造を検討する予定です。 より複雑な構造は、それらの問題を実装して解決するためにより複雑で興味深いものです。 ご清聴ありがとうございました。