Pythonでスタックを使ってキュー（Queue）を実装する方法【コード例付き】

スタック（Stack）を使ってキュー（Queue）を実装したい場合は、キュー専用のクラスを定義し、その中に2つのスタックインスタンスを持たせるのが一般的な手法です。このクラス内に各操作をメソッドとして定義することで、キューに対してさまざまな操作を柔軟に行えるようになります。

以下に、実際の実装例とその動作を示します。

サンプルコード

class Queue_structure:
   def __init__(self):
      self.in_val = Stack_structure()
      self.out_val = Stack_structure()

   def check_empty(self):
      return (self.in_val.check_empty() and self.out_val.check_empty())

   def enqueue_operation(self, data):
      self.in_val.push_operation(data)

   def dequeue_operation(self):
      if self.out_val.check_empty():
         while not self.in_val.check_empty():
            deleted_val = self.in_val.pop_operation()
            self.out_val.push_operation(deleted_val)
      return self.out_val.pop_operation()

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

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

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

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

my_instance = Queue_structure()

while True:
   print('enqueue <value>')
   print('dequeue')
   print('quit')
   my_input = input('What operation would you like to perform ?').split()

   operation = my_input[0].strip().lower()
   if operation == 'enqueue':
      my_instance.enqueue_operation(int(my_input[1]))
   elif operation == 'dequeue':
      if my_instance.check_empty():
         print('The queue is empty')
      else:
         deleted_elem = my_instance.dequeue_operation()
         print('The deleted element is : ', int(deleted_elem))
   elif operation == 'quit':
      break

実行結果

enqueue <value>
dequeue
quit
What operation would you like to perform ?enqueue 45
enqueue <value>
dequeue
quit
What operation would you like to perform ?enqueue 23
enqueue <value>
dequeue
quit
What operation would you like to perform ?enqueue 78
enqueue <value>
dequeue
quit
What operation would you like to perform ?dequeue
The deleted element is : 45
enqueue <value>
dequeue
quit
What operation would you like to perform ?quit

コードの解説

• まず「Queue_structure」クラスを定義し、その中にスタックのインスタンスを2つ（in_val と out_val）作成しています。

• 「check_empty」メソッドは、両方のスタックが空であるかを確認し、キュー全体が空かどうかを判定します。

• 「enqueue_operation」メソッドは、要素を in_val 側のスタックにプッシュすることで、キューへの追加（エンキュー）を実現します。

• 「dequeue_operation」メソッドは、out_val 側のスタックが空の場合、in_val の全要素を順番に移し替えてからポップすることで、先入れ先出し（FIFO）の取り出し（デキュー）を実現します。

• 次に、スタック本体となる「Stack_structure」クラスを作成しています。

• このクラスでは、内部に空のリストを初期化してデータを保持します。

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

• 「push_operation」メソッドはリストの末尾に要素を追加し、「pop_operation」メソッドは末尾から要素を取り除いて返します。

• 最後に「Queue_structure」のインスタンスを生成し、ユーザーに対して enqueue / dequeue / quit の3つの選択肢を提示します。

• ユーザーが入力したコマンドに応じて対応する操作が実行され、その結果がコンソールに出力されます。

ポイント：なぜ2つのスタックが必要？

スタックは後入れ先出し（LIFO）、キューは先入れ先出し（FIFO）という、互いに逆の性質を持つデータ構造です。そこで、要素を一旦 in_val に積み、取り出す際に out_val へ移し替えることで順序を反転させ、キューと同じ振る舞いを実現しています。この手法では、各要素は高々2回ずつ移動されるため、ならし計算量（Amortized O(1)）で効率的に動作します。