作者: /
maze, solution, decisions-8436684.jpg

用C++與Python實作Stack 和 Queue, BFS與DFS

在這篇文章中，我們將探討如何在 C++ 中實作 Stack（堆疊）和 Queue（佇列）。這些資料結構將能幫助我們管理資訊。本文將提供詳細的解說和一些實例來幫助您更好地理解這些概念。

什麼是 Stack？

Stack 是一種後進先出（LIFO, Last In First Out）的資料結構。也就是說，最後加入的元素會最先被取出。這個特性使得 Stack 特別適合用於一些特定的應用，如函數呼叫管理、括號匹配等。

Stack 的基本操作

  • push：將元素加入堆疊頂端。
  • pop：移除並返回堆疊頂端的元素。
  • top：返回堆疊頂端的元素，但不移除它。
  • empty：檢查堆疊是否為空。

Stack 的 C++ 實作

我們可以使用 C++ 標準模板庫（STL）中的 stack 容器來實作堆疊。以下是一個簡單的例子：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;

    // push 操作
    stack.push(10);
    stack.push(20);
    stack.push(30);

    // top 操作
    std::cout << "Stack top: " << stack.top() << std::endl;

    // pop 操作
    stack.pop();
    std::cout << "Stack top after pop: " << stack.top() << std::endl;

    // empty 操作
    if (stack.empty()) {
        std::cout << "Stack is empty" << std::endl;
    } else {
        std::cout << "Stack is not empty" << std::endl;
    }

    return 0;
}

我們首先將三個整數推入堆疊，然後使用 top 操作查看頂端元素，接著使用 pop 移除頂端元素，最後檢查堆疊是否為空。

什麼是 Queue？

Queue 是一種先進先出（FIFO, First In First Out）的資料結構。也就是說，最先加入的元素會最先被取出。Queue 常用於排隊系統、任務排程等應用。

Queue 的基本操作

  • enqueue (push)：將元素加入佇列末尾。
  • dequeue (pop)：移除並返回佇列前端的元素。
  • front：返回佇列前端的元素，但不移除它。
  • empty：檢查佇列是否為空。

Queue 的 C++ 實作

我們可以使用 C++ 標準模板庫（STL）中的 queue 容器來實作佇列。以下是一個簡單的例子：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> queue;

    // enqueue 操作
    queue.push(10);
    queue.push(20);
    queue.push(30);

    // front 操作
    std::cout << "Queue front: " << queue.front() << std::endl;

    // dequeue 操作
    queue.pop();
    std::cout << "Queue front after pop: " << queue.front() << std::endl;

    // empty 操作
    if (queue.empty()) {
        std::cout << "Queue is empty" << std::endl;
    } else {
        std::cout << "Queue is not empty" << std::endl;
    }

    return 0;
}

我們將三個整數加入佇列，然後使用 front 操作查看前端元素，接著使用 pop 移除前端元素，最後檢查佇列是否為空。

Python 版本的 Stack 和 Queue 實作

除了在 C++ 中實作 Stack 和 Queue，我們也可以使用 Python 來實現這些資料結構。Python 提供了非常簡便的方式來處理這些資料結構。

Python 中的 Stack 實作

在 Python 中，我們可以使用內建的 list 來實作堆疊。list 提供了 append 和 pop 方法，分別對應於堆疊的 push 和 pop 操作。

Stack 的 Python 實作範例

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

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

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

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

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

# 使用範例
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print("Stack top:", stack.top())  # Stack top: 30
stack.pop()
print("Stack top after pop:", stack.top())  # Stack top after pop: 20
print("Is stack empty?", stack.is_empty())  # Is stack empty? False

Python 中的 Queue 實作

在 Python 中，我們可以使用 collections 模組中的 deque 來實作佇列。deque 提供了 append 和 popleft 方法，分別對應於佇列的 enqueue 和 dequeue 操作。

Queue 的 Python 實作範例

from collections import deque

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

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

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

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

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

# 使用範例
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print("Queue front:", queue.front())  # Queue front: 10
queue.dequeue()
print("Queue front after dequeue:", queue.front())  # Queue front after dequeue: 20
print("Is queue empty?", queue.is_empty())  # Is queue empty? False

例題：使用 BFS 和 Queue 解決迷宮問題

在這個例題中，我們將探討如何使用廣度優先搜索（BFS）和佇列（Queue）來解決一個迷宮問題。目標是找到從迷宮起點到終點的最短路徑。

問題描述

