Python棧和隊列怎么實現

Python棧和隊列怎么實現

在計算機科學中，棧（Stack）和隊列（Queue）是兩種非常重要的數據結構。它們都是線性數據結構，但在數據的插入和刪除操作上有著不同的規則。本文將詳細介紹如何在Python中實現棧和隊列，并探討它們的應用場景。

1. 棧（Stack）

1.1 棧的基本概念

棧是一種遵循后進先出（LIFO, Last In First Out）原則的數據結構。這意味著最后一個被添加到棧中的元素將是第一個被移除的元素。棧的操作主要包括：

• push：將元素添加到棧的頂部。
• pop：移除并返回棧頂的元素。
• peek：返回棧頂的元素但不移除它。
• is_empty：檢查棧是否為空。
• size：返回棧中元素的數量。

1.2 Python實現棧

在Python中，?？梢酝ㄟ^列表（List）來實現。列表的append()方法可以用于實現push操作，而pop()方法可以用于實現pop操作。

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]

    def size(self):
        return len(self.items)

    def __str__(self):
        return str(self.items)

1.3 棧的應用場景

棧在計算機科學中有廣泛的應用，例如：

• 函數調用棧：在程序執行過程中，函數調用的順序是通過棧來管理的。
• 表達式求值：?？梢杂糜诮馕龊陀嬎銛祵W表達式，如中綴表達式轉后綴表達式。
• 括號匹配：?？梢杂糜跈z查代碼中的括號是否匹配。
• 撤銷操作：許多編輯器使用棧來實現撤銷操作。

1.4 示例：使用棧實現括號匹配

def is_balanced(expression):
    stack = Stack()
    for char in expression:
        if char in "({[":
            stack.push(char)
        elif char in ")}]":
            if stack.is_empty():
                return False
            top = stack.pop()
            if not matches(top, char):
                return False
    return stack.is_empty()

def matches(open, close):
    opens = "({["
    closes = ")}]"
    return opens.index(open) == closes.index(close)

# 測試
print(is_balanced("({[]})"))  # True
print(is_balanced("({[}])"))  # False

2. 隊列（Queue）

2.1 隊列的基本概念

隊列是一種遵循先進先出（FIFO, First In First Out）原則的數據結構。這意味著第一個被添加到隊列中的元素將是第一個被移除的元素。隊列的操作主要包括：

• enqueue：將元素添加到隊列的末尾。
• dequeue：移除并返回隊列的第一個元素。
• peek：返回隊列的第一個元素但不移除它。
• is_empty：檢查隊列是否為空。
• size：返回隊列中元素的數量。

2.2 Python實現隊列

在Python中，隊列可以通過列表（List）來實現。列表的append()方法可以用于實現enqueue操作，而pop(0)方法可以用于實現dequeue操作。然而，使用pop(0)會導致性能問題，因為每次刪除第一個元素時，列表中的所有元素都需要向前移動。

為了提高性能，可以使用collections.deque來實現隊列。deque是一個雙端隊列，支持在兩端高效地添加和刪除元素。

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self.items[0]

    def size(self):
        return len(self.items)

    def __str__(self):
        return str(self.items)

2.3 隊列的應用場景

隊列在計算機科學中也有廣泛的應用，例如：

• 任務調度：操作系統使用隊列來管理進程的調度。
• 打印隊列：打印機使用隊列來管理打印任務。
• 消息隊列：在分布式系統中，消息隊列用于在不同服務之間傳遞消息。
• 廣度優先搜索（BFS）：在圖算法中，隊列用于實現廣度優先搜索。

2.4 示例：使用隊列實現廣度優先搜索

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def bfs(self, start):
        visited = set()
        queue = Queue()
        queue.enqueue(start)
        visited.add(start)

        while not queue.is_empty():
            vertex = queue.dequeue()
            print(vertex, end=" ")

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    queue.enqueue(neighbor)
                    visited.add(neighbor)

# 測試
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("廣度優先搜索 (從頂點 2 開始):")
g.bfs(2)

3. 棧與隊列的比較

3.1 操作對比

3.2 應用場景對比

4. 總結

棧和隊列是兩種基本的數據結構，它們在計算機科學中有著廣泛的應用。棧遵循后進先出（LIFO）的原則，適用于需要回溯操作的場景，如函數調用、表達式求值和括號匹配。隊列遵循先進先出（FIFO）的原則，適用于需要按順序處理任務的場景，如任務調度、打印隊列和廣度優先搜索。

在Python中，?？梢酝ㄟ^列表（List）來實現，而隊列則可以通過collections.deque來實現。選擇合適的實現方式可以提高代碼的性能和可讀性。

通過本文的介紹，希望讀者能夠理解棧和隊列的基本概念，并能夠在實際編程中靈活運用這兩種數據結構。