データ構造

データ構造#

データ構造と計算量#

なぜデータ構造を学ぶのか？ → 一つの実用的な理由は、計算量を大幅に削減できる場合があるから

例

  • listは検索（"hoge" in List）するとき\(O(n)\)（線形探索）

  • setは検索するとき\(O(1)\)

  • listでsortすると、要素数の分だけ計算量かかる

  • heapq（ヒープキュー、優先度つきキュー）で保持すると、最小値や最大値しか取り出せないが、頻繁に最小値や最大値を参照するときはlistで保持して毎回sortするより効率がいい（ABC141D - Powerful Discount Tickets）

参考

スタック#

スタック（stack） はデータの中で最後に入ったものが最初に取り出される 後入れ先出し（Last In First Out: LIFO） のデータ構造

操作：

  • push(x): スタックに要素xを追加する

  • pop(): スタックの最後の要素を取り出す

class Stack:

    def __init__(self):
        self.data = []

    def push(self, x):
        self.data.append(x)

    def pop(self):
        return self.data.pop(-1)


s = Stack()
s.push(1)
s.push(2)
s.pop()

2

キュー#

キュー（Queue） はデータの中で最初に入ったものが最初に取り出される、 先入れ先出し（First In First Out: FIFO） のデータ構造

操作：

  • enqueue(x): キューの末尾に要素xを追加する

  • dequeue(): キューの先頭から要素を取り出す

from queue import Queue

q = Queue()
q.put(1)
q.put(2)
q.get()

1

連結リスト#

#TODO
Contents