両端キュー (循環バッファ/ランダムアクセス$O(1)$)
(DataStructure/misc/ArrayDeque.py)

• View this file on GitHub
• Last update: 2021-02-04 17:47:04+09:00

概要

ランダムアクセスが $O(1)$ で可能な両端キュー。

使い方

ArrayDeque()
空の両端キューを構築する。計算量 $O(1)$

• __len__() -> int
  両端キューの大きさを返す。計算量 $O(1)$

• __iter__() -> Iterator[Any]
  先頭のイテレータオブジェクトを返す。計算量 $O(1)$

• __getitem__(i: int) -> Any
i 番目の要素を返す。計算量 $O(1)$

• __setitem__(i: int, val: Any) -> None
i 番目の要素を val に変更する。計算量 $O(1)$

• append(val: Any) -> None
  両端キューの末尾に要素 val を追加する。計算量 $\mathrm{amortized}\ O(1)$

• appendleft(val: Any) -> None
  両端キューの先頭に要素 val を追加する。計算量 $\mathrm{amortized}\ O(1)$

• pop() -> Any
  両端キューの末尾要素を削除し、その要素を返す。計算量 $\mathrm{amortized}\ O(1)$

• popleft() -> Any
  両端キューの先頭要素を削除し、その要素を返す。計算量 $\mathrm{amortized}\ O(1)$

• clear() -> None
  両端キューを空にする。計算量 $O(1)$

Verified with

• TestCase/AOJ/ITP2_1_B.ArrayDeque.test.py

Code

class ArrayDeque:
    def __init__(self):
        self.arr_size = 1
        self.array = [0]
        self.n = 0
        self.head = 0
        self.tail = 0

    def __len__(self):
        return self.n

    def __iter__(self):
        self._i = 0
        return self

    def __next__(self):
        if self._i >= self.n:
            raise StopIteration
        self._i += 1
        return self.array[(self.head + self._i - 1) & (self.arr_size - 1)]

    def __getitem__(self, i):
        if i < 0:
            i = self.n + i
        if not (0 <= i < self.n):
            raise IndexError
        return self.array[(self.head + i) & (self.arr_size - 1)]

    def __setitem__(self, i, val):
        if i < 0:
            i = self.n + i
        if not (0 <= i < self.n):
            raise IndexError
        self.array[(self.head + i) & (self.arr_size - 1)] = val

    def _resize(self):
        new_arr = [0] * ((self.n + 1) << 1)
        for i in range(self.n):
            new_arr[i] = self.array[(self.head + i) & (self.arr_size - 1)]
        self.array = new_arr
        self.arr_size = (self.n + 1) << 1
        self.head = 0
        self.tail = self.n

    def append(self, val):
        if self.n == self.arr_size - 1:
            self._resize()
        self.array[self.tail] = val
        self.tail = (self.tail + 1) & (self.arr_size - 1)
        self.n += 1

    def appendleft(self, val):
        if self.n == self.arr_size - 1:
            self._resize()
        self.head = (self.head - 1) & (self.arr_size - 1)
        self.array[self.head] = val
        self.n += 1

    def pop(self):
        if self.n == 0:
            raise IndexError
        self.tail = (self.tail - 1) & (self.arr_size - 1)
        val = self.array[self.tail]
        self.n -= 1
        if self.arr_size >= 4 * self.n + 2:
            self._resize()
        return val

    def popleft(self):
        if self.n == 0:
            raise IndexError
        val = self.array[self.head]
        self.head = (self.head + 1) & (self.arr_size - 1)
        self.n -= 1
        if self.arr_size >= 4 * self.n + 2:
            self._resize()
        return val

    def clear(self):
        self.__init__()

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