Python 堆疊資料結構教程

Implement a LIFO stack in Python.運行我們的互動式堆疊程式碼範例來掌握推送、彈出、檢視和容量限制。

概述

堆疊是一種遵循後進先出 (LIFO) 原則的線性資料結構。這意味著添加到堆疊中的最後一個元素是第一個被刪除的元素，類似於一堆盤子。

堆疊支援兩種主要操作：入棧（將項目新增至頂部）和彈出（刪除最近新增的項目）。此外，查看或頂部操作允許檢查頂部元素而不將其移除。

In Python, stacks can be easily built using a list with `.append()` and `.pop()` methods, or by using the `collections.deque` object which offers optimized double-ended queue operations in O(1) time.

程式碼和執行輸出

使用 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']

逐步實施

Managing undo functions in software systems
編譯器中的語法分析和括號檢查
在引擎中遞歸期間追蹤執行呼叫堆疊

常見問題解答

為什麼對於 Stacks 來說，collections.deque 比普通清單更受歡迎？

雖然列表很方便，但它們實際上是動態數組。當它們調整大小時，記憶體重新分配可能需要 O(n) 時間。 deque 物件使用雙向鍊錶架構，確保 O(1) 的推送和彈出。

Python 中的棧會溢位嗎？

Python 中使用列表數組的標準堆疊類別將不斷增長，直到耗盡所有可用的系統記憶體。然而，Python 中的遞歸堆疊有一個預設限制（通常為 1000），以防止無限循環導致解釋器崩潰。