Cơ sở dữ liệu - Hàng đợi

Nội dung text: Cơ sở dữ liệu - Hàng đợi

1. HÀNG ĐỢI QUEUE
2. KHÁI NIỆM ⚫ Hàng đợi là một danh sách tuyến tính, trong đó: Việc bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu gọi là cuối hàng Việc loại bỏ một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. ⚫ Danh sách kiểu hàng đợi còn gọi là danh sách FIFO – First In First Out.
3. KHÁI NIỆM A B C D E F Loại bỏ Bổ sung Đầu hàng Cuối hàng Hình vẽ biểu diễn hàng đợi
4. BIỂU DIỄN CẤU TRÚC DỮ LIỆU ⚫ Giả sử các phần tử của HĐ có kiểu dữ liệu là Item, độ dài của HĐ là N ⚫ HĐ được lưu trong BNMT bởi mảng 1 chiều (lưu trữ kế tiếp). ⚫ Mỗi phần tử của mảng lưu một phần tử của hàng đợi ⚫ Hàng đợi được biểu diễn là một cấu trúc có 3 thành phần: Thành phần thứ nhất là mảng E lưu các phần tử của HĐ Thành phần thứ hai là biến front lưu chỉ số của phần tử đầu hàng Thành phần thứ ba là biến rear lưu chỉ số của phần tử cuối hàng ⚫ Cấu trúc dữ liệu như sau:
5. BIỂU DIỄN CẤU TRÚC DỮ LIỆU 0 1 2 3 4 5 6 7 8 9 = Max-1 E A B C D E F front = 2 rear = 7 Mảng lưu trữ hàng đợi
6. BIỂU DIỄN CẤU TRÚC DỮ LIỆU #define Max N //Định nghĩa kiểu Item struct Queue{ int front, rear; Item E[Max]; }; Queue Q; /* Q.rear = -1 -> hàng đợi rỗng, Q.rear = Max-1 -> Hàng đợi đầy */
7. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 1. Khởi tạo hàng đợi rỗng void Initialize (Queue &Q) { Q.front = 0; Q.rear = -1; } ⚫ 2. Kiểm tra hàng đợi rỗng int Empty (Queue Q) { return (Q.rear == -1); }
8. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI Max=10 0 1 2 3 4 5 6 7 8 9 E front = 0 rear = -1 Biểu diễn hàng đợi rỗng
9. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 3. Kiểm tra hàng đợi đầy int Full (Queue Q) { reurn (Q.rear == Max-1); } 10 = Max 0 1 2 3 4 5 6 7 8 9 E A B C D E F G H front = 2 rear = 9 Biểu diễn hàng đợi đầy
10. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 4. Bổ sung một phần tử vào cuối hàng đợi 10 = Max 0 1 2 3 4 5 6 7 8 9 E A B C D E F X G front = 2 rear = 7 Mảng lưu trữ hàng đợi
11. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 4. Bổ sung một phần tử vào cuối hàng đợi 10 = Max 0 1 2 3 4 5 6 7 8 9 E A B C D E F X G front = 2 rear = 8 Mảng lưu trữ hàng đợi
12. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 4. Bổ sung một phần tử vào cuối hàng đợi 10 = Max 0 1 2 3 4 5 6 7 8 9 E A B C D E F G front = 2 rear = 8 Mảng lưu trữ hàng đợi
13. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 4. Bổ sung một phần tử vào cuối hàng đợi int AddQ(Queue &Q, Item X) { If (Full(Q)) return 0; else { Q.rear++; Q.E[Q.rear] = X; return 1; } } Hàm AddQ thực hiện bổ sung một phần tử vào cuối hàng, hàm trả về 1 nếu bổ sung thành công, ngược lại hàm trả về 0
14. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 5. Lấy ra một phần tử ở đầu hàng đợi Trường hợp hàng đợi có nhiều hơn 1 phần tử 10 = Max 0 1 2 3 4 5 6 7 8 9 E A B C D E F X front = 2 rear = 7 Mảng lưu trữ hàng đợi
15. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 5. Lấy ra một phần tử ở đầu hàng đợi Trường hợp hàng đợi có nhiều hơn một phần tử 10 = Max 0 1 2 3 4 5 6 7 8 9 E B C D E F X A front = 3 rear = 7 Mảng lưu trữ hàng đợi
16. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 5. Lấy ra một phần tử ở đầu hàng đợi Trường hợp hàng đợi có 1 phần tử 10 = Max 0 1 2 3 4 5 6 7 8 9 E B rear = 3 X front = 3 Mảng lưu trữ hàng đợi
17. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 5. Lấy ra một phần tử ở đầu hàng đợi Trường hợp hàng đợi có 1 phần tử 10 = Max 0 1 2 3 4 5 6 7 8 9 E B front = 0 rear = -1 X Hàng đợi rỗng
18. CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI ⚫ 5. Lấy ra một phần tử ở đầu hàng đợi int DeleteQ(Queue &Q, Item &X) { if (Empty(Q)) return 0; else { X = Q.E[Q.front]; if (Q.front == Q.rear) Initialize(Q); else Q.front = Q.front + 1; return 1; } } Hàm DeleteQ thực hiện lấy ra một phần tử ở đầu hàng, hàm trả về 1 nếu lấy ra thành công, ngược lại hàm trả về 0
19. ỨNG DỤNG ⚫Viết chương trình: Nhập một chuỗi ký tự, sử dụng hàng đợi, việc nhập kết thúc khi gõ Enter In chuỗi ra màn hình Đếm các nguyên âm trong chuỗi