"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 13: Hàng đợi - Queues" tìm hiểu về khái niệm về hàng đợi, xây dựng và sử dụng Queue, ví dụ về hàng đợi. Để nắm chi tiết nội dung kiến thức, mời các bạn cùng tham khảo bài giảng.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 13: Hàng đợi - Queues
- Cấu trúc dữ liệu và giải thuật
Bài 13. Hàng đợi - Queues
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- Bài 13. Hàng đợi - Queues
Nội dung:
13.1. Khái niệm về hàng đợi.
13.2. Xây dựng và sử dụng Queue.
13.3. Ví dụ về hàng đợi.
Tham khảo:
1. Data structures and Algorithms Stacks.htm, Kyle Loudon Mastering
Algorithms,
2. Chapter 6 Stacks and Queues, Elliz Horowitz – Fundamentals of Data
Structures.
3. Chapter 3 Stacks and Queues, Deshpande Kakle – C and Data Structures.
4. Bài giảng TS Nguyễn Nam Hồng.
2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (1/8)
3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (2/8)
Trong ứng dụng máy tính, định nghĩa CTDL hàng đợi là danh
sách, trong đó việc thêm một phần tử được thực hiện ở đầu
một danh sách (cuối hàng đợi) và việc lấy ra một phần tử được
thực hiện ở cuối danh sách (đầu hàng).
Hàng đợi còn được gọi là danh sách FIFO (First In First Out).
Ví dụ về hàng đợi
4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (3/8)
Đối với hàng đợi, số lượng ứng dụng có nhiều hơn cả ngăn
xếp.
Ví dụ như máy tính thực hiện nhiệm vụ, có nhiều hàng đợi
được sử dụng:
hàng đợi máy in,
việc truy xuất đĩa,
sử dụng CPU.
chuyển đổi từ Infix sang Prefix.
Phần tử đầu hàng đợi được phục vụ trước, phần tử này thường
gọi là front hay head. Phần tử mới thêm vào được gọi là rear
hay tail.
5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (4/8)
Định nghĩa:
Một hàng đợi các phần tử kiểu T là một chuỗi nối tiếp các phần
tử của T và kèm theo một số tác vụ sau:
1. Tạo mới một đối tượng hàng rỗng.
2. Thêm một phần tử mới vào hàng, giả sử hàng đợi chưa đầy
(phần tử dữ liệu mới luôn được thêm vào cuối hàng).
3. Loại một phần tử ra khỏi hàng, giả sử hàng chưa rỗng (phần tử
bị loại là phần tử tại đầu hàng, thường là phần tử vừa được xử lý
xong).
4. Xem phần tử tại đầu hàng (phần tử sắp được xử lý).
6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (5/8)
Hoạt động của hàng đợi
7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (3/8)
Xây dựng Queue:
Thành phần dữ liệu cho Queue:
MaxEntry: Kích thước của Queue.
QueueEntry: Kiểu dữ liệu dành cho mỗi phần tử trong Queue.
Một số phương thức cơ bản của Queue:
QueueClassL();
int isEmpty();
int isFull();
int Dequeue(QueueEntry *value);
int Enqueue(QueueEntry value);
int Peek(QueueEntry *value);
void makeEmpty();
8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (4/8)
Khai báo lớp Queue (dạng tuyến tính):
template // Lớp mẫu cho kiểu dữ liệu của Queue
class QueueClassL{ // Định nghĩa tên lớp
public:
QueueClassL(); // Hàm tạo của lớp, khởi tạo thông tin cho Queue
int isEmpty(); // Queue rỗng → 1, ngược lại → 0
int isFull(); // Queue đầy → 1, ngược lại → 0
int Dequeue(QueueEntry *value); // Lấy 1 phần tử Queue
int Enqueue(QueueEntry value); // Thêm 1 phần tử vào Queue
int Peek(QueueEntry *value); // Xem giá trị tại đầu của Queue
void makeEmpty(); // Làm rỗng Queue
private:
int front, rear; // front: đầu Queue, rear: cuối Queue
QueueEntry entry[MaxEntry]; // Mảng lưu thông tin của Queue
};
9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (5/8)
Một số phương thức của Queue:
template template
QueueClassL int QueueClassL
::QueueClassL(void) ::isEmpty()
{ {
front=rear=-1; if(front==rear)
} return 1;
else return 0;
}
10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (6/8)
Một số phương thức của Queue:
template
template int QueueClassL
::Dequeue(QueueEntry *value)
int QueueClassL::isFull()
{
{
if(!isEmpty())
if(rear==MaxEntry-1)
{
return 1;
front++;
else return 0; *value = entry[front];
} return 1;
}
else
return 0;
}
11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (7/8)
Một số phương thức của Queue: template
template int QueueClassL
int QueueClassL ::Peek(QueueEntry *value)
::Enqueue(QueueEntry value) { if(!isEmpty() && front!=-1)
{ { *value = entry[front];
if(!isFull()) return 1;
{ }
rear++; else return 0;
entry[rear]=value; }
return 1; template
} void QueueClassL
else ::makeEmpty()
return 0; {
} front=rear=-1;
}
12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.1. Khái niệm về hàng đợi (8/8)
Một số dạng của hàng đợi:
Hàng đợi tuyến tính - Linear Queues
Tổ chức hàng đợi theo nghĩa thông thường.
Hàng đợi vòng - Circular Queues
Giải quyết việc thiếu bộ nhớ khi sử dụng hàng đợi.
Hàng đợi ưu tiên - Priority Queues
Mỗi phần tử có kết hợp thêm thông tin về độ ưu tiên.
Khi chương trình cần lấy một phần tử khỏi hàng đợi, nó sẽ xét
những phần tử có độ ưu tiên cao trước.
Multi-Headed Queues.
13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (1/7)
Với Queue đã được khai báo, xây dựng chương trình sử dụng Queue
#include void main() {
#include QueueClassL queue;
#include QueueEntry value;
typedef int QueueEntry;
int key;
#define MaxEntry 10
char ch;
#include "QueueClass.h“
do {
void menu()
menu();
{
printf("1. Nhap vao QUEUE\n"); printf("Moi lua chon: ");
printf("2. Lay ra khoi QUEUE\n"); scanf("%d",&key);
printf("3. Gia tri tren dinh QUEUE la gi?\n"); switch (key) {
printf("4. QUEUE rong?\n"); case 1:
printf("5. QUEUE day?\n"); printf("Nhap phan tu can dua vao QUEUE\n");
printf("6. Lam rong QUEUE!\n"); scanf("%d",&value);
printf("7. Thoat\n");
if(queue.Enqueue(value))
}
printf("Da them vao Queue\n");
14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (2/7)
else printf("QUEUE van co gia tri\n");
printf("Queue da day!\n"); break; break;
case 2: case 5:
printf("Lay mot phan tu khoi QUEUE\n");
if(queue.isFull()==1)
if(queue.Dequeue(&value))
printf("QUEUE day\n");
printf("Gia tri lay ra: %d\n",value);
else
else
printf("QUEUE chua day\n");
printf("Queue rong\n");
break; break;
case 3: case 6:
if(queue.Peek(&value)) printf("Lam rong QUEUE? Co chac khong? (C/K)");
printf("Gia tri tai front QUEUE: %d\n",value); fflush(stdin);
else scanf("%c",&ch);
printf("Queue rong\n"); if(ch=='c' || ch=='C')
break;
queue.makeEmpty();
case 4:
break;
if(queue.isEmpty()==1)
}
printf("QUEUE rong\n");
} while (key!=7); }
else
15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (3/7)
Một số nhận xét cho dạng Queue nói trên:
Đáp ứng được các tiêu chí về Queue.
Tuy nhiên, với kích thước Queue là 10 (theo ví dụ) chỉ có thể
thêm tối 10 phần tử.
Ngoài ra, vì front chỉ tăng, do đó, trong Queue vẫn còn ô nhớ
nhưng không sử dụng được.
Giải quyết vấn đề trên:
Sử dụng Queue có dạng vòng.
Khi đó, làm thế nào để biết Queue đã đầy hay rỗng?
Giá trị khởi tạo cho front và rear như thế nào?
Xây dựng Queue như thế nào?
16 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (4/7)
Ví dụ về Queue
có dạng vòng
17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (5/7)
Hoạt động của Queue After 5
front 1 dequeues
1 After 7 enqueues 0
0 front
12
12 11
11 rear
10
10 rear
rear
1
0
front
12
11
After 8 more enqueues
10
18 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (6/7)
Xây dựng hàng đợi vòng
template template
class QueueClassC{ QueueClassC::QueueClassC(void)
public:
{
QueueClassC();
front = 0;
int isEmpty();
int isFull(); rear = 0;
int Dequeue(QueueEntry *value); }
int Enqueue(QueueEntry value); template
int Peek(QueueEntry *value); int QueueClassC::isEmpty()
void makeEmpty();
{
private:
if(front= =rear)
int front, rear;
QueueEntry entry[MaxEntry]; return 1;
}; else return 0;
}
19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 13.2. Xây dựng và sử dụng Queue (7/7)
template template
int QueueClassC::isFull() int QueueClassC::Enqueue(QueueEntry
{ value)
if((rear+1)%MaxEntry== front) { if(!isFull()) {
return 1; rear = (rear+1) % MaxEntry;
else return 0; entry[rear]=value; return 1; }
} else return 0; }
template
template
int QueueClassC::Dequeue(QueueEntry
*value) int QueueClassC::Peek(QueueEntry *value)
{ { if(!isEmpty()) {
if(!isEmpty()) *value = entry[(front+1)%MaxEntry];
{ return 1; }
front = (front+1)%MaxEntry; else return 0; }
*value = entry[front]; template
return 1;
void QueueClassC::makeEmpty()
}
{ front=rear=0;
else
}
return 0; }
20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
