Bài giảng Cấu trúc dữ liệu và giải thuật: Hàng đợi - TS. Đào Nam Anh

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 />