Python でスタックを実装するいくつかの方法とその利点と欠点-Python チュートリアル-php.cn

ホームページ

バックエンド開発

Python チュートリアル

Python でスタックを実装するいくつかの方法とその利点と欠点

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 19, 2023 am 09:37 AM

pythonデータ構造

Python 实现栈的几种方式及其优劣

オープンソースの詳細については、

51CTO オープンソース基本ソフトウェアコミュニティをご覧ください。

https://ost.51cto.com

1. スタックの概念

スタックは次のように構成されていますオブジェクトごとに編成された一連のオブジェクトのコレクション。これらのオブジェクトの追加および削除操作は、「後入れ先出し」(LIFO) の原則に従います。

いつでもスタックに挿入できるオブジェクトは 1 つだけですが、取得または削除できるのはスタックの最上位でのみです。たとえば、本の山の中で、表紙が露出しているのは一番上の本だけです。他の本を取り出すには、図に示すように一番上の本を取り出すしかありません。

Python 实现栈的几种方式及其优劣 ## スタックの実用的な応用

#実際、多くのアプリケーションは次のようなスタックを使用します。

Web ブラウザは、最近アクセスした URL を次の場所に保存します。スタック。ユーザーの訪問者が新しい Web サイトにアクセスするたびに、新しい Web サイトの URL がスタックの一番上にプッシュされます。このようにして、ブラウザの [戻る] ボタンをクリックするたびに (またはキーボードショートカット CTRL Z、ほとんどの元に戻すショートカットを押すと)、最後にアクセスした URL をポップアップ表示して、前回アクセスしたときの閲覧状態に戻ることができます。

テキストエディタには通常、最新の編集操作をキャンセルして前の状態に戻る「元に戻す」メカニズムが備わっています。この取り消し操作は、テキストの変更された状態をスタックに保存することによっても実現されます。
一部の高級言語のメモリ管理、JVM スタック、Python スタックは、メモリ管理、入れ子になった言語機能のランタイム環境などにも使用されます。
バックトラック (ゲームのプレイ、パスの検索、網羅的検索)
ハノイ塔、ツリートラバーサル、ヒストグラム問題などのアルゴリズムで使用され、トポロジカルソートなどのグラフアルゴリズムでも使用されます
構文処理:

パラメータとローカル変数用のスペースは、スタックを使用して内部的に作成されます。

中括弧の一致に関するコンパイラ構文チェック
再帰のサポート
コンパイラにおける接尾辞や接頭辞などの式
2. 抽象データ型stack

