Pythonで連結リストを使ってスタックを実装するプログラム

連結リスト（リンクリスト）を使用してスタックデータ構造を実装する場合、要素を追加する「プッシュ（push）」操作と、要素を取り出す「ポップ（pop）」操作に対応するメソッドを定義します。

スタックは「後入れ先出し（LIFO：Last In, First Out）」という特性を持つデータ構造です。本記事の実装では、pushとpopのどちらの操作も先頭ノードのみを書き換えるため、計算量O(1)で高速に処理できる点が大きな特徴です。

以下に具体的な実装例を示します。

サンプルコード

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack_structure:
    def __init__(self):
        self.head = None

    def push_val(self, data):
        if self.head is None:
            self.head = Node(data)
        else:
            newNode = Node(data)
            newNode.next = self.head
            self.head = newNode

    def pop_val(self):
        if self.head is None:
            return None
        else:
            del_Val = self.head.data
            self.head = self.head.next
            return del_Val

my_instance = Stack_structure()
while True:
    print('push <value>')
    print('pop')
    print('quit')
    my_input = input('What action would you like to perform ? ').split()

    operation = my_input[0].strip().lower()
    if operation == 'push':
        my_instance.push_val(int(my_input[1]))
    elif operation == 'pop':
        del_Val = my_instance.pop_val()
        if del_Val is None:
            print('The stack is empty.')
        else:
            print('The deleted value is : ', int(del_Val))
    elif operation == 'quit':
        break

実行結果

push <value>
pop
quit
What action would you like to perform ? push 56
push <value>
pop
quit
What action would you like to perform ? push 78
push <value>
pop
quit
What action would you like to perform ? push 90
push <value>
pop
quit
What action would you like to perform ? pop
The deleted value is : 90
push <value>
pop
quit
What action would you like to perform ? quit

コードの解説

• まず、格納するデータ（data）と次のノードへの参照（next）を持つ「Node」クラスを作成します。

• 続いて、必要な属性を備えた「Stack_structure」クラスを別途定義します。

• 「__init__」関数では、スタックの先頭を表す「head」を「None」で初期化します。

• 「push_val」メソッドは、新しいノードをスタックの先頭に挿入することで、値をスタックへ追加します。

• 「pop_val」メソッドは、スタックの最上位（先頭）の値を削除し、その削除した値を呼び出し元に返します。スタックが空の場合はNoneを返します。

• 「Stack_structure」クラスのインスタンスを生成します。

• ユーザーに対して「push」「pop」「quit」の3つの選択肢を提示します。

• 「push」を選択すると、指定した値がスタックに追加されます。

• 「pop」を選択すると、スタックの最上位にある要素が削除され、その値が表示されます。

• 「quit」を選択すると、無限ループを抜けてプログラムが終了します。

• ユーザーの入力内容に応じて、それぞれ対応する操作が実行されます。

• 各操作の結果はコンソールに出力されます。

このように、連結リストの先頭だけを操作対象にすることで、配列を使った実装とは異なり、要素数に依存しない効率的なスタック操作が実現できます。