DATA STRUCTURE AND ALGORITHM<br />
Queue<br />
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br />
HÀNG ĐỢI<br />
Dr. Dao Nam Anh<br />
<br />
Data Structure and Algorithm<br />
<br />
1<br />
<br />
Outline – Nội dung<br />
Khái niệm Queue<br />
Các thao tác trên Queue<br />
Hiện thực Queue<br />
Ứng dụng của Queue<br />
<br />
Data Structure and Algorithm<br />
<br />
2<br />
<br />
Resource - Reference<br />
Slides adapted from David Matuszek, Marty Stepp<br />
and Hélène Martin, edit by Dao Nam Anh.<br />
Major Reference:<br />
<br />
•<br />
<br />
Robert Sedgewick, and Kevin Wayne, “Algorithms”<br />
Princeton University, 2011, Addison Wesley<br />
<br />
•<br />
<br />
Algorithm in C (Parts 1-5 Bundle)- Third Edition by<br />
Robert Sedgewick, Addison-Wesley<br />
<br />
•<br />
<br />
Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.<br />
<br />
•<br />
<br />
Giải thuật và lập trình, Lê Minh Hoàng, Đại Học<br />
Sư Phạm, 2002<br />
Data Structure and Algorithm<br />
<br />
3<br />
<br />
Queues<br />
<br />
•<br />
<br />
Queue là một danh sách mà các đối tượng được thêm vào ở<br />
một đầu của danh sách và lấy ra ở một đầu kia của danh sách<br />
<br />
•<br />
<br />
Việc thêm một đối tượng vào Queue luôn diễn ra ở cuối<br />
Queue và việc lấy một đối tượng ra khỏi Queue luôn diễn ra<br />
ở đầu Queue<br />
<br />
•<br />
<br />
Việc thêm một đối tượng vào Queue hoặc lấy một đối tượng<br />
ra khỏi Queue được thực hiện theo cơ chế FIFO (First In<br />
First Out - Vào trước ra trước)<br />
<br />
Data Structure and Algorithm<br />
<br />
4<br />
<br />
Queues<br />
Hàng đợi hỗ trợ các thao tác:<br />
<br />
•<br />
<br />
Add - EnQueue(): Thêm đối tượng vào cuối<br />
(rear) Queue<br />
<br />
•<br />
<br />
Remove - DeQueue(): Lấy đối tượng ở đầu<br />
(front) Queue ra khỏi Queue<br />
<br />
•<br />
<br />
Peek: Examine the front element.<br />
front<br />
remove, peek<br />
<br />
1<br />
<br />
back<br />
2<br />
<br />
3<br />
<br />
add<br />
<br />
queue<br />
Data Structure and Algorithm<br />
<br />
5<br />
<br />