Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較）

# はじめに
本記事は、主に競技プログラミングにおける話です。

Python において、スタックとキューを実装するには複数の方法があります。

- スタック(stack)
    - list を使う（`append()`, `pop()`）
    - collections.deque を使う（`append()`, `pop()`）
- キュー(queue)
    - list を使う（`append()`, `pop(0)`）
    - collections.deque を使う(`append()`, `popleft()`)
    - queue.Queue を使う（`put()`, `get()`）

さて、この中で一体どれを使うのが最適でしょうか。
今回はそれを速度面に注目して調べます。


# 計測方法
各データ構造に対して、要素の追加と取り出しを10回、100回、1000回、10000回、100000回行います。

どのコードも、以下の import 部分は省略しています。

```python:import部分
from collections import deque
from queue import Queue
import time
```

## スタック

```python:listを使用
# stack(list)
stack_list_append = []
stack_list_pop = []
for i in range(1, 6):
    start = time.time()

    stack_list = []
    for j in range(10 ** i):
        stack_list.append(j)

    stack_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_list.pop()

    stack_list_pop.append(time.time() - start)
```

```python:dequeを使用
# stack(deque)
stack_deque_append = []
stack_deque_pop = []
for i in range(1, 6):
    start = time.time()

    stack_deque = deque([])
    for j in range(10 ** i):
        stack_deque.append(j)

    stack_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_deque.pop()

    stack_deque_pop.append(time.time() - start)
```

## キュー

```python:listを使用
# queue(list)
queue_list_append = []
queue_list_pop = []
for i in range(1, 6):
    start = time.time()

    queue_list = []
    for j in range(10 ** i):
        queue_list.append(j)

    queue_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_list.pop(0)

    queue_list_pop.append(time.time() - start)
```

```python:dequeを使用
# queue(deque)
queue_deque_append = []
queue_deque_pop = []
for i in range(1, 6):
    start = time.time()

    queue_deque = deque([])
    for j in range(10 ** i):
        queue_deque.append(j)

    queue_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_deque.popleft()

    queue_deque_pop.append(time.time() - start)
```

```python:Queueを使用
# queue(Queue)
queue_Queue_append = []
queue_Queue_pop = []

for i in range(1, 6):
    start = time.time()

    queue_Queue = Queue()
    for j in range(10 ** i):
        queue_Queue.put(j)

    queue_Queue_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_Queue.get()

    queue_Queue_pop.append(time.time() - start)
```


# 計測結果
計測結果をグラフにしたところ、次のようになりました。

<img width="742" alt="スクリーンショット 2020-03-01 16.35.38.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365958/77d76381-a563-6073-a4bf-d341cba5e666.png">

左上から順に見ていきましょう。

## スタックの結果
### 要素の追加
左上のグラフです。
<img width="371" alt="スクリーンショット 2020-03-01 16.39.29.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365958/417a2430-0448-f1a2-304e-ba9f7c7691dd.png">
若干 deque の方が速いですが、ほぼ同じです。

### 要素の取り出し
右上のグラフです。
<img width="370" alt="スクリーンショット 2020-03-01 16.40.06.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365958/a6757c20-f69e-211d-1f98-692ed1b29c0b.png">
こちらも若干 deque の方が速いですが、ほぼ同じです。

## キューの結果
### 要素の追加
左下のグラフです。
<img width="375" alt="スクリーンショット 2020-03-01 16.40.40.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365958/88d56694-1c81-b214-adf0-82cdc8ae3618.png">
要素数が多くなると、 Queue が他に比べて10倍以上遅いです。

### 要素の取り出し
右下のグラフです。
<img width="351" alt="スクリーンショット 2020-03-01 16.40.48.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365958/db613d72-7e90-9516-42bb-7aecda5b2379.png">
Queue は要素の追加の時と同じですが、list が明らかにやばいです。最速の deque と比べると100倍以上遅くなっています。


# 結論
スタックもキューも、collections.deque を使うのが最適です。

せっかくなので、簡単な使い方も書いておきます。

## スタック
```python
from collections import deque

s = deque([])
s.append(1)  # [1]
s.append(2)  # [1, 2]
s.append(3)  # [1, 2, 3]
s.pop()      # 一番上から取り除く [1, 2, 3] -> [1, 2]
s.pop()      # [1, 2] -> [1]
s.pop()      # [1] -> []
```

## キュー
スタックでは取り除くときに pop だったのが、キューだと popleft になっているだけです。

```python
from collections import deque

q = deque([])
q.append(1)  # [1]
q.append(2)  # [1, 2]
q.append(3)  # [1, 2, 3]
q.popleft()  # 一番下から取り除く [1, 2, 3] -> [2, 3]
q.popleft()  # [2, 3] -> [3]
q.popleft()  # [3] -> []
```