Queue (Hàng đợi) là một linear data structure. Queue hoạt động theo cơ chế FIFO (First In First Out). Tức là, phần tử nào được thêm vào đầu tiên sẽ được lấy ra đầu tiên.
Queue mô tả rất tự nhiên hàng đợi của con người trong cuộc sống hàng ngày. Ví dụ, quầy thanh toán ở siêu thị, người xếp hàng đầu tiên đứng đầu hàng đợi sẽ được phục vụ trước. Người mới tới sẽ xếp chèn vào cuối hàng.
Lưu ý: Việc chèn phần tử mới vào hàng đợi có thể không phải là cuối hàng, nó phụ thuộc vào loại hàng đợi và độ ưu tiên của phần tử.
1. Các phương thức cơ bản trên Queue
Các thao tác cơ bản của Queue gồm có:
- Enqueue: Thêm mới một phần tử vào hàng đợi. Nếu hàng đợi đầy thì gọi là Overflow.
- Dequeue: Xóa một phần tử khỏi hàng đợi, nếu hàng đợi rỗng thì gọi là Underflow.
- Front: Lấy một phần tử ở đầu hàng đợi.
- Rear: Lấy một phần tử ở cuối hàng đợi.
2. Cài đặt Queue
Có 2 cách cơ bản để cài đặt một Queue:
- Sử dụng Array
- Sử dụng Linked List
2.1. Cài đặt Queue sử dụng Array
Đang cập nhật…
TÙNG'S BLOG 