Python でのキューの実装について

データ構造はプログラミングの世界において重要な役割を果たします。これらは、データを効率的に使用できる方法で整理するのに役立ちます。 キューは、 利用可能な最も単純なデータ構造の 1 つです。

この記事では、 Queue と Python でのその実装について学びます。

キューとは何ですか?

キューは、 先入れ先出し (FIFO) 原則に従う線形データ構造です。これは Stack データ構造とは逆です。

この 行列を 、映画のチケット カウンターの実際の行列 と比較してみましょう。次のようなキューの図を見てみましょう。

カウンターの列を観察すると、最初の人が作業を終えてからでないと 2 番目の人がカウンターに行くことができません。ここで最初の人がカウンターに来て、次に二人目がカウンターに来ます。したがって、ここでは FIFO (先入れ先出し) の 原則に従っています。誰が最初に来ても、その人が最初に仕事を完了します。私たちの日常生活でも、同様の行列が見られます。

Queue データ構造も同じ原則に従います。これで、キューとは何か、そしてその原理がわかりました。 キューの データ構造に対して実行できる操作を見てみましょう。

キュー内の操作

スタックと同様に、 キュー データ構造には 2 つの主要な操作があります。

エンキュー(データ)

新しいデータをキューの最後に追加します。側面を リア と呼びます。

デキュー()

キューの先頭からデータを削除します。側面を 正面 と呼びます。

理解を深めるために、キュー操作の図を見てみましょう。一枚の写真は千の言葉を語ります。

キューに関する詳細情報を取得するために、いくつかのヘルパー関数を作成できます。使用できるヘルパー関数の数に制限はありません。ここでは、これまでに説明した最も重要な点に注目してみましょう。

後方（）

キューの最後から最初の要素を返します。

フロント（）

キューの先頭から最初の要素を返します。

is_empty()

キューが空かどうかを返します。

それはあなたにとって退屈ではありませんか？概念的なトピックを意味します。

私にとっては そうだ！

しかし、概念を知らなければ何もできません。実装前にそれを完全に把握する必要があります。心配しないでください。コードを使って手を汚す時が来たのです。

PC に Python がインストールされていると思いますが、インストールされていない場合は、オンライン コンパイラーを試すこともできます。

キューの実装

プログラマーにとってキューの実装には 15 分もかかりません。一度学べば、言えるようになるでしょう。おそらくこのチュートリアルを終えたら数分以内に実装できるでしょう。

Python でキューを実装するには複数の方法があります。さまざまなキューの実装を段階的に見てみましょう。

#1. リスト

リストは Python の組み込みデータ型です。リスト データ型を使用してクラスに キュー を実装します。モジュールを使用せずにキュー データ構造を最初から実装するためのさまざまな手順を説明します。さあ、飛び込みましょう。

ステップ1：

Queue というクラスを作成します。

 class Queue:
	pass

ステップ2：

キューのデータをクラスに格納するには、何らかの変数が必要です。これに elements という名前を付けましょう。そしてそれはもちろんリストです。

 class Queue:

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

ステップ3:

キューにデータを挿入するには、クラス内にメソッドが必要です。チュートリアルの前のセクションですでに説明したように、このメソッドは enqueue と呼ばれます。

このメソッドはデータを取得し、それをキュー (要素) に追加します。リスト データ型の append メソッドを使用して、キューの最後にデータを追加できます。

 class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

ステップ4:

キューには出口が必要です。それは dequeue と呼ばれます。リスト データ型の Pop メソッドを使用することはすでに推測されていると思います。推測したかどうかに関係なく、 乾杯 !

リスト データ型の Pop メソッドは、指定されたインデックスのリストから要素を削除します。インデックスを指定しなかった場合は、リストの最後の要素が削除されます。

ここでは、リストの最初の要素を削除する必要があります。したがって、インデックス 0 を Pop メソッドに渡す必要があります。

 class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

行列にはこれで十分です。ただし、キューの操作が適切に機能しているかどうかをテストするには、ヘルパー関数が必要です。ヘルパー関数も書いてみましょう。

ステップ5:

メソッド Rear() は 、キューの最後の要素を取得するために使用されます。リスト データ型の負のインデックス付けは、キューの最後の要素を取得するのに役立ちます。

 class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

ステップ6:

メソッド front()は、 キューの最初の要素を取得するために使用されます。リスト インデックスを使用してキューの最初の要素を取得できます。

 class Queue:

	# ...

	def front(self):
		return self.elements[0]

