データ構造-2：スタックとキュー
この記事は、chatGPT o1が書いています。
データ構造の2回目です。
リンク先のnotebookで動作確認できます。ぜひ、動かしてみてください。
※イラストもchatGPTに描いてもらったけど、スタックとキューを表現できているかどうかは微妙。
スタックとキューを徹底解説！
初心者でも分かる Python の基本データ構造
プログラミングの中でよく出てくる「スタック（Stack）」と「キュー（Queue）」。実はこれらは、データの入れ方・出し方を決めるときに使う、とても大事な考え方なんです。
スタック：後入れ先出し (LIFO)
最後に入れたものを、最初に取り出す
キュー：先入れ先出し (FIFO)
最初に入れたものを、最初に取り出す
「いきなり LIFO とか FIFO とか何？」と思った方も、心配しなくて大丈夫！ 身近な例と一緒にコードを見ながら、1つ1つ理解していきましょう。
1. スタック（Stack）とは
1.1 スタックの身近な例
イメージとしては、「積み重ねられたお皿」を想像してください。上に新しいお皿を重ねていき、取り出すときも上にあるお皿から取るはずですよね。
後入れ先出し（LIFO）
新しく追加したものが「一番上」に積まれ、取り出すときは「一番上」から先に出す。
1.2 Python でスタックを実装してみよう
実際に Python でクラスとして作ってみましょう。以下のコードでは、リストの append() と pop() を使うと「末尾に追加」「末尾から削除」が簡単にできます。これがスタックの「上に積む」「上から取り出す」動きとピッタリ一致するのです。
class Stack:
def __init__(self, max_size=100000):
"""
スタックを初期化する。
max_size: スタックの最大サイズを指定。
"""
self.max_size = max_size
self.stack = [] # スタックのデータを格納するリスト
def is_empty(self):
""" スタックが空かどうかを判定する """
return len(self.stack) == 0
def is_full(self):
""" スタックが満杯かどうかを判定する """
return len(self.stack) == self.max_size
def push(self, x):
""" スタックに要素を追加する """
if self.is_full():
print("error: stack is full.")
return
self.stack.append(x) # リストの末尾に要素を追加
def pop(self):
""" スタックの最上位の要素を取り出す """
if self.is_empty():
print("error: stack is empty.")
return None
return self.stack.pop() # リストの末尾の要素を取り出す
# スタックの動作確認
if __name__ == "__main__":
stack = Stack() # スタックを作成
stack.push(3) # スタックに3を追加 {}→{3}
stack.push(5) # スタックに5を追加 {3}→{3, 5}
stack.push(7) # スタックに7を追加 {3, 5}→{3, 5, 7}
print(stack.pop()) # 7 を取り出す → スタックは {3, 5} に
print(stack.pop()) # 5 を取り出す → スタックは {3} に
stack.push(9) # スタックに9を追加 → {3, 9}
1.3 コードのポイント
push()
スタックがいっぱい (is_full()) ならエラー表示
まだ余裕があれば list.append(x) で末尾に追加
pop()
スタックが空 (is_empty()) ならエラー表示
そうでなければ、末尾 (list.pop()) の要素を取り出す
お皿を重ねるみたいに、「あとから積んだものが先に出てくる」動作を実現しています。
2. キュー（Queue）とは
2.1 キューの身近な例
例えるなら「行列に並ぶ人の列」です。列に並んだ順で処理されていきます。
先入れ先出し（FIFO）
最初に入れた要素が、先に取り出される。
たとえば、スーパーのレジ待ちでは先に並んでいた人が先に会計を済ませますよね。後ろから割り込むことは（普通は）ありません。
2.2 Python でキューを実装してみよう
2.2.1 collections.deque を使った実装
Python には、キューの操作を効率的に行える「deque（デック）」という便利なデータ型が標準で用意されています。先頭から取り出す操作が非常に高速で、キューを作るなら基本的にはこちらを使うのがおすすめです。
from collections import deque
class Queue:
def __init__(self, max_size=100000):
""" キューを初期化する """
self.max_size = max_size
self.queue = deque()
def is_empty(self):
""" キューが空かどうかを判定する """
return len(self.queue) == 0
def is_full(self):
""" キューが満杯かどうかを判定する """
return len(self.queue) >= self.max_size
def enqueue(self, x):
""" キューに要素を追加する """
if self.is_full():
print("error: queue is full.")
return
self.queue.append(x) # 末尾に追加
def dequeue(self):
""" キューから要素を取り出す """
if self.is_empty():
print("error: queue is empty.")
return -1
return self.queue.popleft() # 先頭から取り出す
# 使用例
q = Queue()
q.enqueue(3) # キューに3を追加
q.enqueue(5) # キューに5を追加
q.enqueue(7) # キューに7を追加
print(q.dequeue()) # 3を出力（先に入れた3が先に出る）
print(q.dequeue()) # 5を出力
q.enqueue(9) # キューに9を追加
ポイント
enqueue のときは append(x) → 末尾に追加
dequeue のときは popleft() → 先頭から取り出し
キューが空かどうかを is_empty()、満杯かどうかを is_full() でチェック
2.2.2 リストを使った実装
「自分で 0 番目から取り出すコードを書いてみたい！」という学習目的であれば、リストを使ったキュー実装も勉強になります。ただし先頭 (index=0) から取り出す場合、その度に要素を詰め直すため、要素数が多いと処理速度が落ちる点は注意しましょう。
class Queue:
def __init__(self, max_size=100000):
""" キューを初期化する """
self.queue = [] # リストを使ってキューを管理
self.max_size = max_size
def is_empty(self):
""" キューが空かどうかを判定する """
return len(self.queue) == 0
def is_full(self):
""" キューが満杯かどうかを判定する """
return len(self.queue) >= self.max_size
def enqueue(self, x):
""" キューに要素を追加する """
if self.is_full():
print("error: queue is full.")
return
self.queue.append(x) # リストの末尾に追加
def dequeue(self):
""" キューから要素を取り出す """
if self.is_empty():
print("error: queue is empty.")
return -1
return self.queue.pop(0) # リストの先頭を取り出す
# 使用例
q = Queue()
q.enqueue(3) # キューに3を追加
q.enqueue(5) # キューに5を追加
q.enqueue(7) # キューに7を追加
print(q.dequeue()) # 3を出力
print(q.dequeue()) # 5を出力
q.enqueue(9) # キューに9を追加
3. スタックとキューの違いを整理しよう
スタック（Stack）
後入れ先出し (LIFO)
例：
皿を積み重ねる
戻るボタンの履歴（一番新しいページから戻る）
関数コールスタック（プログラムが関数を呼び出すときに、呼び出し元の情報を上に積む）
キュー（Queue）
先入れ先出し (FIFO)
例：
レジ待ちの行列
プリンターの印刷待ちタスク
メッセージやイベントを順番に処理するシステム
2 つのデータ構造は、仕事やプログラミングのあらゆる場面で頻繁に登場します。どちらが適しているかは、「最後に入れた要素を先に処理するのか？ それとも 最初に入れた要素を先に処理するのか？」の違いで判断するとよいでしょう。
4. まとめ
スタックとキューは、データを「どんな順序で」取り出すかを管理する仕組み。
スタック (LIFO): 最後に入れた要素が最初に出てくる
キュー (FIFO): 最初に入れた要素が最初に出てくる
Python での実装は、スタックはリストの append() + pop()、キューは主に collections.deque を使うと楽ちん。
リストでキューを実装する方法も知っておくと「内部ではこう動いているのか！」という学習になる。
スタックとキューの考え方は、これから先、アルゴリズムやデータ構造をもっと勉強する際の「土台」となります。どちらも使いどころが多いので、ぜひこの機会にしっかり押さえておきましょう！
5. 次に挑戦してみるなら…
応用のデータ構造
リスト、連結リスト、二分木 (Binary Tree)、グラフ (Graph) など、より複雑なデータ構造にステップアップ
アルゴリズム
幅優先探索 (BFS) や深さ優先探索 (DFS) で、キューやスタックがどのように使われるか学んでみる
実践例
ゲームプログラミングでイベント処理の順序管理
Web アプリでのユーザ操作履歴管理
ちょっとずつステップアップしていくと、プログラミングがもっと面白く、もっと役立つものになっていきますよ。まずは今回のコードをコピーして、実際に手元の Python で動かしてみてください。学びは「動かしてナンボ」です！
もしエラーが出たり、分からないことがあったら、気軽に調べたり、誰かに質問してみましょう。それでは、快適なスタック＆キューライフをお楽しみください！
最後まで読んでくださり、ありがとうございました！
これを機に、スタックとキューの理解をしっかり固めていただければ幸いです。今後のプログラミング学習にきっと役立ちますので、ぜひ活用してみてくださいね。
補足：print文で動作過程を可視化
スタック（Stack）の実装例
class Stack:
def __init__(self, max_size=100000):
"""
リストを使ってスタックを初期化する
"""
self.max_size = max_size
self.stack = []
def is_empty(self):
"""スタックが空かどうかを判定"""
return len(self.stack) == 0
def is_full(self):
"""スタックが満杯かどうかを判定"""
return len(self.stack) >= self.max_size
def push(self, x):
"""スタックに要素を追加する (後入れ先出し: LIFO)"""
if self.is_full():
print("error: stack is full.")
return
self.stack.append(x)
print(f"[PUSH] {x} をスタックに追加 → 現在のスタック: {self.stack}")
def pop(self):
"""スタックの最上位要素を取り出す"""
if self.is_empty():
print("error: stack is empty.")
return None
popped_item = self.stack.pop()
print(f"[POP] {popped_item} を取り出した → 現在のスタック: {self.stack}")
return popped_item
# 動作確認用コード
if __name__ == "__main__":
stack = Stack() # スタックのインスタンスを作成
stack.push(3) # スタックに3を追加
stack.push(5) # スタックに5を追加
stack.push(7) # スタックに7を追加
stack.pop() # 一番上（最後に入れた7）を取り出す
stack.pop() # 次に上にある（最後に入れた5）を取り出す
stack.push(9) # スタックに9を追加
解説（最小限）
push() で要素を追加するたびに、print() で「何を追加したのか」「現在のスタックがどう変化したか」が分かるように表示しています。
pop() で要素を取り出すたびに、取り出した後のスタックの状態を表示しています。
スタックは「後入れ先出し（LIFO）」なので、最後に追加したものを先に取り出します。
キュー（Queue）の実装例
class Queue:
def __init__(self, max_size=100000):
"""
リストを使ってキューを初期化する
"""
self.queue = []
self.max_size = max_size
def is_empty(self):
"""キューが空かどうかを判定"""
return len(self.queue) == 0
def is_full(self):
"""キューが満杯かどうかを判定"""
return len(self.queue) >= self.max_size
def enqueue(self, x):
"""キューに要素を追加する (先入れ先出し: FIFO)"""
if self.is_full():
print("error: queue is full.")
return
self.queue.append(x)
print(f"[ENQUEUE] {x} をキューに追加 → 現在のキュー: {self.queue}")
def dequeue(self):
"""キューの先頭から要素を取り出す"""
if self.is_empty():
print("error: queue is empty.")
return None
front_item = self.queue.pop(0)
print(f"[DEQUEUE] {front_item} を取り出した → 現在のキュー: {self.queue}")
return front_item
# 動作確認用コード
if __name__ == "__main__":
q = Queue()
q.enqueue(3) # キューに3を追加
q.enqueue(5) # キューに5を追加
q.enqueue(7) # キューに7を追加
q.dequeue() # 先に入れた3が先に取り出される
q.dequeue() # 次に先頭にあった5を取り出す
q.enqueue(9) # キューに9を追加
解説（最小限）
enqueue() で要素を末尾に追加するとき、キューの中身を print() で確認できるようにしています。
dequeue() で先頭の要素を取り出したら、取り出した要素とキューの新しい状態を表示するので、「先に入れたものが先に出る（FIFO）」様子がよく分かります。
まとめ
スタックは後入れ先出し (LIFO)、キューは先入れ先出し (FIFO) の構造をとります。
上記のコードでは、操作するたびに print() で内部状態を表示するため、「何が起こっているのか」を一目瞭然で確認できます。
初学者の方は、このコードを実行しながら、どのタイミングでどの要素が追加され、どの要素が取り出されるのかをぜひ追いかけてみてください。きっと理解が深まるはずです！