再帰を使ってスタックを逆順に反転するPythonプログラム

再帰（リカージョン）を使用してスタック（Stack）データ構造を反転させたい場合、値の追加・削除・要素の表示を行う基本メソッドに加え、反転処理を担当する stack_reverse メソッドを定義します。

本記事では、その実装方法と動作の仕組みを、実際のコード例と実行結果とともにわかりやすく解説します。

サンプルコード

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

    def check_empty(self):
        return self.items == []

    def push_val(self, data):
        self.items.append(data)

    def pop_val(self):
        return self.items.pop()

    def print_it(self):
        for data in reversed(self.items):
            print(data)

def insert_bottom(instance, data):
    if instance.check_empty():
        instance.push_val(data)
    else:
        deleted_elem = instance.pop_val()
        insert_bottom(instance, data)
        instance.push_val(deleted_elem)

def stack_reverse(instance):
    if not instance.check_empty():
        deleted_elem = instance.pop_val()
        stack_reverse(instance)
        insert_bottom(instance, deleted_elem)

my_instance = Stack_structure()
data_list = input('Enter the elements to add to the stack: ').split()
for data in data_list:
    my_instance.push_val(int(data))

print('The reversed stack is:')
my_instance.print_it()
stack_reverse(my_instance)
print('The stack is:')
my_instance.print_it()

実行結果

Enter the elements to add to the stack: 23 56 73 81 8 9 0
The reversed stack is:
0
9
8
81
73
56
23
The stack is:
23
56
73
81
8
9
0

プログラムの仕組み

• Stack_structure クラスを作成し、__init__ メソッド内で空のリストを初期化します。

• check_empty メソッドは、スタックが空かどうかを判定します。

• push_val メソッドは、引数で受け取ったデータをスタックの末尾に追加します。

• pop_val メソッドは、スタックから末尾の要素を取り除き、その値を返します。

• print_it メソッドは、reversed 関数を使ってスタックの要素を見やすい形で表示します。

• insert_bottom 関数は、通常の追加処理とは異なり、要素をスタックの一番下（底）に挿入するための補助関数です。スタックが空になるまで要素を取り出してから、目的のデータを挿入し、取り出した要素を元の順序で戻すことで実現しています。

• stack_reverse 関数は、スタックが空になるまで要素を一つずつ取り出しながら自分自身を再帰的に呼び出し、最後に insert_bottom を使って各要素を底から積み直すことで、スタック全体を反転させます。

• このクラスのインスタンスを生成し、ユーザーからスペース区切りで入力された複数の要素を受け取ります。

• 受け取った各要素を反復処理し、push_val メソッドでスタックへ追加していきます。

• まず反転前の状態を表示した後、stack_reverse を呼び出してスタックを反転させます。

• 最後に print_it を呼び出し、反転後のスタックの内容をコンソールに出力します。