Persistent stack
(Mylib/DataStructure/Stack/persistent_stack.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Code

#pragma once
#include <iostream>
#include <vector>

namespace haar_lib {
  template <typename T>
  struct persistent_stack {
  protected:
    struct node {
      T value;
      node *next = nullptr;
    };

    node *root_;

    persistent_stack(node *root) : root_(root) {}

  public:
    persistent_stack() : root_(nullptr) {}

    bool empty() const {
      return not root_;
    }

    const T &top() const {
      return root_->value;
    }

    persistent_stack push(const T &value) const {
      node *t = new node({value, root_});
      return persistent_stack(t);
    }

    persistent_stack pop() const {
      node *t = root_->next;
      return persistent_stack(t);
    }

    std::vector<T> data() const {
      std::vector<T> ret;
      node *t = root_;
      while (t) {
        ret.push_back(t->value);
        t = t->next;
      }

      return ret;
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/DataStructure/Stack/persistent_stack.cpp"
#include <iostream>
#include <vector>

namespace haar_lib {
  template <typename T>
  struct persistent_stack {
  protected:
    struct node {
      T value;
      node *next = nullptr;
    };

    node *root_;

    persistent_stack(node *root) : root_(root) {}

  public:
    persistent_stack() : root_(nullptr) {}

    bool empty() const {
      return not root_;
    }

    const T &top() const {
      return root_->value;
    }

    persistent_stack push(const T &value) const {
      node *t = new node({value, root_});
      return persistent_stack(t);
    }

    persistent_stack pop() const {
      node *t = root_->next;
      return persistent_stack(t);
    }

    std::vector<T> data() const {
      std::vector<T> ret;
      node *t = root_;
      while (t) {
        ret.push_back(t->value);
        t = t->next;
      }

      return ret;
    }
  };
}  // namespace haar_lib

Back to top page