Hàng ñợi và Ngăn xếp
(Queue and Stack)
Lê Sỹ Vinh
Bộ môn Khoa Học Máy Tính – Khoa CNTT
ðại Học Công Nghệ - ðHQGHN
Email: vinhioi@yahoo.com
Hàng ñợi (Queue)
Hàng ñợi là gì?
Là một danh sách nhưng các phép toán chỉ ñược thực hiện ở hai ñỉnh của
danh sách. Một ñỉnh gọi là ñầu hàng, ñỉnh còn lại gọi là cuối hàng.
Ví dụ:
•Xếp hàng mua vé tàu xe, giao dịch với ngân hàng
Tính chất:
Vào trước ra trước (First in First Out: FIFO)
Hàng ñợi
Trừu tượng hóa cấu trúc hàng ñợi
1. Mô tả dữ liệu
A= (a0, a1, …, an)
trong ñó:
–ao: Phần tử ở ñầu của hàng ñợi A
–
a
n
: Phần tử ở
cuối
của
hàng ñợi
–
a
n
: Phần tử ở
cuối
của
hàng ñợi
Ví dụ:
A= (‘Vinh’, ‘Tuấn’,. ‘Ánh’)
trong ñó:
‘Vinh’: ðầu hàng ñợi
‘Ánh’: Cuối hàng ñợi
Các phép toán trên hàng ñợi
•empty (A): Kiểm tra hàng ñợi có rỗng hay không
•length (A): Cho biết số phần tử của hàng ñợi
•EnQueue (A, x): Thêm phần tử xcuối hàng ñợi.
A = (a0, a1,…, an) → A = (a0,a1,…,an, x)
Ví dụ: A = (1,3,5)
EnQueue (A, 4) → A = (1, 3, 5, 4)
•DeQueue (A): Loại phần tử ở ñầu hàng ñợi
A = (a0, a1,…, an-1, an) → A = (a1,…,an)
Ví dụ: A = (1,3,5)
DeQueue (A) → A = (3, 5)
•GetHead (A): Lấy phần tử ở ñầu hàng ñợi
A = (a0, a1,…, an-1, an) → getHead (A) → a0
Ví dụ: A = (1,3,5)
getHead (A) → 1
Bài tập
1. Viết chương trình cài ñặt cấu trúc hàng ñợi bằng mảng và danh sách liên
kết
2. Tính ñộ phức tạp cho cài ñặt ở câu 1
3. ðọc và cài ñặt hàng ñợi bằng màng tròn