Pythonで先頭・中央・末尾から要素を追加・削除できるキューを実装する方法

本記事では、キューの先頭（フロント）・中央（ミドル）・末尾（バック）の3箇所から値を追加（push）および削除（pop）できるデータ構造を、Pythonで実装する方法を解説します。さらに、任意の時点でのキュー全体の状態を確認できる関数も併せて実装します。

実装する機能一覧

今回作成するクラスは、以下の7つのメソッドを持つ必要があります。

• push_from_front(value)：キューの先頭に値を追加する
• push_from_middle(value)：キューの中央に値を追加する
• push_from_back(value)：キューの末尾に値を追加する
• pop_from_front()：先頭の要素を取り出して削除する
• pop_from_middle()：中央の要素を取り出して削除する
• pop_from_back()：末尾の要素を取り出して削除する
• show_queue()：現在のキューの全要素を返す

動作例

例えば、次の順序で操作を行った場合を考えてみましょう。

push_from_back(10)
push_from_back(20)
push_from_front(30)
push_from_middle(40)
push_from_front(50)
show_queue()
pop_from_back()
show_queue()
pop_from_front()
show_queue()
pop_from_middle()
show_queue()

この場合、出力は以下のようになります。

[50, 30, 40, 10, 20]
[50, 30, 40, 10]
[30, 40, 10]
[30, 10]

実装の方針

ここではシンプルに、Pythonのリスト（配列）をキューの内部表現として使用します。各操作は次のように定義できます。

• push_from_front()：リストの位置0に値を挿入する
• push_from_middle()：リストの長さを2で割った位置（中央）に値を挿入する
• push_from_back()：リストの末尾に値を追加する
• pop_from_front()：リストが空でなければ、先頭の要素を削除して返す
• pop_from_middle()：（リストの長さ − 1）を2で割った位置の要素を削除して返す
• pop_from_back()：末尾の要素を削除して返す
• show_queue()：引数なしで呼び出され、リストそのものを返す

なお、キューが空の状態でpopが呼ばれた場合に備え、(self.array or [-1])というイディオムを使って、空なら -1 を返すようにしています。これによりエラーを回避しつつ、簡潔なコードを実現できます。

Pythonによる実装コード

それでは、実際のコードを見てみましょう。

class Solution():

   def __init__(self):
      self.array = []

   def push_from_front(self, value):
      self.array.insert(0, value)

   def push_from_middle(self, value):
      self.array.insert(len(self.array) // 2, value)

   def push_from_back(self, value):
      self.array.append(value)

   def pop_from_front(self):
      return (self.array or [-1]).pop(0)

   def pop_from_middle(self):
      return (self.array or [-1]).pop((len(self.array) - 1) // 2)

   def pop_from_back(self):
      return (self.array or [-1]).pop()

   def show_queue(self):
      return self.array

ob = Solution()
ob.push_from_back(10)
ob.push_from_back(20)
ob.push_from_front(30)
ob.push_from_middle(40)
ob.push_from_front(50)
print(ob.show_queue())
ob.pop_from_back()
print(ob.show_queue())
ob.pop_from_front()
print(ob.show_queue())
ob.pop_from_middle()
print(ob.show_queue())

入力

ob = Solution()
ob.push_from_back(10)
ob.push_from_back(20)
ob.push_from_front(30)
ob.push_from_middle(40)
ob.push_from_front(50)
print(ob.show_queue())
ob.pop_from_back()
print(ob.show_queue())
ob.pop_from_front()
print(ob.show_queue())
ob.pop_from_middle()
print(ob.show_queue())

出力

[50, 30, 40, 10, 20]
[50, 30, 40, 10]
[30, 40, 10]
[30, 10]

計算量のポイント

この実装における各操作の計算量は以下の通りです。

• push_from_back / pop_from_back：O(1)。リストの末尾への追加・削除は高速です。
• push_from_front / pop_from_front：O(n)。先頭への挿入や削除では、後続の全要素をずらす必要があります。
• push_from_middle / pop_from_middle：O(n)。中央付近の操作も同様に要素の移動が発生します。

もし先頭と末尾の操作だけが必要であれば、collections.dequeを使うことで両端の操作をO(1)で行えます。しかし、dequeは中央への効率的なアクセスをサポートしないため、中央操作が必要な本ケースではリストベースの実装が適しています。要素数が非常に大きくパフォーマンスが重要になる場合は、平衡二分探索木やインデックス付きの連結リストなど、より高度なデータ構造の採用も検討するとよいでしょう。