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

2つのキューを使用してスタックを実装するには、「Stack_structure」クラスと「Queue_structure」クラスが必要です。それぞれのクラスには、スタックおよびキューに対して値を追加・削除するためのメソッドが定義されています。

この手法では、push操作のたびに新しい要素をqueue_1に追加し、queue_2内の既存要素をすべてその後ろへ移動させてから2つのキューを入れ替えることで、キューでありながらスタック特有のLIFO（後入れ先出し）の動作を実現しています。

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

サンプルコード

class Stack_structure:
   def __init__(self):
      self.queue_1 = Queue_structure()
      self.queue_2 = Queue_structure()

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

   def push_val(self, data):
      self.queue_1.enqueue_operation(data)
      while not self.queue_2.check_empty():
         x = self.queue_2.dequeue_operation()
         self.queue_1.enqueue_operation(x)
      self.queue_1, self.queue_2 = self.queue_2, self.queue_1

   def pop_val(self):
      return self.queue_2.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 <value>')
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('Stack is empty.')
      else:
         print('The deleted value is: ', my_instance.pop_val())
   elif operation == 'quit':
      break

実行結果

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

コードの解説

• 「Stack_structure」クラスを作成し、内部で2つのキューを初期化します。

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

• スタックに要素を追加する「push_val」メソッドを定義します。新しい要素をqueue_1に入れ、queue_2の既存要素をすべてその後ろへ移動させた後、2つのキューを入れ替えます。

• スタックから要素を取り出す「pop_val」メソッドを定義します。

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

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

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

• キューから要素を取り出す「dequeue_operation」メソッドを定義します。

• キューのサイズを取得する「size_calculate」メソッドを定義します。

• 「Queue_structure」のインスタンスを2つ生成し、スタックの内部構造として利用します。

• ユーザーには「Menu」「push」「pop」「quit」の4つの操作を選択できるメニューを表示します。

• ユーザーが入力した内容に基づいて、スタックの要素に対する操作が実行されます。

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