1. Các ứng dụng thực tế phổ biến

• Ứng dụng của Stack:

  • Thao tác Undo / Redo trong các phần mềm soạn thảo văn bản (lưu lại lịch sử thay đổi).

  • Lịch sử duyệt web (Back / Forward nút trên browser).

  • Quản lý Call Stack trong hệ điều hành & ngôn ngữ lập trình khi gọi hàm đệ quy.

  • Trình biên dịch: Kiểm tra tính hợp lệ của dấu ngoặc đóng/mở trong cú pháp code.

• Ứng dụng của Queue:

  • Quản lý tiến trình trong Hệ điều hành (CPU Task Scheduling).

  • Bộ đệm dữ liệu (Buffer) trong truyền dữ liệu mạng hoặc streaming video.

  • Thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth First Search).

2. Bài toán Kinh điển: Kiểm tra Chuỗi ngoặc Hợp lệ (Valid Parentheses)

Phát biểu bài toán:

Cho một chuỗi chỉ chứa các ký tự ngoặc (), {}, []. Hãy kiểm tra chuỗi đó có hợp lệ hay không.

Một chuỗi ngoặc hợp lệ khi:

1. Ngoặc mở phải được đóng bởi ngoặc cùng loại.

2. Ngoặc mở phải được đóng theo đúng thứ tự.

Ví dụ:

• "({[]})" $\rightarrow$ Hợp lệ (True)

• "([)]" $\rightarrow$ Không hợp lệ (False) (ngoặc ] bị đóng sai vị trí)

Giải thuật sử dụng Stack:

• Duyệt từng ký tự trong chuỗi:

  • Nếu là ngoặc mở (, {, [ $\rightarrow$ Push vào Stack.

  • Nếu là ngoặc đóng ), }, ] $\rightarrow$ Pop phần tử đỉnh Stack ra so sánh. Nếu không khớp loại hoặc Stack đang rỗng $\rightarrow$ Trả về False.

• Kết thúc chuỗi, nếu Stack rỗng $\rightarrow$ Trả về True.

def is_valid_parentheses(s: str) -> bool:
    stack = []
    # Ánh xạ ngoặc đóng -> ngoặc mở tương ứng
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping:
            # Lấy phần tử đỉnh stack nếu stack không rỗng
            top_element = stack.pop() if stack else "#"
            if mapping[char] != top_element:
                return False
        else:
            # Nếu là ngoặc mở, đẩy vào stack
            stack.append(char)

    # Nếu stack rỗng tức là tất cả ngoặc mở đều đã được đóng hợp lệ
    return len(stack) == 0


# Kiểm thử
print(is_valid_parentheses("({[]})"))  # Output: True
print(is_valid_parentheses("([)]"))  # Output: False

• Độ phức tạp thời gian: $O(N)$ (duyệt qua chuỗi đúng 1 lần).

• Độ phức tạp bộ nhớ: $O(N)$ (trường hợp xấu nhất Stack lưu toàn bộ $N$ ngoặc mở).

BÀI TẬP 

Bài tập 1: Phân tích Tư duy Cấu trúc

Hệ thống xử lý đơn hàng tự động của một trang thương mại điện tử tiếp nhận hàng nghìn đơn mua từ khách hàng cùng lúc. Hệ thống cần đảm bảo đơn nào gửi trước sẽ được xử lý đóng gói và giao trước.

1. Cấu trúc dữ liệu nào (Stack hay Queue) là lựa chọn chính xác cho tính năng này? Vì sao?

2. Nếu bổ sung thêm tính năng: "Cho phép người dùng hoàn tác (Cancel) thao tác đặt hàng vừa bấm trong vòng 5 giây", thao tác hoàn tác này nên được lưu trữ bằng cấu trúc dữ liệu nào?

Bài tập 2: Thử thách Cài đặt Thuật toán (Thực hành Code)

Dựa vào nguyên lý LIFO của Stack, hãy viết một hàm Python reverse_string(text: str) -> str nhận vào một chuỗi ký tự và trả về chuỗi đó theo chiều ngược lại.

Ví dụ: reverse_string("DSA") $\rightarrow$ "ASD"

(Yêu cầu: Cài đặt bằng cách push từng ký tự vào Stack, sau đó pop ra để ghép thành chuỗi mới).