Pythonでstackとqueueを使う

stack

listを使えば良い。

1
2
3
4
stack = []
stack.append(1) #  push　O(1)  
stack.append(2) # push　O(1)
stack.pop() #  pop　O(1)

listは末尾への挿入・削除はO(1)で処理できるが、任意の位置に対する挿入・削除はO(n)であることに注意が必要。つまり、stackとしてリストが与えられていた場合、順番を逆順にする等してstackの底をリストの先頭にすると良いだろう。

queue

dequeは両端キューとして実装されているが、これをqueueとして使えば良い。

1
2
3
4
5
from collections import deque
queue = deque()
queue.append(1) #  enqueue　O(1)
queue.append(2) #  enqueue　O(1)
queue.popleft() #  dequeue　O(1)

余談

dequeue自体はもちろんstackとしても利用可能である。ちなみにPythonのdequeは双方向連結リストで実装されているため、ランダムアクセス（端以外の要素へのアクセス）はO(n)となってしまう。純粋なstackとしての用途であれば、listとdequeどちらを用いても良いが、それらの特性を理解しておくと良いと思う。

参考

https://docs.python.org/3.7/library/collections.html#collections.deque