#Pythonで学ぶアルゴリズム< スタックとキュー >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第18弾としてスタックとキューを扱う．今回も並べ替えのカテゴリとしているが，スタックとキューは次回の並べ替え（ヒープソート）との比較のため学ぶのであり，決して並べ替えアルゴリズムということではないことを述べておく．

スタック（stack）

データの格納されたリストにおいて，末尾(最後に入れたもの)から取り出すこと．
スタック(stack)は積み上げるという意味で，その名前の通りである．積荷におけるイメージとリストでのイメージの図を次に示す．

キュー（queue）

データの格納されたリストにおいて，先頭(先に入れたもの)から取り出すこと．
キュー(queue)は「列」という意味で，その名前の通り入れたものは反対から出てくるというイメージである．先ほどと同様に積荷におけるイメージとリストでのイメージの図を次に示す．

また，図に示すように，キューにおいてはデータの格納，取り出しに対して，エンキューとデキューという名称がつけられている．

スタックの実装

以下にスタックのコードとその出力を示す．

コード

stack.py

"""
2021/01/12
@Yuya Shimizu

スタック(stack)
"""

List = []

List.append(3)         #stackに[3]を追加
List.append(5)         #stackに[5]を追加
List.append(2)         #stackに[2]を追加

print(List)

temp = List.pop()     #stackから取り出し
print(f"\n取り出し: {temp}\n")
print(List)

temp = List.pop()     #stackから取り出し
print(f"\n取り出し: {temp}\n")
print(List)

List.append(4)         #stackに[4]を追加
print(f"\n追加: 4\n")
print(List)

temp = List.pop()     #stackから取り出し
print(f"\n取り出し: {temp}\n")
print(List)

出力

[3, 5, 2]

取り出し: 2

[3, 5]

取り出し: 5

[3]

追加: 4

[3, 4]

取り出し: 4

[3]

キューの実装

以下にキューのコードとその出力を示す．

コード

queue_program.py

"""
2021/01/12
@Yuya Shimizu

キュー(queue)
"""
import queue

q = queue.Queue()

q.put(3)                #キューに[3]を追加
q.put(5)                #キューに[5]を追加
q.put(2)                #キューに[2]を追加

print(q.queue)

temp = q.get()      #キューから取り出し
print(f"\nデキュー: {temp}\n")
print(q.queue)

temp = q.get()      #キューから取り出し
print(f"\nデキュー: {temp}\n")
print(q.queue)

q.put(4)                #キューに[4]を追加
print(f"\nエンキュー: 4\n")
print(q.queue)

temp = q.get()      #キューから取り出し
print(f"\nデキュー: {temp}\n")
print(q.queue)

出力

deque([3, 5, 2])

デキュー: 3

deque([5, 2])

デキュー: 5

deque([2])

エンキュー: 4

deque([2, 4])

デキュー: 2

deque([4])

キューに関しては，Pythonにqueueというモジュールが用意されており，Queueクラスを使うことで，putメソッドすなわちエンキュー，getメソッドすなわちデキューを実装することができる．注意としては，queue.pyという名前ではqueueモジュールが読み込めないことである．

感想

今回はスタックとキューについて学んだ．直接，並べ替えを学んだわけではないが，データの取り扱いについて，新たなキューというものを知った．また，スタックにおいては，pop()を再び扱い，pop()の使い方にも慣れて気がする．次回のヒープソートで，今回学んだことよりも優れた方法が学べるということで楽しみである．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　増井敏克　著　　翔泳社