Pythonで理解する蟻本「2-1 キュー」(p.32)
この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-1 キュー」(p.32)
のコードをPythonで書き直したものとなっています。
PythonとC++の違い
スタックとは異なり、キューは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