DSA 棧

棧

棧是一種可以容納多個元素的資料結構。

將棧想象成一疊煎餅。

在一疊煎餅中，煎餅的新增和移除都在頂部進行。因此，當移除一個煎餅時，它總是你最後新增的那個。這種組織元素的方式稱為 LIFO：後進先出（Last In First Out）。

我們可以在棧上進行的基本操作有：

• Push：向棧中新增一個新元素。
• Pop：移除並返回棧頂的元素。
• Peek：返回棧頂的元素。
• isEmpty：檢查棧是否為空。
• Size：查詢棧中元素的數量。

在上面的棧動畫中，嘗試使用這些基本操作。

棧可以透過陣列或連結串列來實現。

棧可用於實現撤銷機制、恢復到先前狀態、建立圖的深度優先搜尋演算法或回溯。

棧經常與佇列（Queue）一起提及，佇列是下一頁描述的類似資料結構。

使用陣列實現棧

為了更好地理解使用陣列或連結串列實現棧的好處，你應該檢視 本頁面，它解釋了陣列和連結串列如何在記憶體中儲存。

這就是我們使用陣列作為棧時的樣子

使用陣列實現棧的原因

• 記憶體效率高：陣列元素不像連結串列節點那樣儲存下一個元素的地址。
• 易於實現和理解：使用陣列實現棧比使用連結串列需要更少的程式碼，因此通常也更容易理解。

不使用陣列實現棧的原因

• 固定大小：陣列佔用記憶體的固定部分。這意味著它可能會佔用比所需更多的記憶體，或者如果陣列滿了，它就無法容納更多元素。

由於 Python 列表對實現棧所需的功能提供了良好的支援，我們可以用幾行程式碼建立棧並執行棧操作，如下所示：

stack = []

# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack: ", stack)

# Pop
element = stack.pop()
print("Pop: ", element)

# Peek
topElement = stack[-1]
print("Peek: ", topElement)

# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)

# Size
print("Size: ",len(stack))

但是，為了顯式地建立一個具有基本操作的棧資料結構，我們應該建立一個棧類。這種在 Python 中建立棧的方式也更類似於其他程式語言（如 C 和 Java）中建立棧的方式。

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, element):
        self.stack.append(element)
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack.pop()
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack[-1]
    
    def isEmpty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

# Create a stack
myStack = Stack()

myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Stack: ", myStack.stack)

print("Pop: ", myStack.pop())

print("Peek: ", myStack.peek())

print("isEmpty: ", myStack.isEmpty())

print("Size: ", myStack.size())

使用連結串列實現棧

使用連結串列實現棧的原因

• 動態大小：與陣列不同，棧可以動態地增長和收縮。

不使用連結串列實現棧的原因

• 額外的記憶體：每個棧元素必須包含指向下一個元素的地址（下一個連結串列節點）。
• 可讀性：程式碼可能對某些人來說更難閱讀和編寫，因為它更長且更復雜。

這就是如何使用連結串列實現棧。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def push(self, value):
        new_node = Node(value)
        if self.head:
            new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        popped_node = self.head
        self.head = self.head.next
        self.size -= 1
        return popped_node.value
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.head.value
    
    def isEmpty(self):
        return self.size == 0
    
    def stackSize(self):
        return self.size

myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')

print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())

DSA 練習

透過練習來測試自己

練習

下圖代表了一個“棧”資料結構。

對上面的棧執行 peek() 方法，會返回什麼？

提交答案 »

開始練習