Python スタックデータ構造のチュートリアル

Python で LIFO スタックを実装します。インタラクティブなスタックコード例を実行して、プッシュ、ポップ、ピーク、容量制限をマスターします。

概要

スタックは、後入れ先出し (LIFO) 原則に従う線形データ構造です。これは、プレートのスタックと同様に、スタックに追加された最後の要素が最初に削除される要素であることを意味します。

スタックは、プッシュ (項目を先頭に追加) とポップ (最後に追加された項目を削除) という 2 つの主な操作をサポートします。さらに、ピークまたはトップ操作を使用すると、トップ要素を削除せずに検査できます。

Python では、`.append()` および `.pop()` メソッドを含むリストを使用するか、O(1) 時間で最適化された両端キュー操作を提供する `collections.deque` オブジェクトを使用して、スタックを簡単に構築できます。

コードと実行の出力

Python のリスト構造を使用してプッシュ、ポップ、ピーク関数をエミュレートするカスタムスタック実装。

stack.py

エディターで試してみる

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
        
    def push(self, item):
        self.items.append(item)
        print(f"Pushed: {item}")
        
    def pop(self):
        if self.is_empty():
            return "Underflow: Stack is empty"
        popped = self.items.pop()
        print(f"Popped: {popped}")
        return popped
        
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]
        
    def size(self):
        return len(self.items)

# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")

print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")

stack.pop()
print(f"Stack after Pop: {stack.items}")

端子出力

Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']

段階的な実装

ソフトウェアシステムでの元に戻す機能の管理
コンパイラでの構文解析と括弧チェック
エンジンでの再帰中の実行コールスタックの追跡

よくある質問

スタックの通常のリストよりも collections.deque が優先されるのはなぜですか?

リストは便利ですが、内部では動的配列です。サイズを変更すると、メモリの再割り当てに O(n) 時間がかかることがあります。 deque オブジェクトは二重リンクリストアーキテクチャを使用し、O(1) のプッシュとポップを保証します。

Python ではスタックがオーバーフローする可能性がありますか?

リスト配列を使用する Python の標準スタッククラスは、利用可能なシステムメモリをすべて消費するまで増大します。ただし、Python の再帰スタックには、無限ループによるインタープリターのクラッシュを防ぐためのデフォルトの制限 (通常は 1000) があります。

Python スタック データ構造のチュートリアル

概要