永続 Queue (Banker's Queue)
(DataStructure/misc/BankersQueue.py)

• View this file on GitHub
• Last update: 2021-06-27 18:25:48+09:00

概要

Queue を永続化したデータ構造。

使い方

BankersQueue()
空の Banker’s Queue を構築する。計算量 $O(1)$

• front() -> Any
  Banker’s Queue の先頭の要素を返す。計算量 $O(1)$

• push(val: Any) -> BankersQueue
  末尾に要素 val を追加した Banker’s Queue を返す。計算量 $\mathrm{amortized} O(1)$

• pop() -> BankersQueue
  先頭の要素を削除した Banker’s Queue を返す。計算量 $\mathrm{amortized} O(1)$

参考

銀行家の Queue (37zigen さん)

Verified with

• TestCase/LibraryChecker/persistent_queue.test.py

Code

class LinkedList:

    class LazyConcatLinkedList:
        def __init__(self, left, right):
            self.l = left
            self.r = right

        def evaluate(self):
            l = self.l.pop()
            return LinkedList.concat(l, self.r)

    class LazyReverseLinkedList:
        def __init__(self, ll):
            self.head = ll.head
            self.tail = ll.tail

        def evaluate(self):
            head, tail = self.head, self.tail
            ret = LinkedList.push(None, head)
            while tail is not None:
                head, tail = tail.head, tail.tail
                ret = LinkedList.push(ret, head)
            return ret

    def __init__(self, head=None, tail=None):
        self.head = head
        self.tail = tail

    def top(self):
        return self.head

    def pop(self):
        if self.tail is not None:
            self.tail = self.tail.evaluate()
        return self.tail

    def evaluate(self):
        return self

    @classmethod
    def push(cls, ll, head):
        return LinkedList(head, ll)

    @classmethod
    def reverse(cls, ll):
        return cls.LazyReverseLinkedList(ll)

    @classmethod
    def concat(cls, ll_left, ll_right):
        if ll_left is None:
            return ll_right.evaluate()
        return LinkedList(ll_left.head,
                          cls.LazyConcatLinkedList(ll_left, ll_right))


class BankersQueue:
    def __init__(self, f=None, r=None, fsize=0, rsize=0):
        self.f = f
        self.r = r
        self.fsize = fsize
        self.rsize = rsize

    def _normalize(self):
        if self.fsize >= self.rsize:
            return self
        else:
            lazy_rotate = LinkedList.concat(self.f, LinkedList.reverse(self.r))
            return BankersQueue(lazy_rotate,
                                None,
                                self.fsize + self.rsize,
                                0)

    def front(self):
        return self.f.top()

    def push(self, val):
        return BankersQueue(self.f,
                            LinkedList.push(self.r, val),
                            self.fsize,
                            self.rsize + 1)._normalize()

    def pop(self):
        return BankersQueue(self.f.pop(),
                            self.r,
                            self.fsize - 1,
                            self.rsize)._normalize()

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