Persistent Stack
(data-structure/persistent_stack.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Include: #include "data-structure/persistent_stack.hpp"

Description

永続スタックは，過去のバージョンを保持するスタックである．

空間計算量: $O(m)$, $m$ は変更の数

Operations

• bool empty()
  • 時間計算量: $O(1)$
• T top()
  • 先頭の要素を返す
  • 時間計算量: $O(1)$
• PersistentStack push(T val)
  • val を先頭に追加する
  • 時間計算量: $O(1)$
• PersistentStack pop()
  • 先頭の要素を削除する
  • 時間計算量: $O(1)$

Reference

• ゼロから作る永続データ構造

Code

#pragma once
#include <memory>

template <typename T>
class PersistentStack {
   public:
    PersistentStack() = default;

    T top() const { return last->val; }

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

    PersistentStack push(const T& val) const {
        return PersistentStack(std::make_shared<Node>(val, last));
    }

    PersistentStack pop() const { return PersistentStack(last->prev); }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr prev;
        Node(T val, node_ptr prev) : val(val), prev(prev) {}
    };

    node_ptr last;

    explicit PersistentStack(node_ptr last) : last(last) {}
};

#line 2 "data-structure/persistent_stack.hpp"
#include <memory>

template <typename T>
class PersistentStack {
   public:
    PersistentStack() = default;

    T top() const { return last->val; }

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

    PersistentStack push(const T& val) const {
        return PersistentStack(std::make_shared<Node>(val, last));
    }

    PersistentStack pop() const { return PersistentStack(last->prev); }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr prev;
        Node(T val, node_ptr prev) : val(val), prev(prev) {}
    };

    node_ptr last;

    explicit PersistentStack(node_ptr last) : last(last) {}
};

Back to top page