給定一個迷宮，由一個二維矩陣表示，其中 0 表示可以通行的路徑，1 表示牆壁或障礙物。您需要從起點（左上角）到終點（右下角）找到一條最短的路徑。如果無法到達終點，則返回 -1。

迷宮範例如下：

迷宮：
0 0 1 0
1 0 1 0
1 0 0 0
0 1 1 0

起點在 (0, 0)，終點在 (3, 3)。

解法：使用 BFS 和 Queue

我們可以使用廣度優先搜索（BFS）來解決這個問題，因為 BFS 能夠保證在找到終點時所經過的路徑是最短的。以下是 Python 實作範例：

Python 程式碼

from collections import deque

def shortest_path_in_maze(maze):
    if not maze or not maze[0]:
        return -1

    rows, cols = len(maze), len(maze[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
    queue = deque([(0, 0, 0)])  # (行, 列, 步數)
    visited = set((0, 0))

    while queue:
        r, c, steps = queue.popleft()

        # 如果到達終點，返回步數
        if r == rows - 1 and c == cols - 1:
            return steps

        # 探索四個方向
        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            # 確認新位置在迷宮內且可通行且未訪問過
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))

    # 如果無法到達終點，返回 -1
    return -1

# 測試範例
maze = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [1, 0, 0, 0],
    [0, 1, 1, 0]
]

print(shortest_path_in_maze(maze))  # 輸出: 7

程式碼解析

  1. 初始化：
    • 使用 deque 來初始化佇列，起點為 (0, 0)，初始步數為 0。
    • 使用 set 來追蹤已訪問過的位置。
  2. BFS 遍歷：
    • 從佇列中取出當前位置和步數。
    • 檢查是否到達終點，如果到達，返回步數。
    • 探索當前位置的四個鄰近方向，確保新位置在迷宮內、可通行且未訪問過，然後加入佇列並標記為已訪問。
  3. 結束條件：
    • 如果佇列空了仍未找到終點，返回 -1，表示無法到達終點。

例題：使用 DFS 和Stack解決島嶼計數問題

在這個例題中，我們將探討如何使用深度優先搜索（DFS）來解決島嶼計數問題。給定二維矩陣中島嶼的數量，其中 1 表示陸地，0 表示水域。島嶼由水平或垂直相鄰的陸地組成。

問題描述

給定一個二維矩陣，其中：

  • 1 表示陸地。
  • 0 表示水域。

計算出矩陣中島嶼的數量。島嶼是由相連的 1 組成的區塊（只考慮水平和垂直方向）。

範例如下：

矩陣：
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 1 1

在這個範例中，有 3 個島嶼。

解法：使用 DFS 計數島嶼

我們可以使用 DFS 來遍歷整個矩陣，並在遇到 1 時啟動一次 DFS，將該島嶼的所有陸地標記為已訪問過，然後計數。

Python 程式碼（使用遞迴的 DFS）

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def dfs(r, c):
        stack = [(r, c)]
        while stack:
            row, col = stack.pop()
            if (row, col) not in visited:
                visited.add((row, col))
                # 探索四個方向
                for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1' and (nr, nc) not in visited:
                        stack.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                islands += 1

    return islands

# 測試範例
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "1"],
    ["0", "0", "0", "1", "1"],
    ["0", "0", "0", "0", "0"],
    ["1", "0", "1", "1", "1"]
]

print(num_islands(grid))  # 輸出: 3

Python 程式碼（使用遞迴的 DFS）

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols or
                grid[r][c] == '0' or (r, c) in visited):
            return
        visited.add((r, c))
        # 探索四個方向
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                islands += 1

    return islands

# 測試範例
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "1"],
    ["0", "0", "0", "1", "1"],
    ["0", "0", "0", "0", "0"],
    ["1", "0", "1", "1", "1"]
]

print(num_islands(grid))  # 輸出: 3

程式碼解析

  1. 初始化：
    • 檢查矩陣是否為空。
    • 獲取矩陣的行數和列數，並初始化一個集合來追蹤已訪問的位置。
    • 設置 islands 計數器。
  2. DFS 遍歷（使用遞迴或堆疊）：
    • 使用遞迴方式，從當前位置向四個方向遞迴搜索相連的 1，並將訪問過的位置加入 visited。
    • 使用堆疊方式，將起始位置壓入堆疊，迭代地從堆疊中彈出位置並搜索相連的 1。
  3. 計數島嶼：
    • 遍歷整個矩陣，當遇到一個新的 1 且未訪問過時，啟動一次 DFS，並增加 islands 計數。
  4. 返回結果：
    • 返回計數的島嶼數量。

Back to Blog

Related Posts

返回頂端