Pythonでのスタック、キューと優先順位のキューの実現方法

前言
スタック、キュー、および優先キューは、非常に基礎的なデータ構造である。Pythonは「符号化の効率的」な言語として、これらの基礎的なデータ構造に対して比較的良い実現があります。業務需要の開発過程で、車輪を繰り返し作るべきではなく、今日はいくつかのデータ構造の実現を見に来ました。
0 x 00スタック（Stck）
スタックはLIFO（後進先出）のデータ構造であり、スタック（push）、スタック（pop）の2つの操作があり、スタックの一番上の要素しか操作できない。
Pythonにはスタックを実現できる多くのデータ構造がある。
1、リスト
listはPythonに内蔵されているリストデータ構造であり、スタックの特性をサポートしています。ただリストでスタックの性能を実現するのは特に良くないです。
リスト内部は動的拡がりの配列により実現されるからである。要素を増減させると拡大操作がトリガされる可能性があります。リストの先頭に要素を増減させると、リスト全体が移動します。
リストを使用してスタックを実現するためには、listのappnd（入スタック）、pop（スタック）方法が使用されてもよい。

>>> s = []
>>> s.append('one')
>>> s.append('two')
>>> s.append(3)
>>> s
['one', 'two', 3]
>>> s.pop()
3
>>> s.pop()
'two'
>>> s.pop()
'one'
>>> s.pop()
IndexError: pop from empty list

2、collection s.deque
dequeクラスは二重端行列です。Pythonでは、一般的な時間で要素の追加と削除を両端で行うことができます。非常に効率的なので、スタックを実現することも、キューを実現することもできます。
もしPythonでスタックを実現するなら、優先的にdequeを選択すべきで、listではない。
dequeのスタックとスタック方法もそれぞれapped()とpop()です。

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')
>>> s
deque(['eat', 'sleep', 'code'])
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
>>> s.pop()
IndexError: pop from an empty deque

3、queue.LifoQue
名前の通り、これはつまりスタックです。しかし、スレッドは安全です。併発する環境で使うなら、LifoQueを使うことができます。
それはスタックとスタックの操作にput()とget()を使っています。ここでget()はLifoQueが空の時に詰まります。

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')
>>> s
<queue.LifoQueue object at 0x109dcfe48>
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
>>> s.get()
#              

0 x 01列(Queue)
キューはFIFO（先入先出）のデータ構造です。入隊、出隊の2つの操作があり、しかも定数時間の操作です。
Pythonではどのようなデータ構造を使用して行列を実現できますか？
1、リスト
リストは1つの列を実現することができますが、その入隊、出隊操作は非常に効率的ではありません。リストはダイナミックなリストですので、キューの頭からチーム操作を行うと、要素全体の移動が発生します。
リストを使用して1つのキューを実現する場合は、appnd()で入隊操作を行い、pop(0)法を用いてキューヘッドでチーム外操作を実行します。リストの最初の要素で動作するので、後続の要素は前の位置に移動します。リストで列を実現するのはおすすめできません。

>>> q = []
>>> q.append('1')
>>> q.append('2')
>>> q.append('three')

>>> q.pop(0)
'1'
>>> q.pop(0)
'2'
>>> q.pop(0)
'three'
>>> q.pop(0)
IndexError: pop from empty list

2、collection s.deque
上記から、dequeは双方向リストであることが分かりました。リストの両端に定数時間で追加削除操作ができます。したがって、dequeでキューを実現するのは非常に効率的である。
deque入隊操作はapped()の方法を使って、アウト操作はpopleft()の方法を使います。

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')
>>> q
deque(['eat', 'sleep', 'code'])
#   popleft  
>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'
>>> q.popleft()
IndexError: pop from an empty deque

3、queue.Que
同様に、併発環境でキューを使用する場合は、スレッドの安全なqueue.Queを選択します。
LifoQueと似ていますが、入隊と出隊はそれぞれput（）とget（）の方法で操作されています。get（）は列が空いている間はずっとブロックされています。

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<queue.Queue object at 0x110564780>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
#           
>>> q.get_nowait()
_queue.Empty
>>> q.put('111')
>>> q.get_nowait()
'111'
>>> q.get()
#      ，            

4、マルチプレックス.Queue
プロセスバージョンのキュー。マルチプロセス環境でキューを使うなら、マルチプレックス・Queueを選ぶべきです。
同じように、その入隊操作はput（）とget（）です。get()メソッドは列が空で、列が空でないまで渋滞します。

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<multiprocessing.queues.Queue object at 0x110567ef0>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
>>> q.get_nowait()
_queue.Empty
>>> q.get()
#      ，            

0 x 02優先列（PriorityQue）
ほぼ並べ替えられたシーケンスでは、優先順位の列というデータ構造を使用して、最大または最小の要素を効率的に取得することができます。
スケジュール問題のシーンでは優先順位の列がよく使われます。これは主に最大値または最小値を取得する操作と入力操作があります。
1、リスト
優先順位のあるキューはlistを使用して実現できるが、効率的ではない。一番の値を取得するには並べ替えが必要です。そして一番の値を取得します。新しい要素が追加されたら、再び一番の値を取得すると、また並べ替えます。だからオススメします。
2、heappq
一般的に、優先順位の列は、このようなデータ構造のヒープを使用して実装される。heappqはPython標準倉庫の中で積み上げる実現です。heappqデフォルトで実現されるのは一番小さい山です。
入隊操作はヒップホップ（）を使い、出隊操作はヒップホップ（）を使います。

>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, 'code'))
>>> heapq.heappush(q, (1, 'eat'))
>>> heapq.heappush(q, (3, 'sleep'))
>>> q
[(1, 'eat'), (2, 'code'), (3, 'sleep')]
>>> while q:
	next_item = heapq.heappop(q)
	print(next_item)

	
(1, 'eat')
(2, 'code')
(3, 'sleep')

3、queue.PriorityQue
queue.PriorityQueの内部はheappqをカプセル化しています。違いはスレッドの安全です。併発の環境下でPriorityQueを使うべきです。

>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, 'code'))
>>> q.put((1, 'eat'))
>>> q.put((3, 'sleep'))
>>> while not q.empty():
	next_item = q.get()
	print(next_item)

(1, 'eat')
(2, 'code')
(3, 'sleep')

0 x 03まとめてみます
多くの基礎的なデータ構造はPythonで既に実現されており、我々は車輪を繰り返して作るべきではなく、これらのデータ構造を選択して業務需要を実現するべきである。
collection.dequeは双方向のチェーンテーブルで、シングルスレッドの場合、StckとQueueueを実現するために使用できます。一方、heappqモジュールは、効率的な優先順位の高いキューを実現してくれます。
同時多発の場合、Stck、Que、PriorityQueを使うなら、queueモジュールの下のクラスを選択します。

スタックのqueue.LifoQue

を実現します。

Queのqueue.Queまたはmultiprocessing.Que

を実現しました。

PriorityQueのqueue.PriorityQue

を実現しました。

以上のこれらのクラスはput()とget()の方法があり、get()はスタック/列が空いている時に閉塞します。

0 x 04学習資料
Python Tricks:A Buffet of Awesome Python Feature s
――Dan Bader
はい、以上はこの文章の全部の内容です。本文の内容は皆さんの学習や仕事に対して一定の参考学習価値を持つことを望んでいます。ありがとうございます。