Cấu trúc dữ liệu và Giải thuật Bài 36: Hàng đợi (Queue): Nguyên lý FIFO và các ứng dụng hàng ngày.

Nếu Stack đại diện cho sự "đóng gói" và truy xuất ngược, thì Hàng đợi (Queue) sinh ra để bảo vệ sự công bằng và tính tuần tự. Bất cứ khi nào hệ thống của bạn phải đối mặt với một lưu lượng yêu cầu (requests) ập đến cùng lúc vượt quá khả năng xử lý tức thời của CPU hay Database, Queue chính là bộ đệm hoàn hảo để giữ cho hệ thống không bị sụp đổ.

1. Nguyên lý FIFO (First-In-First-Out)

Queue hoạt động dựa trên quy luật tự nhiên nhất của xã hội loài người: Vào trước, Ra trước (First-In-First-Out).

Lấy bối cảnh tại cổng soát vé tự động (AFC) của tuyến Metro Line 1. Khi một đoàn tàu vừa cập bến và hàng trăm hành khách cùng ùa ra quẹt thẻ, hệ thống cửa xoay không thể mở nắp cho tất cả cùng lúc. Hành khách nào chạm thẻ vào đầu đọc trước sẽ được xác thực và mở cửa trước. Hành khách đến sau bắt buộc phải xếp hàng chờ ở phía sau.

Trong thuật ngữ của Queue:

• Điểm hành khách bước vào xếp hàng gọi là Rear (Đuôi).

• Điểm hành khách quẹt thẻ và đi qua cửa xoay gọi là Front (Đầu).

  Dòng chảy dữ liệu chỉ di chuyển theo đúng một hướng duy nhất: Đi vào từ Đuôi và đi ra từ Đầu.

2. Các thao tác API cốt lõi

Tương tự như Stack, Queue giấu đi toàn bộ sự phức tạp bên trong và chỉ cung cấp các giao diện cực kỳ tinh gọn, đảm bảo mọi thao tác đều diễn ra trong $O(1)$:

1. Enqueue (Xếp hàng): Thêm một phần tử mới vào vị trí Rear (Đuôi).

2. Dequeue (Rời hàng): Lấy phần tử đang đứng ở vị trí Front (Đầu) ra khỏi hàng đợi để xử lý.

3. Front / Peek (Xem trước): Đọc giá trị của phần tử đang đứng ở Đầu hàng mà không bốc nó ra.

4. IsEmpty (Kiểm tra rỗng): Kiểm tra xem hàng đợi có còn ai không trước khi gọi lệnh Dequeue, nhằm tránh lỗi hệ thống.

3. Nỗi đau của việc triển khai Queue bằng Mảng tĩnh

Chúng ta có thể dễ dàng dùng một mảng (Array) để mô phỏng Queue. Tuy nhiên, thao tác Dequeue sẽ bộc lộ một điểm yếu vật lý chí mạng.

Giả sử mảng đang là [A, B, C, D]. A đang ở Front (index 0).

Khi bạn Dequeue A, ô nhớ index 0 bị trống. Để giữ đúng bản chất mảng liên tục và vị trí Front luôn ở index 0, toàn bộ các phần tử B, C, D phải được dịch chuyển (Shift) lên trước một ô: [B, C, D, _].

Sự dịch chuyển này tiêu tốn thời gian $O(n)$. Nếu hàng đợi mua hàng flash sale của Hasaki có 100.000 người, chỉ một người thanh toán xong ở quầy số 1, server phải dịch chuyển 99.999 bản ghi còn lại trong bộ nhớ. CPU sẽ quá tải ngay lập tức.

Để thao tác Dequeue đạt $O(1)$, chúng ta có hai hướng giải quyết trong thực tế:

1. Sử dụng Danh sách liên kết (Linked List): Xóa Node ở Head và Thêm Node ở Tail (cả hai đều $O(1)$).

2. Sử dụng Mảng động (Slice) với hai con trỏ ảo, chấp nhận lãng phí một chút bộ nhớ trước khi dọn dẹp.

