logo

TechCodeview

Python でスタックする

あ スタック 項目を格納する線形データ構造です。 後入れ先出し (LIFO) または先入れ後出し (FILO) 方式。スタックでは、新しい要素が一方の端に追加され、要素はその端からのみ削除されます。挿入および削除操作は、プッシュおよびポップと呼ばれることがよくあります。

Pythonでスタックする



スタックに関連付けられた関数は次のとおりです。

  • 空の（） – スタックが空かどうかを返します – 時間計算量: O(1)
  • サイズ（） – スタックのサイズを返します – 時間計算量: O(1)
  • トップ() / ピーク() – スタックの最上位要素への参照を返します – 時間計算量: O(1)
  • プッシュ(a) – スタックの先頭に要素「a」を挿入 – 時間計算量: O(1)
  • ポップ（） – スタックの最上位要素を削除 – 時間計算量: O(1)

実装：

Python でスタックを実装するにはさまざまな方法があります。この記事では、Python ライブラリのデータ構造とモジュールを使用したスタックの実装について説明します。
Python のスタックは、次の方法を使用して実装できます。

  • リスト
  • Collections.deque
  • キュー.LifoQueue

リストを使用した実装:

Python の組み込みデータ構造リストをスタックとして使用できます。 Push() の代わりに、append() を使用してスタックの先頭に要素を追加し、pop() が LIFO 順序で要素を削除します。
残念ながら、このリストにはいくつかの欠点があります。最大の問題は、成長するにつれて速度の問題に遭遇する可能性があることです。リスト内の項目はメモリ内に並べて保存されます。スタックが現在保持しているメモリ ブロックよりも大きくなった場合、Python はメモリの割り当てを行う必要があります。これにより、一部の append() 呼び出しが他の呼び出しよりも大幅に時間がかかる可能性があります。



パイソン 
# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>
出力 
Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

collections.deque を使用した実装:

Python スタックは、コレクション モジュールの deque クラスを使用して実装できます。コンテナの両端からの追加およびポップ操作を迅速に行う必要がある場合は、リストよりも Deque の方が優先されます。これは、O(n) を提供するリストと比較して、deque の追加およびポップ操作の時間計算量が O(1) であるためです。時間の複雑さ。

リストにあるのと同じ deque メソッド、append() および Pop() が使用されます。

パイソン 
# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>
出力 
Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

キューモジュールを使用した実装

キュー モジュールには、基本的にスタックである LIFO キューもあります。データは put() 関数を使用してキューに挿入され、get() はキューからデータを取り出します。



このモジュールではさまざまな機能が使用できます。

  • 最大サイズ – キュー内で許可される項目の数。
  • 空の（） – キューが空の場合は True を返し、それ以外の場合は False を返します。
  • 満杯（） – 存在する場合は True を返します 最大サイズ キュー内のアイテム。キューが maxsize=0 (デフォルト) で初期化された場合、full() は True を返しません。
  • 得る（） – キューからアイテムを削除して返します。キューが空の場合は、アイテムが使用可能になるまで待ちます。
  • get_nowait() – すぐに利用できる場合は項目を返し、それ以外の場合は QueueEmpty を発生させます。
  • 置く(アイテム) – アイテムをキューに入れます。キューがいっぱいの場合は、空きスロットが利用可能になるまで待ってから項目を追加します。
  • put_nowait(アイテム) – ブロックせずにアイテムをキューに入れます。すぐに使用できる空きスロットがない場合は、QueueFull を上げます。
  • qsize() – キュー内の項目の数を返します。
パイソン 
# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>
出力 
0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

単一リンクリストを使用した実装:

リンク リストには、定数時間で実行される 2 つのメソッド addHead(item) と RemoveHead() があります。これら 2 つの方法はスタックの実装に適しています。

  • getSize() – スタック内の項目の数を取得します。
  • isEmpty() – スタックが空の場合は True を返し、それ以外の場合は False を返します。
  • ピーク（） – スタックの一番上の項目を返します。スタックが空の場合は例外を発生させます。
  • プッシュ(値) – 値をスタックの先頭にプッシュします。
  • ポップ（） – スタックの先頭の値を削除して返します。スタックが空の場合は例外を発生させます。

上記のアプローチの実装を以下に示します。

パイソン 
# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # 現在のスタックのサイズを取得する def getSize(self): return self.size # スタックが空かどうかを確認する def isEmpty(self): return self.size = = 0 # スタックの最上位項目を取得します def Peak(self): # 空のスタックを # ピークしているかどうかを確認するための衛生チェック。 if self.isEmpty(): return None return self.head.next.value # 値をスタックにプッシュします。 def Push(self, value): node = Node(value) node.next = self.head.next # 新しいノードが現在のヘッドを指すようにします self.head.next = node #!!! # ヘッドを新しいノードになるように更新します self.size += 1 # スタックから値を削除して戻ります。 def Pop(self): if self.isEmpty(): raise Exception('空のスタックからのポップ') Remove = self.head.next self.head.next = Remove.next #!!!変更された self.size -= 1 return Remove.value # ドライバー コード if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Stack: {stack}') for _ in range(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # 変数名が変更されました print(f'Stack: {スタック}')>>' 
    出力    
 スタックは、明確に定義された一連の操作を備えたシンプルなデータ構造であるため、理解しやすく、使いやすくなっています。
  • 要素の追加と削除には、これらの操作の時間計算量が O(1) であるため、スタックは効率的です。
  • 要素の順序を逆にするために、スタック データ構造を使用します。
  • スタックを使用して、アプリケーションに元に戻す/やり直し機能を実装できます。
    •     スタックの欠点:    
    • スタックのサイズ制限は欠点であり、スタックがいっぱいになると、それ以上要素をスタックに追加できなくなります。
    • スタックでは、最上位要素以外の要素への高速アクセスは提供されません。
    • 探している要素が見つかるまで要素を 1 つずつポップする必要があるため、スタックでは効率的な検索はサポートされていません。