Pythonで理解する蟻本「2-1 スタック」(p.31)
この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-1 スタック」(p.31)
のコードをPythonで書き直したものとなっています。
PythonとC++の違い
C++と違い、Pythonにはスタックというデータ構造はありません。
Pythonではlist(リスト)やdeque(両端キュー)のメソッドを利用することで、スタックとして使うことができます。
またC++においては、popはコンテナの末尾側の要素を削除するだけで、返り値はありません。
一方でPythonにおいては、popはコンテナの末尾側の要素を削除し、その値を返します(返り値がある)。
そのため、蟻本ではスタックの末尾側の要素を出力した後にその値を削除していますが、この記事のコードでは末尾側の要素を削除する際に値を変数に受け取り、その値を出力しています。
(蟻本のコードは「出力→値の削除」の順番になっているが、この記事のコードでは「値の削除→出力」の順番になっている。)
スタックのコード
listを使ったコード
s = [] # リストを用意する s.append(1) # [] → [1] s.append(2) # [1] → [1,2] s.append(3) # [1,2] → [1,2,3] x = s.pop() # 一番上から取り除いてxに代入する [1,2,3] → [1,2] print(x) # 3 x = s.pop() # [1,2] → [1] print(x) # 2 x = s.pop() # [1] → [] print(x) # 1
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.pop() # 一番上から取り除いてxに代入する [1,2,3] → [1,2] print(x) # 3 x = s.pop() # [1,2] → [1] print(x) # 2 x = s.pop() # [1] → [] print(x) # 1