棧和隊列的主要區別

一、棧和隊列的基本介紹

棧（Stack）和隊列（Queue）是兩種經典的數據結構，用於在計算機程序中存儲和管理數據。棧是一種後進先出（LIFO）的數據結構，只允許在棧頂進行插入和刪除操作。隊列是一種先進先出（FIFO）的數據結構，只允許在隊列尾部進行插入操作，在隊列頭部進行刪除操作。

下面是棧和隊列的簡單Python代碼實現：

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

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

    def pop(self):
        return self.items.pop()

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

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

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

    def dequeue(self):
        return self.items.pop(0)

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

二、基本操作的差異

棧和隊列的主要區別在於它們的基本操作。在棧中，元素的插入和刪除只能在棧頂進行，而隊列中元素的插入只能在隊列尾部進行，刪除操作則只能在隊列頭部進行。這意味著在棧中最後插入的元素會被最先刪除，而在隊列中最先插入的元素會被最先刪除。

下面是分別實現了棧和隊列的基本操作代碼：

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

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

    def pop(self):
        return self.items.pop()

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


# 隊列
class Queue:
    def __init__(self):
        self.items = []

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

    def dequeue(self):
        return self.items.pop(0)

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

三、性能差異

棧和隊列的另一個主要區別是它們的性能差異。在棧中，插入和刪除操作的時間複雜度都是O(1)，因為只需要操作棧頂的元素。而在隊列中，插入操作的時間複雜度也是O(1)，但刪除操作的時間複雜度為O(n)，因為需要將所有的元素向前移動一位。

下面是分別實現了棧和隊列的性能比較代碼：

import time

# 棧
s = Stack()
start = time.time()
for i in range(1000000):
    s.push(i)
while not s.is_empty():
    s.pop()
end = time.time()
print("Time used for Stack:", end-start)

# 隊列
q = Queue()
start = time.time()
for i in range(1000000):
    q.enqueue(i)
while not q.is_empty():
    q.dequeue()
end = time.time()
print("Time used for Queue:", end-start)

四、應用場景的不同

棧和隊列在不同的應用場景中有不同的用途。棧通常用於處理遞歸和回溯問題，以及表達式的計算和括弧匹配。隊列則常用於解決如廣度優先搜索（BFS）等問題。同時，隊列還常被用於實現具有緩衝區的數據傳輸。

下面是棧和隊列分別應用於表達式括弧匹配的代碼實現：

# 棧應用：表達式括弧匹配
def is_balanced(expr):
    s = Stack()
    for char in expr:
        if char in ['(', '[', '{']:
            s.push(char)
        elif char in [')', ']', '}']:
            if s.is_empty():
                return False
            top = s.pop()
            if not is_match(top, char):
                return False
    return s.is_empty()

def is_match(p1, p2):
    return (p1 == '(' and p2 == ')') or (p1 == '[' and p2 == ']') or (p1 == '{' and p2 == '}')

print(is_balanced("(Pangolin)[Python]"))  # True
print(is_balanced("{Python(Jupyter)}[Java]"))  # True
print(is_balanced("({Python][Jupyter)}"))  # False

# 隊列應用：BFS實現圖的遍歷
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')
# 輸出：A B C D E F