2.6 Queue – Hàng đợi
- Định nghĩa
- Ứng dụng
- Cài đặt queue bằng mảng
- Cài đặt queue bằng danh sách móc nối
Định nghĩa
- Queue: là cấu trúc hiệu quả để lưu trữ và lấy dữ liệu theo thứ tự vào trước ra trước (FIFO)
- Phần tử được lấy ra ở phần đầu queue (front), và được thêm vào ở cuối queue (rear)
Ứng dụng
- Trong hệ điều hành:
- Hàng đợi xử lý sự kiện
- Quản lý tiến trình
- Tổ chức bộ đệm bàn phím
- Xử lý các lệnh
- Khử đệ quy
- Lưu vết quá trình tìm kiếm, quay lui, vét cạn ….
Cài đặt queue
- enQueue() : thêm một phần tử mới vào queue
- deQueue() : lấy một phần tử khỏi queue
- empty() : kiểm tra xem queue có rỗng hay không
- front() : trả về giá trị phần tử ở đầu queue, mà không hủy nó
Lưu trữ queue
- Lưu trữ kế tiếp dùng mảng
- Lưu trữ sử dụng danh sách móc nối
Lưu trữ bằng mảng
Kiểm tra queue rỗng:
- Kiểm tra hàng đợi được lưu bởi mảng queue .
- Trả về giá trị 1 nếu queue rỗng(không có phần tử nào)
- Ngược lại thì trả về 0
int Empty(int queue[], int front, int rear) {
if (rear == front) return 1;
else return 0;
} Thêm một phần tử mới vào queue
- Thêm một phần tử mới vào queue lưu bởi mảng queue[]
- Nếu queue chưa đầy thì thêm value vào queue, trả về giá trị 0 (thêm thành công)
- Ngược lại thì trả về giá trị ‐1(thêm không thành công)
int enQueue(int queue[], int & rear, int value) {
if (rear < MAX - 1) {
rear = rear + 1;
queue[rear] = value;
return 0;
} else {
printf("queue da day !\n");
return -1;
}
} Lấy một phần tử khỏi queue
- Lấy một phần tử ra khỏi queue lưu bởi mảng queue[]
- Nếu queue khác rỗng thì lấy một phần tử ra khỏi queue, giá trị phần tử đó chứa trong value, trả về giá trị 0 (lấy thành công)
- Ngược lại thì trả về giá trị ‐1(không thành công)
int deQueue(int queue[], int & front, int rear, int & value) {
if (front == rear) {
printf("Queue rong !\n");
return‐ 1;
}
front = front + 1;
value = queue[front];
} Trả về giá trị phần tử đang ở đầu queue
- Lấy giá trị phần tử ở đầu queue
- Nếu queue khác rỗng thì lấy giá trị phần tử ở đầu queue gán cho value, trả về giá trị 0 (lấy thành công)
- Ngược lại thì trả về giá trị ‐1(không thành công)
int Front(int queue[], int front, int rear, int & value) {
if (front == rear) {
printf("Queue rong !\n");
return‐ 1;
}
value = queue[front + 1];
}
#define MAX 10
int main() {
int queue[MAX];
int front, rear;
int n, value;
front = rear = (-1);
enQueue(queue, rear, 10);
if (empty(queue, front, rear) == 1)
printf("Queue dang rong!\n");
else {
Front(queue, front, rear, value);
printf("Dau queue : %d\n", value);
}
getch();
} Lưu trữ bằng mảng
Sử dụng queue dạng vòng
Ban đầu:
int Front(int queue[], int front, int rear, int & value) {
if (front == rear) {
printf("Queue rong !\n");
return -1;
}
value = queue[(front + 1) % MAX];
}
int enQueue(int queue[], int front, int & rear, int value) {
if (((rear + 1) % MAX) == front) {
printf("queue da day, khong the them % d!\n ", value);
return‐ 1;
}
rear = (rear + 1) % MAX;
queue[rear] = value;
return 0;
}
Lưu trữ bằng danh sách móc nối
- enQueue() : thêm phần tử vào đầu danh sách móc nối
- deQueue(): xóa phần tử ở cuối danh sách móc nối
int empty(NODE * front, NODE * rear) {
if (front == NULL) return 1;
else return 0;
}
int enQueue(NODE * & front, NODE * & rear, int value) {
NODE * ptr = (NODE * ) malloc(sizeof(NODE));
if (ptr == NULL) {
printf("Khong con du bo nho !\n");
return -1;
}
ptr -> data = value;
ptr -> pNext = NULL;
if (front == NULL) {
front = ptr;
rear = front;
} else {
rear -> pNext = ptr;
rear = ptr;
}
return 0;
}
int deQueue(NODE *&front, NODE *&rear, int &value)
int front(NODE * front, NODE *rear, int &value)
Ứng dụng
Mô phỏng hàng đợi tại một phòng khámTại phòng khám, mỗi người đến được nhận một số theo thứ tự tăng dần, thứ tự phục vụ theo thứ tự các số đó. Giả sử mỗi người khách đến có thời gian phục vụ là t (t là một giá trị nguyên trong khoảng 1‐9). Tại mỗi thời điểm xác suất có một khác mới là a (0<a<1).
|
