クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-1 キュー」(p.32)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-1 キュー」(p.32)
のコードをPythonで書き直したものとなっています。

PythonC++の違い

スタックとは異なり、キューはPythonにも存在します。

一方でlist(リスト)やdeque(両端キュー)のメソッドを利用して、キューとして使うこともできます。


またC++においては、popはコンテナの先頭側の要素を削除するだけで、返り値はありません

一方でPythonにおいては、popはコンテナの先頭側の要素を削除し、その値を返します(返り値がある)。

そのため、蟻本ではスタックの先頭側の要素を出力した後にその値を削除していますが、この記事のコードでは先頭側の要素を削除する際に値を変数に受け取り、その値を出力しています。

(蟻本のコードは「出力→値の削除」の順番になっているが、この記事のコードでは「値の削除→出力」の順番になっている。)


キューのコード

Queue(キュー)を使ったコード

from queue import Queue

que = Queue()    # キューを用意する
que.put(1)       # [] → [1]
que.put(2)       # [1] → [1,2]
que.put(3)       # [1,2] → [1,2,3]
x = que.get()    # 一番下から取り除いてxに代入する [1,2,3] → [2,3]
print(x)         # 1
x = que.get()    # [2,3] → [3]
print(x)         # 2
x = que.get()    # [3] → []
print(x)         # 3

list(リスト)を使ったコード

s = []          # リストを用意する
s.append(1)     # [] → [1]
s.append(2)     # [1] → [1,2]
s.append(3)     # [1,2] → [1,2,3]
x = s.pop(0)    # 一番下から取り除いてxに代入する [1,2,3] → [2,3]
print(x)        # 1
x = s.pop(0)    # [2,3] → [3]
print(x)        # 2
x = s.pop(0)    # [3] → []
print(x)        # 3

deque(両端キュー)を使ったコード

from collections import deque

s = deque()        #両端キューを用意する
s.append(1)        # [] → [1]
s.append(2)        # [1] → [1,2]
s.append(3)        # [1,2] → [1,2,3]
x = s.popleft()    # 一番下から取り除いてxに代入する [1,2,3] → [2,3]
print(x)           # 1
x = s.popleft()    # [2,3] → [3]
print(x)           # 2
x = s.popleft()    # [3] → []
print(x)           # 3

どれを使えばよい?

Queue、list、dequeを使って同じ処理をするコードを書いてみましたが、速度の点で言えばdequeの方が圧倒的に速いです。

なので、キューを使いたいときにはdequeを利用することをお勧めします。

どのくらい速度が違うのかは、sabaさんがQiita記事で詳しく説明されているので、興味のある方は一度読んでみるとよいでしょう。

qiita.com