スタックとキューの実装

スタックとキューは、データ構造の中でも非常に基本的で重要な構造です。この教材では、Pythonを使用してスタックとキューを実装し、その動作を理解します。

スタックの実装

スタックは「後入れ先出し（Last In First Out, LIFO）」のデータ構造です。つまり、最後に追加された要素が最初に取り出されます。

スタックの基本操作

スタックには主に以下の操作があります。

• push(item): 要素をスタックの上に追加する
• pop(): スタックの上から要素を取り出す
• peek(): スタックの上の要素を確認する（取り出さない）
• is_empty(): スタックが空かどうかを確認する

スタックの実装コード

以下に、スタックの実装コードを示します。

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
print(stack.peek()) # 2
print(stack.is_empty()) # False

コードの解説

• __init__: スタックの初期化を行い、内部リストitemsを作成します。
• push: 引数itemをitemsリストの末尾に追加します。
• pop: スタックが空でない場合、最上部の要素を取り出して返します。空の場合はエラーを発生させます。
• peek: スタックの最上部の要素を返しますが、スタックは変更しません。空の場合はエラーを発生させます。
• is_empty: スタックが空であるかどうかを真偽値で返します。
• size: スタックの要素数を返します。

キューの実装

キューは「先入れ先出し（First In First Out, FIFO）」のデータ構造です。つまり、最初に追加された要素が最初に取り出されます。

キューの基本操作

キューには主に以下の操作があります。

• 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
print(queue.front())    # 2
print(queue.is_empty()) # False

コードの解説

• __init__: キューの初期化を行い、内部リストitemsを作成します。
• enqueue: 引数itemをitemsリストの末尾に追加します。
• dequeue: キューが空でない場合、最前部の要素を取り出して返します。空の場合はエラーを発生させます。
• front: キューの最前部の要素を返しますが、キューは変更しません。空の場合はエラーを発生させます。
• is_empty: キューが空であるかどうかを真偽値で返します。
• size: キューの要素数を返します。

まとめ

スタックとキューは、基本的なデータ構造であり、さまざまなアルゴリズムや問題解決に利用されます。スタックはLIFOの性質を持ち、キューはFIFOの性質を持っています。これらのデータ構造を適切に利用することで、効率的なプログラムを構築することができます。