QUEUES – Lý thuyết cơ bản

Tram Ho

5.1 Queue là gì?

Queue(Hàng đợi) là một cấu trúc dữ liệu được sử dụng để lưu trữ dữ liệu (tương tự như Linked Lists và Stacks). Trong hàng đợi, thứ tự dữ liệu đến là điều quan trọng. Nói chung, bạn có thể tưởng tượng hàng đợi là một dòng người đang chờ được phục vụ theo thứ tự tuần tự bắt đầu từ đầu hàng hoặc tuần tự.

Định nghĩa: Hàng đợi là một danh sách có thứ tự trong đó việc thêm được thực hiện ở một đầu (phía sau) và việc xóa được thực hiện ở đầu kia (phía trước). Phần tử đầu tiên được thêm là phần tử đầu tiên sẽ bị xóa. Do đó, nó được gọi là First in First out (FIFO) hoặc Last in Last out (LILO).

Tương tự như Ngăn xếp, có 2 tên đặc biệt được đặt cho hai thay đổi có thể được thực hiện đối với hàng đợi. Khi một phần tử được chèn vào hàng đợi, khái niệm được gọi là EnQueue và khi một phần tử bị xóa khỏi hàng đợi, khái niệm được gọi là DeQueue. DeQueing một hàng đợi trống sẽ gây ra underflow và EnQueue một phần tử trong một hàng đợi đã đầy được gọi là overflow. Nói chung, chúng tôi coi chúng là những trường hợp ngoại lệ.

image.png

5.2 Queue được sử dụng như thế nào?

Khái niệm hàng đợi có thể được giải thích bằng cách quan sát một hàng tại quầy đặt chỗ.
Khi vào hàng chúng ta đứng ở cuối hàng và người đứng đầu hàng là người sẽ được phục vụ tiếp theo.
Anh ta sẽ thoát khỏi hàng đợi và được phục vụ.
Khi điều này xảy ra, người tiếp theo sẽ đến ở đầu hàng, sẽ thoát ra khỏi hàng đợi và sẽ được phục vụ.
Khi mỗi người ở đầu hàng tiếp tục thoát ra khỏi hàng đợi, chúng ta sẽ di chuyển về phía người đứng đầu hàng.
Cuối cùng chúng ta sẽ đến đầu hàng và chúng ta sẽ thoát khỏi hàng đợi và được phục vụ.
Hành vi này rất hữu ích trong những trường hợp cần duy trì thứ tự đến.

5.3 Queue ADT

Các hoạt động sau đây làm cho một hàng đợi trở thành một ADT. Việc chèn và xóa trong hàng đợi phải tuân theo cơ chế FIFO. Để đơn giản, chúng ta giả sử các phần tử là số nguyên.

Main Queue Operations

  • enQueue (int data): Chèn một phần tử vào cuối hàng đợi
  • int deQueue(): Loại bỏ và trả về phần tử ở phía trước hàng đợi

Auxiliary Queue Operations

  • int Front (): Trả về phần tử ở phía trước mà không xóa nó
  • int QueueSize (): Trả về số phần tử được lưu trữ trong hàng đợi
  • int IsEmptyQueue (): Cho biết không có phần tử nào được lưu trữ trong hàng đợi hay không

5.4 Exceptions(Ngoại lệ)

Tương tự như các ADT khác, việc thực thi DeQueue trên hàng đợi trống sẽ ném ra “Empty Queue Exception” và thực thi EnQueue trên hàng đợi full sẽ ném ra “Full Queue Exception”.

5.5 Ứng dụng

Sau đây là một số ứng dụng sử dụng hàng đợi.

Ứng dụng trực tiếp

  • Hệ điều hành lập lịch công việc (với mức độ ưu tiên ngang nhau) theo thứ tự đến (ví dụ: hàng đợi in).
  • Mô phỏng các hàng đợi trong thế giới thực chẳng hạn như các hàng tại quầy bán vé hoặc bất kỳ tình huống nào đến trước được phục vụ trước yêu cầu một hàng đợi.
  • Multiprogramming
  • Truyền dữ liệu không đồng bộ (file IO, pipes, sockets).
  • Thời gian chờ đợi của khách hàng tại tổng đài.
  • Xác định số lượng nhân viên thu ngân cần có tại siêu thị.

