競プロでちょいハマったPythonのスタックとキューについて

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

### 前置き

<a href="http://www.smartbowwow.com/2018/05/atcoder.html">
この前の記事</a>で書いたように、先日競技プログラミングを始めました。
僕はC++はかけないので、とりあえず一番手に馴染んでいるPythonを使って解いています。

競技プログラミングでは基本のデータ構造のスタックとキューについて、とりあえずリストを使って書いてみたら少しハマってしまいました。
Pythonには便利な機能がたくさんありますが、内部のアルゴリズムまで把握して使わないと計算時間を大きく消費してしまいますね。

### ハマった内容

Pythonではリストがスタックとキューの代わりになります。
制限時間がそんなにタイトじゃなければこれでいいはず。

```python:stack.py
stack=[1,2,3,4]

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

```

```python:queue.py
queue=[1,2,3,4]

#enqueue
queue.append(5) #queue=[1,2,3,4,5]
#dequeue
queue.pop(0) #queue=[1,2,3,4]

```

このうち、`append(5)`と`pop()`はO(1)だけれど、`pop(0)`はO(n)(先頭の要素を削除した後、配列を一つずつ前にずらしている)
なので、計算量が大きくなってしまいます。

このように、pythonのリストを使ってスタックとキューを作ると、スタックは問題ないが、キューの方は遅くなってしまう恐れがあります。

おとなしく、`collections.deque`をつかうと安全。

```python:deque.py
from collections import deque

L=deque([1,2,3,4])
#push,enqueue
L.append(5)#[1,2,3,4,5]
#pop
L.pop()#[1,2,3,4]
#dequeue
L.popleft()#[2,3,4]
```

### まとめ

* 内部のアルゴリズムも理解して正しく使おう！
* 不安な時はライブラリを使おう！

ぐぐりらにっき