Cấu trúc dữ liệu và Giải thuật Bài 37: Hàng đợi vòng (Circular Queue) - Tối ưu hóa không gian bộ nhớ.

Ở Bài 36, chúng ta đã tối ưu thao tác Dequeue trên mảng xuống thời gian $O(1)$ bằng cách trượt con trỏ Head về phía trước. Tuy nhiên, cái giá phải trả là sự xuất hiện của "không gian chết" (Dead Space). Khi Head tiến lên, các ô nhớ phía trước nó bị bỏ hoang. Mảng có thể báo "Đầy" (khi Tail chạm đáy mảng) mặc dù phía đầu mảng vẫn còn rất nhiều chỗ trống.

Để dọn dẹp không gian chết này, nếu dùng thao tác dịch chuyển toàn bộ mảng (Shift), ta lại rơi vào thảm họa $O(n)$. Đối với các hệ thống backend lớn, hoặc đặc biệt là môi trường vi điều khiển (STM32, ESP32) nơi bộ nhớ SRAM chỉ tính bằng Kilobyte, việc lãng phí RAM hoặc dùng mảng động cấp phát liên tục sẽ làm phân mảnh vùng Heap và gây crash hệ thống.

Giải pháp tối thượng chính là sự kết hợp giữa Hàng đợi (Queue) và phép toán Modulo (Bài 26): Hàng đợi vòng (Circular Queue) hay còn gọi là Ring Buffer.

1. Bản chất của sự uốn cong

Tương tự như cấu trúc mảng xoay vòng, chúng ta uốn cong mảng tuyến tính thành một vòng khép kín. Khi con trỏ Tail (hoặc Head) chạy đến vị trí cuối cùng của mảng (capacity - 1), thay vì báo lỗi "Out of bounds", phép toán Modulo % sẽ bẻ lái nó quay ngược trở lại vị trí 0.

Công thức dịch chuyển cốt lõi:

next_index = (current_index + 1) % capacity

Nhờ công thức này, Tail có thể vòng lên phía trước để tái sử dụng lại các ô nhớ "không gian chết" mà Head đã giải phóng sau khi Dequeue.

2. Nghịch lý Trống và Đầy (The Empty-Full Dilemma)

Khi thiết kế Circular Queue, bạn sẽ đối mặt với một vấn đề logic kinh điển.

Giả sử mảng có 5 phần tử. Khởi tạo Head = 0 và Tail = 0. Trạng thái này là Rỗng.

Bây giờ, bạn thêm liên tục 5 phần tử. Tail chạy một vòng và lại quay về vị trí 0 (trùng với Head). Trạng thái này là Đầy.

Làm sao để hệ thống phân biệt được khi Head == Tail thì mảng đang Rỗng hay đang Đầy? Có hai trường phái thiết kế để giải quyết nghịch lý này:

1. Hi sinh một ô nhớ: Luôn để trống 1 ô nhớ. Mảng được coi là Đầy khi Tail nằm ngay sát sau Head ((Tail + 1) % capacity == Head).

2. Sử dụng biến đếm (Size/Count): Dùng thêm một biến nguyên nguyên lưu số lượng phần tử hiện tại. Đây là cách trực quan và dễ bảo trì nhất trong các ngôn ngữ bậc cao.

3. Triển khai Ring Buffer bằng Golang

Đối với một kỹ sư nhúng hoặc backend như Hiếu, mô hình dùng biến đếm count mang lại sự an toàn tuyệt đối khi kiểm soát luồng dữ liệu liên tục:

Go

type CircularQueue struct {
    items    []int
    head     int // Con trỏ trỏ vào phần tử đầu hàng
    tail     int // Con trỏ trỏ vào vị trí trống TIẾP THEO để chèn
    count    int // Số lượng phần tử hiện có
    capacity int // Sức chứa tối đa (cố định)
}

