永続スタック (DataStructure/persistent_stack.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-16 19:41:27+09:00
• Include: #include "DataStructure/persistent_stack.hpp"

永続スタック

永続スタックは、永続データ構造の一種で、変更の履歴だけを持つことでデータ自体のサイズを小さく保ちながら stack の操作を実現できます。このデータ構造は、最新の変更だけをコピーするので過去の状態を効率的に保存することが可能です。

参考

• あなたの庭に永続データ構造を飾りませんか？
• Persistent Stack - AtCoder Heuristic Contest Memo

コンストラクタ

PersistentStack<T> ps

• 型 T を要素に持つ空のスタックを作成します。

計算量

• $O(1)$

push

void ps.push(const T &v)

要素 v をスタックに追加します。

計算量

• $O(1)$

pop

void ps.pop()

スタックの先頭の要素を削除します。

制約

• スタックが空でないこと。

計算量

• $O(1)$

top

T ps.top()

スタックの先頭の要素を返します。

制約

• スタックが空でないこと。

計算量

• $O(1)$

empty

bool ps.empty()

スタックが空かどうかを返します。

計算量

• $O(1)$

size

int ps.size()

スタックに含まれる要素の数を返します。

計算量

• $O(1)$

extract_values

vector<T> ps.extract_values()

スタックのすべての要素を順番に取り出し、vector に格納して返します。
スタックの順番は保持され、最初に追加した要素が最初に、最後に追加した要素が最後に配置されます。

計算量

• $O(n)$

Verified with

• test/DataStructure/persistent_stack/abc273-e.cpp

Code

#include <bits/stdc++.h>

using namespace std;

template <class T>
class PersistentStack
{
protected:
    struct History
    {
        T v;
        shared_ptr<History> previous;
        int size = 1;
        History(const T &v, shared_ptr<History> previous) : v(v), previous(previous)
        {
            if (previous == nullptr)
            {
                size = 1;
                return;
            }

            size = previous->size + 1;
        }
    };

private:
    shared_ptr<History> latest;

public:
    PersistentStack() : latest(nullptr)
    {
    }

    PersistentStack(shared_ptr<History> latest) : latest(latest)
    {
    }

    bool empty() const
    {
        return latest == nullptr;
    }

    T top() const
    {
        assert(!empty());
        return latest->v;
    }

    void push(const T &v)
    {
        latest = make_shared<History>(v, latest);
    }

    void pop()
    {
        assert(!empty());
        latest = latest->previous;
    }

    int size() const
    {
        if (empty())
        {
            return 0;
        }

        return latest->size;
    }

    vector<T> extract_values()
    {
        vector<T> result;
        auto now = PersistentStack(latest);
        while (!now.empty())
        {
            result.push_back(now.top());
            now.pop();
        }

        reverse(result.begin(), result.end());

        return result;
    }
};

#line 1 "DataStructure/persistent_stack.hpp"
#include <bits/stdc++.h>

using namespace std;

template <class T>
class PersistentStack
{
protected:
    struct History
    {
        T v;
        shared_ptr<History> previous;
        int size = 1;
        History(const T &v, shared_ptr<History> previous) : v(v), previous(previous)
        {
            if (previous == nullptr)
            {
                size = 1;
                return;
            }

            size = previous->size + 1;
        }
    };

private:
    shared_ptr<History> latest;

public:
    PersistentStack() : latest(nullptr)
    {
    }

    PersistentStack(shared_ptr<History> latest) : latest(latest)
    {
    }

    bool empty() const
    {
        return latest == nullptr;
    }

    T top() const
    {
        assert(!empty());
        return latest->v;
    }

    void push(const T &v)
    {
        latest = make_shared<History>(v, latest);
    }

    void pop()
    {
        assert(!empty());
        latest = latest->previous;
    }

    int size() const
    {
        if (empty())
        {
            return 0;
        }

        return latest->size;
    }

    vector<T> extract_values()
    {
        vector<T> result;
        auto now = PersistentStack(latest);
        while (!now.empty())
        {
            result.push_back(now.top());
            now.pop();
        }

        reverse(result.begin(), result.end());

        return result;
    }
};

Back to top page