Persistent Stack (永続スタック)
(lib/data_structure/persistent_stack.hpp)

• View this file on GitHub
• Last update: 2024-11-15 16:27:00+09:00
• Include: #include "lib/data_structure/persistent_stack.hpp"

Code

#pragma once

/**
 * @brief Persistent Stack (永続スタック)
 */

template<typename T>
struct PersistentStack{
    T val;
    PersistentStack *next = nullptr;
    int exist = 0;

    PersistentStack(const T &_val, PersistentStack *_next) : val(_val), next(_next){
        exist = _next->exist + 1;
    }

    PersistentStack(){
    }

    int size() const {
        return exist;
    }

    bool empty() const {
        return size() == 0;
    }

    T top() const {
        return val;
    }

    PersistentStack *pop() const {
        return next;
    }

    PersistentStack *push(const T &x){
        return new PersistentStack(x, this);
    }
};

#line 2 "lib/data_structure/persistent_stack.hpp"

/**
 * @brief Persistent Stack (永続スタック)
 */

template<typename T>
struct PersistentStack{
    T val;
    PersistentStack *next = nullptr;
    int exist = 0;

    PersistentStack(const T &_val, PersistentStack *_next) : val(_val), next(_next){
        exist = _next->exist + 1;
    }

    PersistentStack(){
    }

    int size() const {
        return exist;
    }

    bool empty() const {
        return size() == 0;
    }

    T top() const {
        return val;
    }

    PersistentStack *pop() const {
        return next;
    }

    PersistentStack *push(const T &x){
        return new PersistentStack(x, this);
    }
};

Back to top page