標準ライブラリ

ここでちょっと問題はひとやすみ
標準ライブラリでスタック、キュー、ベクタ、リストを使う方法が解説されてます

Pythonではどうなるのかな

スタック

C++のSTLにはsize、top、push、pop、emptyといった関数が
含まれている模様
サンプルを見ると、popは削除のみで値を取り出すのはtopを使えってことかな
何ていうんだっけ
関数は副作用なしで値を返すだけ、副作用はコマンドでコマンドは値を返さない、みたいなの

ググったらPythonチュートリアルで早速紹介されてるようだ
ということは逆に言うとStackクラスみたいなのはないってことだなきっと

スタックの一番上に要素を追加するには append() を使います。スタックの一番上から要素を取り出すには pop() をインデクスを指定せずに使います。
5.1.1. リストをスタックとして使う

あれ
考えてみたらappendって末尾にくっつけるやつだよな
普通のリストだとO(n)になってしまうよな
Pythonでリストって言ってるやつは双方向リストなのかな

・・・
ただの配列だった
そうだったか
確認してなかった

そりゃ末尾に追加だな

わざわざクラスで書くとこうかな

class Stack():

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

    def top(self):
        return self.s[-1]

    def size(self):
        return len(self.s)

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

    def pop(self):
        return self.s.pop()

    def empty(self):
        return len(self.s) == 0

もう一度調べてみたら双方向キューを実装したcollections.dequeっていうのがある
といってもスタックとして使うだけなら配列で十分

from collections import dequeして
self.s = []をself.s = deque()にするだけで動くことは動く

キュー

キューのクラスは書いたけどcollections.dequeで書き直してみよう
append、appendleft、pop、popleftとあって先頭も末尾も
自由にできるけど、左か右か、どっちを先頭とするべきかな

$ python3
>>> from collections import deque
>>> q = deque([1,2,3])
>>> q
deque([1, 2, 3])
>>> q.popleft()
1

appendとpopleftを使うのが素直そうな感じ

class Queue():

    def __init__(self):
        self.q = deque()

    def size(self):
        return len(self.q)

    def front(self):
        return self.q[0]

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

    def pop(self):
        return self.q.popleft()

    def empty(self):
        return len(self.q) == 0