スタックとキューの実装

毎日の「あとで元に戻したい」「来た順番に処理したい」という場面、身に覚えはありませんか？ブラウザの戻るボタンや、プリンターの印刷待ち行列など、実はその裏側で活躍しているのがスタック（Stack）とキュー（Queue）という基本データ構造です。

ここではPythonでの実装方法をていねいに解説しながら、LIFOやFIFOといった基礎用語、効率的に動かすためのコツまでをやさしく学んでいきます。 「名前は聞いたことがあるけど、どう使えば良いかは曖昧…」という方でも大丈夫。動作イメージからコード、よくあるつまずきまで、読みやすさ重視で進めます。

スタックの実装を理解しよう

まずは、最後に入れたものが最初に出るLIFO（Last In, First Out）です。 イメージとしては、お皿を重ねていく台所のシーンを思い浮かべてください。上に置いた皿から順に取り出しますよね。それがまさにスタックの動きです。アプリの「元に戻す（Undo）」機能でも同じ発想が使われています。

スタックの基本操作

具体的な操作の名前がわかるとコードも読みやすくなります。ここで出てくる用語は、ほぼすべての言語・教材で共通です。

• push(item): 要素を上に積む（追加）
• pop(): 一番上の要素を取り出す（削除）
• peek(): 一番上の要素をのぞき見る（削除しない）
• is_empty(): 空かどうかを調べる

Pythonでスタックを実装する

まずは実際に手を動かしてみましょう。Pythonのリストは末尾への追加と削除が高速なため、スタックの実装にぴったりです。

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# 使ってみよう
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())   # 3（最後に入れた3が先に出る）
print(stack.peek())  # 2（中身は見えるが取り出さない）
print(stack.is_empty())  # False

このStackクラスは、とてもシンプルな仕組みで動いています。

まず、コンストラクタの中で空のリストを用意し、そこに要素を積み重ねていきます。pushではリストの末尾にappendするだけなので処理は高速です。

取り出しのpopは、空のときに取り出そうとすると危険なので、最初にis_emptyで確認し、空でなければ末尾から取り出します。のぞき見のpeekは、末尾の要素にインデックス-1でアクセスするだけ。sizeは単純にリストの長さを返しています。Pythonのリストは末尾への追加・削除が平均O(1)でとても効率的なので、スタック用途に向いています。

キューの実装を自分のものにする

次は、最初に入れたものが最初に出るFIFO（First In, First Out）の構造です。受付の順番待ちや、レジの列を想像するとイメージしやすいでしょう。プリンターの印刷ジョブ、メッセージキュー、タスクの順次処理など、現場での出番がとても多い構造です。

キューの基本操作

スタックと名前が似ていますが、操作の意味は列（Queue）らしさを持っています。用語の雰囲気をつかんでおきましょう。

• enqueue(item): 後ろに並ぶ（追加）
• dequeue(): 前から順に出ていく（取り出し）
• front(): 先頭の中身をのぞき見る（取り出さない）
• is_empty(): 空かどうかを調べる

まずは仕組み理解のためのシンプル実装

最初はリストだけでキューを表現してみます。

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)      # 後ろに並ぶ

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.pop(0)     # 先頭から取り出す（ここがポイント）

    def front(self):
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self.items[0]         # 先頭をのぞく

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# 動かしてみよう
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 1（先に来た1が先に出る）
print(queue.front())    # 2
print(queue.is_empty()) # False

実は、リストのpop(0)は先頭要素を取り出したあとに、残りをすべて前につめ直す必要があり、要素数に比例して時間がかかります（O(n)）。

要素が多いキューでは、これがボトルネックになります。「使っていたらだんだん遅くなってきた…」というのは、まさにこの挙動が原因で起きがちです。

実践ではcollections.dequeで効率化しよう

そこでPython標準ライブラリのcollections.deque（デック）の出番です。dequeは両端への追加・取り出しがどちらもO(1)で、キューにぴったりです。業務コードや大きなデータを扱う場合は、基本的にこちらを使うのがベストプラクティスです。

from collections import deque

class FastQueue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)      # 右端に追加（O(1)）

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.popleft()  # 左端から取り出す（O(1)）

    def front(self):
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self.items[0]         # 先頭をのぞく（要素はそのまま）

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# こちらが実務向け
fq = FastQueue()
fq.enqueue("A")
fq.enqueue("B")
fq.enqueue("C")
print(fq.dequeue())  # A
print(fq.front())    # B
print(fq.size())     # 2

キューのコード解説

リスト版とdeque版の違いは「先頭から取り出す方法」にあります。リストではpop(0)が重いのに対し、dequeはpopleftが瞬時に終わります。enqueueはappend（右端に追加）、dequeueはpopleft（左端から取り出し）という両端操作の組み合わせで、常にO(1)の性能を確保できます。frontは先頭要素を眺めるだけなので構造は変わりません。空のときはエラーを投げる実装にしておくと、バグの早期発見につながります。

まとめ（次の学習へのつなぎ）

ここまでで、Pythonでのスタック（LIFO）とキュー（FIFO）の実装、そして効率よく動かすための考え方を身につけました。スタックはlistのappend/popで手軽に、高速に扱えます。キューは小規模ならlistでも動きますが、実務や学習を通じて覚えておきたいのはcollections.dequeを使うこと。これだけでパフォーマンスの心配がぐんと減ります。

「なぜ順番が大事なのか？」という視点は、探索やソート、さらにはヒープ（優先度キュー）にもつながっていきます。次のセクション「ヒープ（優先度キュー）の概念と基本操作」では、優先順位付きで取り出せるデータ構造を学び、より実用的な“順番のコントロール”へ進んでいきましょう。