Ứng dụng gián tiếp

  • Cấu trúc dữ liệu bổ trợ cho các thuật toán
  • Thành phần của cấu trúc dữ liệu khác

5.6 Implementation

Có nhiều cách (tương tự như Stacks) để thực hiện các queue operations và một số phương pháp thường được sử dụng được liệt kê dưới đây.

  • Implement dựa trên mảng tròn đơn giản
  • Implement dựa trên mảng tròn động
  • Implement danh sách liên kết

Tại sao lại là Circular Arrays(Mảng tròn)?

Đầu tiên, hãy xem liệu chúng ta có thể sử dụng các mảng đơn giản để triển khai hàng đợi như chúng ta đã làm với ngăn xếp hay không.
Chúng ta biết rằng, trong hàng đợi, việc chèn được thực hiện ở một đầu và việc xóa được thực hiện ở đầu kia.
Sau khi thực hiện một số thao tác chèn và xóa, quá trình này trở nên dễ hiểu.
Trong ví dụ được hiển thị bên dưới, có thể thấy rõ ràng rằng các vị trí ban đầu của mảng đang bị lãng phí.
Vì vậy, triển khai mảng đơn giản cho hàng đợi không hiệu quả.
Để giải quyết vấn đề này, chúng ta giả sử các mảng là mảng tròn.
Điều đó có nghĩa là, chúng ta coi phần tử cuối cùng và các phần tử đầu tiên của mảng là liền nhau.
Với cách biểu diễn này, nếu có bất kỳ vị trí trống nào ở đầu, con trỏ phía sau có thể dễ dàng đi đến vị trí trống tiếp theo của nó.

image.png

image.png

Simple Circular Array Implementation(Implement dựa trên mảng tròn đơn giản)

image.png

Việc triển khai Queue ADT đơn giản này sử dụng một mảng.
Trong mảng, chúng ta thêm các phần tử theo hình tròn và sử dụng hai biến để theo dõi phần tử bắt đầu và phần tử kết thúc.
Nói chung, phía trước được sử dụng để chỉ ra phần tử bắt đầu và phía sau được sử dụng để chỉ ra phần tử kết thúc trong hàng đợi.
Mảng lưu trữ các phần tử hàng đợi có thể full.
Một hoạt động EnQueue sau đó sẽ ném ra một full queue exception.
Tương tự, nếu chúng ta thử xóa một phần tử khỏi hàng đợi trống, nó sẽ ném ra empty queue exception.

Note: Ban đầu, cả phía trước và phía sau đều trỏ đến -1 cho biết hàng đợi trống.

Đây là code của tác giả, cá nhân mình thấy chưa chuẩn lắm vì có hàm khởi tạo cho phép truyền độ lớn của queue vào, nhưng cả 2 hàm enQueue và deQueue 2 tham số rear và front đều đang tính toán theo CAPACITY.

Nên mình có tham khảo thêm code ở đây

Performance and Limitations

Performance: Gọi n là số phần tử trong hàng đợi:

image.png

Limitations
Kích thước tối đa của hàng đợi phải được xác định trước đó và không thể thay đổi.
Cố gắng EnQueue một phần tử mới vào một hàng đợi full sẽ gây ra một exception.

Dynamic Circular Array Implementation

Mình tham khảo code ở đây

Performance

image.png

Linked List Implementation

Một cách khác để triển khai hàng đợi là sử dụng Linked lists.
Hoạt động EnQueue được thực hiện bằng cách chèn một phần tử vào cuối danh sách. Thao tác DeQueue được thực hiện bằng cách xóa một phần tử khỏi đầu danh sách.

image.png

Performance

image.png

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo