永続 Stack
(DataStructure/misc/PersistentStack.py)

• View this file on GitHub
• Last update: 2021-02-02 21:07:06+09:00

概要

Stack を永続化したデータ構造。一応、経路復元などに使える。

使い方

PersistentStack(val=None, prev=None)
空の Persistent Stack を構築する。計算量 $O(1)$

• top() -> Any
  Persistent Stack の末尾の要素を返す。計算量 $O(1)$

• push(val: Any) -> PersistentStack
  末尾に要素 val を追加した Persistent Stack を返す。計算量 $O(1)$

• pop() -> PersistentStack
  末尾の要素を削除した Persistent Stack を返す。計算量 $O(1)$`

Verified with

• TestCase/unittest/PersistentStack.unittest.test.py

Code

class PersistentStack:
    def __init__(self, val=None, prev=None):
        self.val = val
        self.prev = prev

    def top(self):
        return self.val

    def push(self, x):
        return PersistentStack(x, self)

    def pop(self):
        return self.prev

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page