Bài 13. Hàng đợi - Queues
Nội dung:
13.1. Khái niệm về hàng đợi.
13.2. Xây dựng và sử dụng Queue.
13.3. Ví dụ về hàng đợi.
Tham khảo:
1. Data structures and Algorithms Stacks.htm, Kyle Loudon Mastering
Algorithms,
2. Chapter 6 Stacks and Queues, Elliz Horowitz –Fundamentals of Data
Structures.
3. Chapter 3 Stacks and Queues, Deshpande Kakle –C and Data Structures.
4. Bài giảng TS Nguyễn Nam Hồng.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
2
13.1. Khái niệm về hàng đợi (1/8)
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
3
13.1. Khái niệm về hàng đợi (2/8)
Trong ứng dụng máy tính, định nghĩa CTDL hàng đợi là danh
sách, trong đó việc thêm một phần tử được thực hiện ở đầu
một danh sách (cuối hàng đợi) và việc lấy ra một phần tử được
thực hiện ở cuối danh sách (đầu hàng).
Hàng đợi còn được gọi là danh sách FIFO (First In First Out).
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
4
Ví dụ về hàng đợi
13.1. Khái niệm về hàng đợi (3/8)
Đối với hàng đợi, số lượng ứng dụng có nhiều hơn cả ngăn
xếp.
Ví dụ như máy tính thực hiện nhiệm vụ, có nhiều hàng đợi
được sử dụng:
hàng đợi máy in,
việc truy xuất đĩa,
sử dụng CPU.
chuyển đổi từ Infix sang Prefix.
Phần tử đầu hàng đợi được phục vụ trước, phần tử này thường
gọi là front hay head. Phần tử mới thêm vào được gọi là rear
hay tail.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
5
