DATA STRUCTURE AND ALGORITHM Queue
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT HÀNG ĐỢI
Dr. Dao Nam Anh
1
Data Structure and Algorithm
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
2
Data Structure and Algorithm
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”
• Algorithm in C (Parts 1-5 Bundle)- Third Edition by
Princeton University, 2011, 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
Robert Sedgewick, Addison-Wesley
3
Data Structure and Algorithm
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
• 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)
Queue và việc lấy một đối tượng ra khỏi Queue luôn diễn ra ở đầu Queue
4
Data Structure and Algorithm
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
5
queue Data Structure and Algorithm
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
6
queue Data Structure and Algorithm
Ứ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
7
Data Structure and Algorithm
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
17 23 97 44
myQueue:
David Matuszek
front = 0 rear = 3
8
Data Structure and Algorithm
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
0 1 2 3 4 5 6 7
deleting from the other (the front)
17 23 97 44 23
myQueue:
• To insert: put new element in location 4, and set rear to 4
David Matuszek
front = 0 rear = 4
9
Data Structure and Algorithm
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
0 1 2 3 4 5 6 7
deleting from the other (the front)
17 23 97 44
myQueue:
• 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
front = 1 rear = 3
10
Data Structure and Algorithm
Mô tả Queue bằng mảng
rear = 3 front = 0
17 23 97 44
Ban đầu:
17 23 97 44 333
Chèn:
23 97 44 333
Xóa:
• 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:
front = 1 rear = 4
11
Data Structure and Algorithm
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
11
myQueue:
• Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi
rear = 5 front = 5
trong cùng thứ tự
12
• Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm
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
11 22
myQueue:
• Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi
rear = 6 front = 5
trong cùng thứ tự
13
• Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm
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
11 22 33
myQueue:
• Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi
rear = 7 front = 5
trong cùng thứ tự
14
• Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm
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
44
11 22 33
myQueue:
• Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi
rear = 0 front = 5
trong cùng thứ tự
15
• Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm
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
44 55
11 22 33
myQueue:
• Thêm vào hàng đợi các số 11, 22, 33, 44, 55, và sẽ xóa đi
rear = 1 front = 5
trong cùng thứ tự
16
• Tính: front = (front + 1) % myQueue.length; và: rear = (rear + 1) % myQueue.length; Data Structure and Algorithm
Full and empty queues
• Hàng đợi có thể đầy:
0 1 2 3 4 5 6 7
44 55 66 77 88 11 22 33
myQueue:
• Hàng đợi có thể rỗng:
0 1 2 3 4 5 6 7
rear = 4 front = 5
myQueue:
Đó là vấn đề!
rear = 4 front = 5
17
Data Structure and Algorithm
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
44 55 66 77 88 11 22 33
myQueue:
• 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
count = 8 rear = 4 front = 5
44 55 66 77
11 22 33
myQueue:
rear = 3 front = 5
18
Data Structure and Algorithm
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;
19
Data Structure and Algorithm
};
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
20
Data Structure and Algorithm
Discussion – Câu hỏi
• https://sites.google.com/site/daonamanhedu/data-
structure-algorithm
21
