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

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

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

https://ost.51cto.com

1. スタックの概念

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

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

## スタックの実用的な応用

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

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

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

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

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

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

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

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

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

pop()

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

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

list

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

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

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

コードは以下のように表示されます:

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)、*定数レベルの操作#です。
##2 番目の実装のパフォーマンスは、スタック内の要素の数によって制限されます。これは、insert(0) と Pop(0) の時間計算量が O(n) であるためです。要素が多いほど、遅くなります。

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 はメモリ内のどこを検索すればよいかを正確に認識しているため、myList[3] の取得は高速です。このメモリ レイアウトにより、リストでスライスを適切に機能させることもできます。

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

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

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

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

ただし、スタックへのエントリの追加と削除を絶えず行うこの時間にはコストがかかります。 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 可能是值得做的。

六、选择哪一种实现作为栈

一般来说，如果你不使用多线程，你应该使用 deque。如果你使用多线程，那么你应该使用 LifoQueue，除非你已经测量了你的性能，发现 push 和 pop 的速度的小幅提升会带来足够的差异，以保证维护风险。

你可以对列表可能很熟悉，但需要谨慎使用它，因为它有可能存在内存重新分配的问题。deque 和 list 的接口是相同的，而且 deque 没有线程不安全问题。

七、总结

本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中如何使用它的情况。在文章的中，介绍了 Python 中实现栈的三种不同方式，知道了 deque 对于非多线程程序是一个更好的选择，如果你要在多线程编程环境中使用栈的话，可以使用 LifoQueue。

​​想了解更多关于开源的内容，请访问：​​

​​51CTO 开源基础软件社区​​

​​https://ost.51cto.com​​。

以上がPython でスタックを実装するいくつかの方法とその利点と欠点の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。