Giải thích độ phức tạp thời gian của các thao tác cơ bản trong Queue và nêu rõ lý do tại sao một số cách cài đặt lại kém hiệu quả?

Question

Accepted Answer

Độ phức tạp thời gian chuẩn của Queue

Thao tác Enqueue (Thêm phần tử vào cuối): O(1) nếu có duy trì con trỏ tail.
Thao tác Dequeue (Lấy phần tử ra từ đầu): O(1) nếu quản lý con trỏ head hoặc sử dụng mảng vòng.
Thao tác Peek (Xem phần tử đầu): O(1).
Thao tác Search (Tìm kiếm phần tử): O(N).

Nguyên nhân gây kém hiệu quả trong thực tế

Nếu cài đặt Queue bằng mảng thông thường mà không dùng mảng vòng, khi thực hiện Dequeue, ta phải dịch chuyển toàn bộ các phần tử còn lại về bên trái để lấp đầy vị trí trống, dẫn đến độ phức tạp thời gian của Dequeue bị đẩy lên O(N), làm giảm hiệu năng hệ thống nghiêm trọng.
Nếu cài đặt danh sách liên kết nhưng quên duy trì con trỏ tail, thao tác Enqueue sẽ phải duyệt qua toàn bộ danh sách từ đầu đến cuối để tìm node cuối cùng, biến độ phức tạp thành O(N).

Lưu ý kinh nghiệm thực chiến
Luôn kiểm tra kỹ các biến con trỏ khi xây dựng cấu trúc dữ liệu tùy chỉnh (Custom Data Structures) để tránh vi phạm các ràng buộc về hiệu năng O(1) trong các tác vụ cốt lõi.