4. Triển khai Queue siêu tốc bằng Golang (Slice + 2 Pointers)

Để tránh việc phải dịch chuyển mảng $O(n)$ mỗi lần Dequeue, các kỹ sư Backend Golang thường dùng một Slice nhưng không xóa hẳn phần tử vật lý ngay lập tức, mà chỉ trượt con trỏ head lên phía trước.

Go

type Queue struct {
    items []int
    head  int // Con trỏ trỏ đến vị trí Front hiện tại
}

func (q *Queue) Enqueue(data int) {
    q.items = append(q.items, data) // Push vào cuối Slice (Rear) -> O(1) Amortized
}

func (q *Queue) Dequeue() (int, bool) {
    if q.IsEmpty() {
        return 0, false
    }
    
    // Lấy dữ liệu ở vị trí Head
    frontValue := q.items[q.head]
    
    // Trượt con trỏ Head lên 1 nhịp thay vì dịch chuyển toàn bộ mảng -> O(1)
    q.head++
    
    // [Tối ưu Memory Leak]: Dọn rác khi mảng rỗng
    if q.head == len(q.items) {
        // Reset lại Slice và con trỏ khi tất cả đã được Dequeue
        // Giúp giải phóng bộ nhớ cho Garbage Collector
        q.items = nil 
        q.head = 0
    }
    
    return frontValue, true
}

func (q *Queue) Front() (int, bool) {
    if q.IsEmpty() {
        return 0, false
    }
    return q.items[q.head], true
}

func (q *Queue) IsEmpty() bool {
    // Rỗng khi con trỏ head chạy đuổi kịp kích thước của Slice
    return q.head == len(q.items)
}

5. Ứng dụng định hình Kiến trúc Hệ thống

Queue không chỉ là một cấu trúc dữ liệu trên RAM, nó đã tiến hóa thành các hệ thống phần mềm độc lập (Message Brokers) khổng lồ:

• Message Queue (RabbitMQ / Kafka / Redis Pub/Sub): Trong kiến trúc Microservices, khi người dùng đặt hàng trên ứng dụng e-commerce, Service Đơn hàng sẽ không gọi trực tiếp sang Service Gửi Email (nếu email server sập, toàn bộ tiến trình sẽ treo). Thay vào đó, nó Enqueue một "Nhiệm vụ gửi Email" vào RabbitMQ. Các Worker (chạy bằng Go hoặc PHP Laravel) sẽ từ từ Dequeue từng nhiệm vụ ra để xử lý. Dù có 1 triệu đơn hàng cùng lúc, hệ thống không bao giờ sập, nó chỉ xử lý chậm lại.

• Bộ đệm phần cứng (Hardware Buffer): Bàn phím máy tính của bạn là một Queue. Nếu máy tính đang bị đơ (CPU bận), bạn gõ liên tiếp các phím "H", "I", "E", "U". Các ký tự này được đẩy vào Keyboard Buffer. Khi CPU rảnh, nó sẽ Dequeue và in ra màn hình đúng thứ tự "HIEU" mà bạn đã gõ, không làm mất ký tự nào.

• CPU Task Scheduling (Lập lịch tiến trình): Hệ điều hành Linux duy trì các "Ready Queue". Các tiến trình (Process/Goroutines) xếp hàng chờ để được cấp phát thời gian chạy trên các nhân (Cores) của CPU theo nguyên tắc công bằng FIFO (kết hợp với độ ưu tiên).

Giải pháp dùng con trỏ trượt lên phía trước trong mảng động (như code Golang ở trên) giúp tối ưu tốc độ xuống $O(1)$, nhưng lại sinh ra vùng "không gian chết" ở đầu mảng (những ô nhớ đã bị Dequeue không thể dùng lại được nữa cho đến khi toàn bộ mảng rỗng). Để giải quyết triệt để sự lãng phí này trong các hệ thống nhúng (Embedded) hoặc IoT có bộ nhớ siêu nhỏ, chúng ta sẽ bẻ cong mảng thẳng thành một vòng tròn khép kín.