Pythonで連結リストを使ってキュー（Queue）データ構造を実装する方法

連結リスト（リンクリスト）を用いてキューのデータ構造を実装するには、要素を末尾に追加するメソッド（enqueue操作）と、先頭から要素を取り出して削除するメソッド（dequeue操作）を定義します。キューは「先入れ先出し（FIFO：First In, First Out）」という特性を持つデータ構造であり、最初に追加した要素が最初に取り出されます。

以下に、その実装例を示します。

サンプルコード

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

class Queue_structure:
   def __init__(self):
      self.head = None
      self.last = None

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

   def dequeue_operation(self):
      if self.head is None:
         return None
      else:
         val_returned = self.head.data
         self.head = self.head.next
         return val_returned

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':
      dequeued = my_instance.dequeue_operation()
      if dequeued is None:
         print('The queue is empty.')
      else:
         print('The deleted element is : ', int(dequeued))
   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 12
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

コードの解説

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

• 次に、キュー本体となる「Queue_structure」クラスを必要な属性とともに定義します。

• 初期化用の「__init__」関数では、先頭要素を表す「head」と末尾要素を表す「last」を「None」に設定して初期化します。

• 「enqueue_operation」メソッドは、キューの末尾に新しい値を追加するためのものです。キューが空の場合は新規ノードが先頭かつ末尾になり、そうでなければ既存の末尾ノードの後ろに接続します。

• 「dequeue_operation」メソッドは、キューの先頭から値を取り出して削除し、その削除された値を返します。キューが空の場合は「None」を返します。

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

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

• 「enqueue」を選ぶと、指定した値がキューに追加されます。

• 「dequeue」を選ぶと、キューから先頭の要素が削除され、その値が表示されます。

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

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