ステップ7:

is_empty() メソッドは、キューが空かどうかを確認するために使用されます。リストの長さを確認できます。

 class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

ふう！ キュー データ構造の実装部分が完了しました。 Queue クラスが使用するオブジェクトを作成する必要があります。

やりましょう。

 class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

これで Queue オブジェクトができました。いくつかの一連の操作でテストしてみましょう。

• is_empty メソッドを使用してキューが空かどうかを確認します。 True を返す必要があります。
• enqueue メソッドを使用して、番号 1、2、3、4、5 を キュー に追加します。
• is_empty メソッドは False を 返す必要があります。確認してください。
• フロント メソッドと リア メソッドをそれぞれ使用して、 フロント 要素と リア 要素を印刷します。
• dequeue メソッドを使用してキューから要素を削除します。
• 前 玉を確認してください。要素 2 を返す必要があります。
• 次に、キューからすべての要素を削除します。
• is_empty メソッドは True を返す必要があります。確認してください。

キューの実装をテストするにはこれで十分だと思います。キューをテストするには、上記の各ステップのコードを記述します。

コードを書きましたか?

いいえ、心配しないでください。

以下のコードを確認してください。

 class Queue:

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

	def enqueue(self, data):
		self.elements.append(data)
		return data

	def dequeue(self):
		return self.elements.pop(0)

	def rear(self):
		return self.elements[-1]

	def front(self):
		return self.elements[0]

	def is_empty(self):
		return len(self.elements) == 0

if __name__ == '__main__':
	queue = Queue()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

上記のプログラムを実行すると思います。次の結果のような出力が得られます。

 True
False
1 5
2 5
True

リスト データ型を キュー データ構造として直接使用できます。上記のキューの実装は、他のプログラミング言語でのキューの実装をより深く理解するのに役立ちます。

また、前に行ったようにオブジェクトを作成するだけで、プロジェクトの別のプログラムで キュー の上記のクラス実装を使用することもできます。

リスト データ型を使用して キューを 最初から実装しました。キュー用の組み込みモジュールはありますか?うん！組み込みのキュー実装があります。見てみましょう。

#2. コレクションからのデック

これは両端キューとして実装されます。両端からの要素の追加と削除をサポートしているため、 スタック や キュー として使用できます。 dequeue を 使用したキューの実装を見てみましょう。

これは、 二重リンク リストと呼ばれる他のデータ構造を使用して実装されます。したがって、要素の挿入と削除のパフォーマンスは一貫しています。中央のリンク リストから要素にアクセスするには O(n) 時間がかかりました。 キュー から中間要素にアクセスする必要がないため、 キュー として使用できます。

デキュー が提供するさまざまなメソッドを確認してみましょう。

• append(data) – データをキューに追加するために使用されます
• Popleft() – キューから最初の要素を削除するために使用されます

フロント、リア、 および is_empty には代替メソッドはありません。 フロント メソッドと リア メソッドの代わりにキュー全体を出力できます。次に、 len メソッドを使用して、 キュー が空かどうかを確認します。

前回では、一連の手順に従って キューの 実装をテストしました。ここでも同じ一連の手順に従います。

 from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

次の出力のような結果が得られます。

 True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. キューからのキュー

Python には、キュー実装用の Queue というクラスを提供する queue という組み込みモジュールがあります。以前に実装したものと似ています。

まず、 Queue クラスのさまざまなメソッドをチェックアウトしてみましょう。

• put(data) – データをキューに追加またはプッシュします
• get() – キューから最初の要素を削除し、それを返します
• empty() – スタックが空かどうかを返します
• qsize() – キューの長さを返します。

上記のメソッドでキューを実装してみましょう。

 from queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

上記のコードの出力を確認してください。

 True
False
1
2
3
Size 2
4
5
True

Queue クラスには他にもいくつかのメソッドがあります。 dir 組み込み関数を使用してそれらを探索できます。

結論

キューのデータ構造とその実装について学習できたと思います。待ち行列はこれで終わりです。 FIFO (先入れ先出し) 順序で処理する必要があるさまざまな場所でキューを使用できます。キューを使用するケースが発生した場合は、問題解決にキューを使用します。

Python をマスターすることに興味がありますか?これらの学習リソースを確認してください。

コーディングを楽しんでください 🙂 👨‍💻