Cài đặt Queue bằng Mảng

• Ưu điểm:
  • Truy cập phần tử dựa trên chỉ số có độ phức tạp thời gian O(1).
  • Dữ liệu được lưu trữ liền kề trong bộ nhớ, tối ưu hóa khả năng tận dụng bộ nhớ cache (Cache Locality).
• Nhược điểm:
  • Kích thước cố định (đối với mảng tĩnh) hoặc tốn chi phí cấp phát lại bộ nhớ và sao chép dữ liệu (đối với mảng động).
  • Gặp hiện tượng lãng phí bộ nhớ nếu không dùng mảng vòng.

Cài đặt Queue bằng Danh sách liên kết đơn

• Ưu điểm:
  • Kích thước linh hoạt, dễ dàng mở rộng động theo số lượng phần tử thực tế mà không cần định nghĩa trước dung lượng tối đa.
  • Thao tác Enqueue và Dequeue ở cả hai đầu đều đạt độ phức tạp thời gian O(1) nếu duy trì đồng thời con trỏ head và tail.
• Nhược điểm:
  • Tốn thêm bộ nhớ để lưu trữ các con trỏ (pointers) liên kết giữa các node.
  • Không tối ưu Cache Locality do các node nằm rải rác trong bộ nhớ heap.

Lưu ý kinh nghiệm thực chiến

Ở cấp độ Junior, khi phỏng vấn cần nắm vững độ phức tạp thời gian (Time Complexity) và không gian (Space Complexity) của từng cách tiếp cận để lựa chọn cấu trúc dữ liệu phù hợp với bài toán hệ thống cụ thể.