Bài 9. C u trúc d ấ ữ
li u hàng đ iệ ợ
Danh sách ki u Hàng đ i (Queue)ể ợ
Queue là cách t ch c l u tr các đ i t ng d i d ng ổ ứ ư ữ ố ượ ướ ạ
m t danh sách tuy n tính mà vi c b sung đ i t ng ộ ế ệ ổ ố ượ
đ c th c hi n đ u danh sách và vi c l y đ i t ng ra ượ ự ệ ở ầ ệ ấ ố ượ
đ c th c hi n cu i c a danh sách.ượ ự ệ ở ố ủ
Queue còn đ c g i là danh sách ki u ượ ọ ể FIFO (First In
First Out - vào tr c ra tr c)ướ ướ
C u trúc d li u tr u t ng Queue ấ ữ ệ ừ ượ
(The queue ADT)
Queue ADT l u tr các đ i ư ữ ố
t ng b t kỳượ ấ
Thêm vào và xóa đi (l y ra) ấ
theo ki u FIFOể
Thêm vào th c hi n cu i ự ệ ở ố
c a queue và l y ra th c ủ ấ ự
hi n đ u queueệ ở ầ
Các phép toán chính th c ự
hi n trên queue:ệ
•- enqueue(Object o): b ổ
sung m t ph n t o vào ộ ầ ử
cu i c a queue.ố ủ
•- dequeue(Object &o): Xóa
đi ph n t đ u c a queueầ ử ầ ủ
Các phép toán b trổ ợ
•- front(): tr l i ph n t đ u ả ạ ầ ử ầ
c a queue nh ng không ủ ư
xóa nó đi
•size(): tr l i s ph n t ả ạ ố ầ ử
hi n đang đ c l u tr ệ ượ ư ữ
trong queue
•isEmpty(): tr l i giá tr ki u ả ạ ị ể
boolen đ xác đ nh có ph n ể ị ầ
t đ c l u tr trong queue ử ượ ư ữ
không?
Ngo i l : th c hi n ạ ệ ự ệ dequeue
ho c ặenqueue trong khi
queue r ng, khi đó ta c n ỗ ầ
ph i chuy n nó đ n ngo i ả ể ế ạ
l ệ
M t s ng d ng c a queueộ ố ứ ụ ủ
Các ng d ng tr c ti pứ ụ ự ế
- Danh sách hàng đ iợ
- Truy nh p các ngu n dùng chung(ví d ậ ồ ụ
máy in trong m ng c c b )ạ ụ ộ
- Đa l p trìnhậ
Các ng d ng không tr c ti pứ ụ ự ế
- C u trúc d li u h tr cho các thu t toánấ ữ ệ ỗ ợ ậ
- Làm thành ph n c a các c u trúc d li u ầ ủ ấ ữ ệ
khác
Cài đ t queue b ng m ngặ ằ ả
S d ng m t m ng ki u vòng có kích th c Nử ụ ộ ả ể ướ
S d ng 2 bi n l u tr ch s c a ph n t tr c và ử ụ ế ư ữ ỉ ố ủ ầ ử ướ
ph n t sau:ầ ử
f l u ch s ph n t tr cư ỉ ố ầ ử ướ
r l u tr ch s ph n t chu n b đ c đ a vàoư ữ ỉ ố ầ ử ẩ ị ượ ư
V trí r c a m ng là r ngị ủ ả ỗ
C u hình bình th ngấ ườ
C u hình vòng l iấ ạ