Pythonで1つのキューを使ってスタックを実装する方法

1つのキューだけを使ってスタック（LIFO：後入れ先出し）を実装するには、「Stack_structure」クラスと、その内部で利用する「Queue_structure」クラスの2つを用意します。それぞれのクラスに、値を追加・削除するためのメソッドを定義していきます。

キューは先入れ先出し（FIFO）という特性を持つため、pop操作の際には「最後に入れた要素以外を一度取り出して、再びキューの末尾へ戻す」という並べ替え処理が必要になる点がポイントです。以下に具体的な実装例を示します。

サンプルコード

class Stack_structure:
    def __init__(self):
        self.q = Queue_structure()

    def check_empty(self):
        return self.q.check_empty()

    def push_val(self, data):
        self.q.enqueue_operation(data)

    def pop_val(self):
        for _ in range(self.q.size_calculate() - 1):
            dequeued = self.q.dequeue_operation()
            self.q.enqueue_operation(dequeued)
        return self.q.dequeue_operation()

class Queue_structure:
    def __init__(self):
        self.items = []
        self.size = 0

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

    def enqueue_operation(self, data):
        self.size += 1
        self.items.append(data)

    def dequeue_operation(self):
        self.size -= 1
        return self.items.pop(0)

    def size_calculate(self):
        return self.size

my_instance = Stack_structure()

print('Menu')
print('push ')
print('pop')
print('quit')

while True:
    my_input = input('What operation 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':
        if my_instance.check_empty():
            print('The stack is empty.')
        else:
            print('The deleted value is : ', my_instance.pop_val())
    elif operation == 'quit':
        break

出力結果

Menu
push 
pop
quit
What operation would you like to perform ? push 89
What operation would you like to perform ? push 43
What operation would you like to perform ? push 76
What operation would you like to perform ? push 56
What operation would you like to perform ? pop
The deleted value is : 56
What operation would you like to perform ? quit

コードの解説

• 「Stack_structure」クラスを作成し、内部に「Queue_structure」のインスタンスを保持します。

• 「check_empty」メソッドを定義し、スタックが空かどうかを判定できるようにします。

• 「push_val」メソッドを定義し、スタックへ要素を追加できるようにします。

• 「pop_val」メソッドを定義し、スタックから要素を取り除きます。ここでは、キューのサイズから1を引いた回数だけ要素を取り出しては末尾に戻すことで、最後に入れた要素を先頭に移動させています。

• 「Queue_structure」クラスを作成し、内部に空のリストを初期化するとともに、サイズを0に設定します。

• 「check_empty」メソッドを定義し、キューが空かどうかを判定できるようにします。

• 「enqueue_operation」メソッドを定義し、キューへ要素を追加できるようにします。

• 「dequeue_operation」メソッドを定義し、キューから要素を取り除けるようにします。

• 「size_calculate」メソッドを定義し、キューの現在のサイズを取得できるようにします。

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

• ユーザーが選択できる操作として「push」「pop」「quit」の3種類をメニューとして表示します。

• ユーザーの入力内容に応じて、スタックへの追加・削除などの操作を実行します。

• 処理結果はコンソールに出力されます。

計算量の目安

この実装では、push操作はキューの末尾に追加するだけなのでO(1)で実行できます。一方、pop操作では要素の並べ替えのために全要素を一度巡回する必要があるため、計算量はO(n)となります。データ数が多い場合にはこの点に注意してください。