データ構造

Contents

データ構造#

データ構造と計算量#

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

TimeComplexity - Python Wiki

listは検索（"hoge" in List）するとき\(O(n)\)（線形探索）
setは検索するとき\(O(1)\)
listでsortすると、要素数の分だけ計算量かかる
heapq（ヒープキュー、優先度つきキュー）で保持すると、最小値や最大値しか取り出せないが、頻繁に最小値や最大値を参照するときはlistで保持して毎回sortするより効率がいい（ABC141D - Powerful Discount Tickets）

特集！知らないと損をする計算量の話 - Qiita

スタック#

スタック（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()

キュー#

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

操作：

enqueue(x): キューの末尾に要素xを追加する
dequeue(): キューの先頭から要素を取り出す

from queue import Queue

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

連結リスト#

#TODO