func Constructor(k int) CircularQueue {
    return CircularQueue{
        items:    make([]int, k),
        head:     0,
        tail:     0,
        count:    0,
        capacity: k,
    }
}

// Enqueue: Thêm vào đuôi
func (q *CircularQueue) Enqueue(value int) bool {
    if q.IsFull() {
        return false // Báo lỗi nếu hàng đợi đã đầy
    }
    
    q.items[q.tail] = value
    // Trượt Tail lên 1 bước, nếu chạm đáy thì vòng về 0
    q.tail = (q.tail + 1) % q.capacity
    q.count++
    
    return true
}

// Dequeue: Lấy ra từ đầu
func (q *CircularQueue) Dequeue() bool {
    if q.IsEmpty() {
        return false // Báo lỗi nếu hàng đợi rỗng
    }
    
    // Ở đây ta không cần xóa dữ liệu vật lý (như gán bằng 0), 
    // vì dữ liệu rác sẽ bị Enqueue ghi đè lên sau này.
    
    // Trượt Head lên 1 bước, vòng về 0 nếu cần
    q.head = (q.head + 1) % q.capacity
    q.count--
    
    return true
}

func (q *CircularQueue) Front() int {
    if q.IsEmpty() {
        return -1
    }
    return q.items[q.head]
}

func (q *CircularQueue) IsEmpty() bool {
    return q.count == 0
}

func (q *CircularQueue) IsFull() bool {
    return q.count == q.capacity
}

Mọi thao tác trên cấu trúc này đều là $O(1)$ tuyệt đối. Không có bất kỳ vòng lặp nào ẩn giấu, không cấp phát thêm bộ nhớ động.

4. Ứng dụng sống còn trong Thực tế Hệ thống

Ring Buffer không phải là lý thuyết suông, nó là "hơi thở" của các hệ thống ngầm bên dưới mà chúng ta thao tác mỗi ngày:

• Vi điều khiển và Giao tiếp phần cứng (UART, SPI, I2C): Khi bạn lập trình nhúng C/C++ trên mạch, ngắt (Interrupt) ngoại vi có thể nhận dữ liệu bất cứ lúc nào. Hàm ngắt (ISR) sẽ đẩy dữ liệu vào một Ring Buffer (Enqueue) siêu nhanh rồi thoát để không khóa CPU. Vòng lặp while(1) ở chương trình chính (Main) sẽ từ từ rút dữ liệu ra (Dequeue) để xử lý. Nếu không có Ring Buffer, dữ liệu sẽ bị "rơi rớt" (Data Loss) khi CPU đang bận làm việc khác.

• Xử lý truyền phát Video/Audio (Media Streaming): Khi xem YouTube, trình duyệt sẽ tải trước (buffer) một đoạn video vào Hàng đợi vòng. Khi Player phát (Dequeue) khung hình số 1, trình duyệt sẽ dùng ngay ô nhớ trống đó để tải (Enqueue) khung hình số N+1. Bộ nhớ tiêu thụ luôn được giữ cố định (ví dụ 50MB) dù bạn có xem video dài 10 tiếng.

• Networking Stack của Hệ điều hành: Card mạng (NIC) sử dụng cấu trúc Ring Descriptor để nhận các gói tin (Packets) từ dây cáp mạng trước khi chuyển chúng lên Kernel xử lý.

Chúng ta đã giải quyết trọn vẹn luồng dữ liệu FIFO bình đẳng. Tuy nhiên, xã hội và máy tính không phải lúc nào cũng bình đẳng. Trong các hệ thống y tế hoặc Lập lịch tiến trình của OS, một tác vụ quan trọng (ví dụ: cấp cứu, hoặc cập nhật hệ thống lõi) phải được "chen ngang" lên đầu hàng đợi bất chấp việc nó đến sau. Để hệ thống có thể đối xử "thiên vị" dựa trên mức độ ưu tiên, chúng ta cần một siêu cấu trúc dữ liệu mới.