あらゆるデータ構造は、データの保存と取得の方法から切り離せません。上で述べたように、スタックは順序付けられた要素のコレクションであり、追加、操作、および削除はすべて発生します。その最上部では (

Stack(): 空のスタックを作成します。パラメータは必要なく、空のスタックを返します。

push(e): 要素 e をスタック S の先頭に追加します。パラメータ e が必要で、戻り値はありません。
pop(): スタックの最上位にある要素を削除します。パラメータは必要ありませんが、最上位の要素を返し、スタックの内容を変更します。
top(): スタックの先頭にある要素を返しますが、スタックの先頭にある要素は削除しません。スタックが空の場合、この操作は動作します。
is_empty(): スタックに要素が含まれていない場合は、ブール値 True を返します。
size(): スタック内の要素のデータを返します。パラメータは必要なく、整数を返します。 Python では、これは特別なメソッド __len__ を使用して実現できます。

Python 实现栈的几种方式及其优劣 Python スタックのサイズは固定されている場合もあれば、サイズの変更を許可する動的実装がある場合もあります。固定サイズのスタックの場合、すでにいっぱいのスタックに要素を追加しようとすると、スタックオーバーフロー例外が発生します。同様に、

pop()

操作を使用してすでに空のスタックから要素を削除しようとすることをアンダーフローと呼びます。 3. Python リストを使用してスタックを実装する

Python を学習するときは、Python リスト

list

を学習している必要があります。メソッド内スタックの関数を実装します:

append メソッドは、リストの末尾に要素を追加するために使用されます。このメソッドは、push() 操作をシミュレートできます。

pop() メソッドは、ポップ操作をシミュレートするために使用されます。
L[-1] を介して top() 操作をシミュレートします。
len(L)==0 を判定して isEmpty() 操作をシミュレートします。
size() 関数を len() 関数を通じて実装します。

Python 实现栈的几种方式及其优劣コードは以下のように表示されます:

class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.append(e)

def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop()
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[-1]# the last item in the list
arrayStack = ArrayStack()
arrayStack.push("Python")
arrayStack.push("Learning")
arrayStack.push("Hello")
print("Stack top element: ", arrayStack.top())
print("Stack length: ", arrayStack.size())
print("Stack popped item: %s" % arrayStack.pop())
print("Stack is empty?", arrayStack.is_empty())
arrayStack.pop()
arrayStack.pop()
print("Stack is empty?", arrayStack.is_empty())
# arrayStack.pop()

このプログラムを実行すると、結果は次のようになります:

Stack top element:Hello
Stack length:3
Stack popped item: Hello
Stack is empty? False
Stack is empty? True

リストの末尾をスタックの先頭として使用することに加えて、リストの先頭をスタックの先頭として使用することもできます。ただし、この場合、pop() メソッドと append() メソッドを直接使用することはできませんが、pop() メソッドと insert() メソッドを通じて、リストの最初の要素であるインデックス 0 の要素に明示的にアクセスできます。

class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.insert(0, e) 
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop(0)
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[0]# the last item in the list

抽象データ型の実装を変更しましたが、その論理特性は保持しました。この能力は抽象的思考を体現します。どちらのメソッドもスタックを実装していますが、パフォーマンス方法は異なります。

append() メソッドと Pop() メソッドの時間計算量は両方とも *O(1)、*定数レベルの操作#です。

4. collections.deque を使用してスタックを実装する

Python では、コレクションモジュールには両端キューデータ構造 deque があり、append() と Pop も実装されます。 () メソッド:

>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('Apple')
>>> myStack.append('Banana')
>>> myStack.append('Orange')
>>> 
>>> myStack
deque(['Apple', 'Banana', 'Orange'])
>>> myStack.pop()
'Orange'
>>> myStack.pop()
'Banana'
>>>
>>> len(myStack)
1
>>> myStack[0]
'Apple'
>>> myStack.pop()
'Apple'

>>>
>>> myStack.pop()
Traceback (most recent call last):
File "<pyshell#13>", line 1, in <module>
myStack.pop()
IndexError: pop from an empty deque
>>>

リストがあるのに、なぜ deque が必要なのでしょうか?

deque と list が要素に対して同様の操作を行うことがわかると思いますが、Python ではなぜ deque データ構造をリストに追加するのでしょうか?

これは、Python のリストが連続したメモリブロックに構築されているためです。つまり、リストの要素は互いに近くに格納されます。

Python 实现栈的几种方式及其优劣

これは、リストのインデックス作成など、一部の操作では非常に効果的です。 Python はメモリ内のどこを検索すればよいかを正確に認識しているため、myList[3] の取得は高速です。このメモリレイアウトにより、リストでスライスを適切に機能させることもできます。

連続リストのメモリレイアウトにより、一部のオブジェクトの .append() に時間がかかる場合があります。連続メモリブロックがいっぱいの場合は、別のメモリブロックを取得して、最初にメモリブロック全体をコピーする必要があります。このアクションには、通常の .append() 操作よりも時間がかかる場合があります。

Python 实现栈的几种方式及其优劣

両端キューの両端キューは、二重リンクリストに基づいています。リンクされたリスト構造では、各エントリは独自のメモリブロックに格納され、リスト内の次のエントリへの参照を持ちます。

二重リンクリストにも同じことが当てはまりますが、各エントリがリスト内の前後のエントリへの参照を持つ点が異なります。これにより、リストの両端にノードを簡単に追加できます。

リンクリスト構造に新しいエントリを追加するには、新しいエントリの参照が現在のスタックの先頭を指すように設定し、スタックの先頭が新しいエントリを指すようにするだけです。

Python 实现栈的几种方式及其优劣

ただし、スタックへのエントリの追加と削除を絶えず行うこの時間にはコストがかかります。 myDeque[3] の取得は、Python がリストの各ノードをたどって 3 番目の要素を取得する必要があるため、リストよりも遅くなります。

幸いなことに、スタック上の要素にランダムにインデックスを付けたり、リストのスライス操作を実行したりする必要はほとんどありません。スタック上のほとんどの操作はプッシュまたはポップです。

コードでスレッドを使用しない場合、定数時間の .append() および .pop() 操作により、Python スタックの実装には deque がより適切な選択肢になります。

5. queue.LifoQueue を使用してスタックを実装する

Python スタックはマルチスレッドプログラムでも非常に役立ちます。list と deque の 2 つのメソッドについてはすでに学習しました。複数のスレッドからアクセスできるデータ構造の場合、リストはスレッドセーフではないため、マルチスレッドプログラミングでリストを使用すべきではありません。 deque の .append() メソッドと .pop() メソッドはアトミックです。つまり、別のスレッドによって干渉されません。

つまり、deque を使用してスレッドセーフな Python スタックを構築することは可能ですが、そうすると将来の誤用にさらされ、競合状態が発生します。

わかりました。マルチスレッドプログラミングを行っている場合、list をスタックとして使用することはできません。また、おそらく deque をスタックとして使用したくないでしょう。では、Python スタックをビルドするにはどうすればよいですか?スレッド化されたプログラム?

答えはキューモジュール queue.LifoQueue にあります。スタックが後入れ先出し (LIFO) ベースで動作することをどのようにして学んだかを覚えていますか?それが、LifoQueue の「Lifo」部分が表すものです。

list と deque のインターフェイスは似ていますが、LifoQueue は .put() と .get() を使用してスタックにデータを追加したり、スタックからデータを削除したりします。

>>> from queue import LifoQueue
>>> stack = LifoQueue()
>>> stack.put('H')
>>> stack.put('E')
>>> stack.put('L')
>>> stack.put('L')
>>> stack.put('O')
>>> stack
<queue.LifoQueue object at 0x00000123159F7310>
>>> 
>>> stack.get()
'O'
>>> stack.get()
'L'
>>> stack.empty()
False
>>> stack.qsize()
3
>>> stack.get()
'L'
>>> stack.get()
'E'
>>> stack.qsize()
1
>>> stack.get()
'H'
>>> stack.get_nowait()
Traceback (most recent call last):
File "<pyshell#31>", line 1, in <module>
stack.get_nowait()
_queue.Empty
>>> 

>>> stack.put('Apple')
>>> stack.get_nowait()
'Apple'

与 deque 不同，LifoQueue 被设计为完全线程安全的。它的所有方法都可以在线程环境中安全使用。它还为其操作添加了可选的超时功能，这在线程程序中经常是一个必须的功能。

然而，这种完全的线程安全是有代价的。为了实现这种线程安全，LifoQueue 必须在每个操作上做一些额外的工作，这意味着它将花费更长的时间。

通常情况下，这种轻微的减速对你的整体程序速度并不重要，但如果你已经测量了你的性能，并发现你的堆栈操作是瓶颈，那么小心地切换到 deque 可能是值得做的。