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

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

1. DATA STRUCTURE AND ALGORITHM Queue CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT HÀNG ĐỢI Dr. Dao Nam Anh Data Structure and Algorithm 1
2. Outline – Nội dung  Khái niệm Queue  Các thao tác trên Queue  Hiện thực Queue  Ứng dụng của Queue Data Structure and Algorithm 2
3. Resource - Reference Slides adapted from David Matuszek, Marty Stepp and Hélène Martin, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 3
4. Queues • Queue là một danh sách mà các đối tượng được thêm vào ở một đầu của danh sách và lấy ra ở một đầu kia của danh sách • Việc thêm một đối tượng vào Queue luôn diễn ra ở cuối Queue và việc lấy một đối tượng ra khỏi Queue luôn diễn ra ở đầu Queue • Việc thêm một đối tượng vào Queue hoặc lấy một đối tượng ra khỏi Queue được thực hiện theo cơ chế FIFO (First In First Out - Vào trước ra trước) Data Structure and Algorithm 4
5. Queues Hàng đợi hỗ trợ các thao tác: • Add - EnQueue(): Thêm đối tượng vào cuối (rear) Queue • Remove - DeQueue(): Lấy đối tượng ở đầu (front) Queue ra khỏi Queue • Peek: Examine the front element. front back remove, peek add 1 2 3 queue Data Structure and Algorithm 5
6. Queues Queue còn hỗ trợ các thao tác: • isEmpty(): Kiểm tra xem hàng đợi có rỗng không • Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra front back remove, peek add 1 2 3 queue Data Structure and Algorithm 6
7. Ứng dụng Hàng đợi • Cuộc sống hàng ngày:  Xếp hàng đợi thang máy  Hàng xe ô tô tại trạm xăng • Programming:  Mô hình hàng đợi của khách hàng  Hàng đợi các phép tính cần tính • Hệ điều hành:  Hàng đợi các tệp ra máy in  Hàng đợi các chương trình để chạy  Hàng đợi các gói tin gửi lên mạng Data Structure and Algorithm 7
8. Mô tả Queue bằng mảng Có thể tạo một Queue bằng cách sử dụng một mảng 1 chiều theo kiểu xoay vòng (coi phần tử an-1 kề với phần tử a0) • Hàng đợi chứa tối đa N phần tử • Phần tử ở đầu hàng đợi sẽ có chỉ số front • Phần tử ở cuối hàng đợi sẽ có chỉ số rear 0 1 2 3 4 5 6 7 myQueue: 17 23 97 44 front = 0 rear = 3 David Matuszek Data Structure and Algorithm 8
9. Mô tả Queue bằng mảng • A queue is a first in, first out (FIFO) data structure • This is accomplished by inserting at one end (the rear) and deleting from the other (the front) 0 1 2 3 4 5 6 7 myQueue: 17 23 97 44 23 front = 0 rear = 4 • To insert: put new element in location 4, and set rear to 4 David Matuszek Data Structure and Algorithm 9
10. Mô tả Queue bằng mảng • A queue is a first in, first out (FIFO) data structure • This is accomplished by inserting at one end (the rear) and deleting from the other (the front) 0 1 2 3 4 5 6 7 myQueue: 17 23 97 44 front = 1 rear = 3 • To insert: put new element in location 4, and set rear to 4 • To delete: take element from location 0, and set front to 1 David Matuszek Data Structure and Algorithm 10
11. Mô tả Queue bằng mảng front = 0 rear = 3 Ban đầu: 17 23 97 44 Chèn: 17 23 97 44 333 Xóa: 23 97 44 333 front = 1 rear = 4 • Dùng mảng: Có xu hướng dời về cuối mảng • Hai cách hiện thực:  Khi lấy một phần tử ra thì đồng thời dời ô lên một vị trí  Khi lấy một phần tử ra thì không dời ô lên: Data Structure and Algorithm 11
12. Mô tả Queue bằng danh sách vòng • Dùng mảng lưu Hàng đợi với danh sách vòng 0 1 2 3 4 5 6 7 myQueue: 11 rear = 5 front = 5 • Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi trong cùng thứ tự • Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm 12
13. Mô tả Queue bằng danh sách vòng • Dùng mảng lưu Hàng đợi với danh sách vòng 0 1 2 3 4 5 6 7 myQueue: 11 22 rear = 6 front = 5 • Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi trong cùng thứ tự • Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm 13
14. Mô tả Queue bằng danh sách vòng • Dùng mảng lưu Hàng đợi với danh sách vòng 0 1 2 3 4 5 6 7 myQueue: 11 22 33 rear = 7 front = 5 • Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi trong cùng thứ tự • Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm 14
15. Mô tả Queue bằng danh sách vòng • Dùng mảng lưu Hàng đợi với danh sách vòng 0 1 2 3 4 5 6 7 myQueue: 44 11 22 33 rear = 0 front = 5 • Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi trong cùng thứ tự • Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm 15
16. Mô tả Queue bằng danh sách vòng • Dùng mảng lưu Hàng đợi với danh sách vòng 0 1 2 3 4 5 6 7 myQueue: 44 55 11 22 33 rear = 1 front = 5 • Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi trong cùng thứ tự • Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm 16
17. Full and empty queues • Hàng đợi có thể đầy: 0 1 2 3 4 5 6 7 myQueue: 44 55 66 77 88 11 22 33 rear = 4 front = 5 • Hàng đợi có thể rỗng: 0 1 2 3 4 5 6 7 myQueue: rear = 4 front = 5 Đó là vấn đề! Data Structure and Algorithm 17
18. Full and empty queues: solutions • Giải pháp 1: Dùng thêm 1 biến phụ 0 1 2 3 4 5 6 7 myQueue: 44 55 66 77 88 11 22 33 count = 8 rear = 4 front = 5 • Giải pháp 2: Giữ 1 ô trống: Coi như hàng đợi chỉ có n-1 ô 0 1 2 3 4 5 6 7 myQueue: 44 55 66 77 11 22 33 rear = 3 front = 5 Data Structure and Algorithm 18
19. Mô tả Queue bằng danh sách nối đơn • Có thể tạo một hàng đợi sử dụng một DSLK đơn • Phần tử đầu DSKL (phead) sẽ là phần tử đầu Queue (front), phần tử cuối DSKL (ptail) sẽ là phần tử cuối Queue (rear) struct Node { DataType data; Node *pNext; }; struct Queue { Node *front, *rear; }; Data Structure and Algorithm 19
20. Mô tả Queue bằng danh sách nối đơn • Tương tự như cài đặt Stack bằng danh sách nối đơn kiểu LIFO, ta cũng không kiểm tra Queue tràn trong trường hợp mô tả Queue bằng danh sách nối đơn kiểu FIFO Data Structure and Algorithm 20
21. Discussion – Câu hỏi • structure-algorithm Data Structure and Algorithm 21