Bài giảng bài 2: Hàng đợi (Queue0

Câu hỏi kiểm tra Trình bày cách khai báo một cấu trúc của một ngăn xếp ? Trả lời typedef struct { int top; int nodes[MAXSIZE]; } stack; Bài 2. HÀNG ĐỢI (QUEUE) CBGD: Trần Việt Khánh MỤC TIÊU Sau bài học này, sinh viên có khả năng: Trình bày được định nghĩa hàng đợi (Queue)  Cài đặt được hàng đợi  Vận dụng hàng đợi vào các bài toán (tính toán, sắp hàng bán vé tại rạp chiếu phim,...) NỘI DUNG I/ Định nghĩa II/ Cài đặt Queue (hàng đợi) Khai báo cấu trúc của một hàng đợi Các tác vụ trên hàng đợi I/ Định nghĩa Queue (hàng đợi) là một cấu trúc trừu tượng, được thực hiện theo cơ chế FIFO (First In First Out): phần tử được đưa vào hàng đợi trước sẽ được lấy ra trước tiên. - Queue được cài đặt trên cơ sở mảng (bao gồm nhiều phần tử). - Queue có 2 chỉ số: chỉ số front để chỉ định phần tử đầu hàng đợi, chỉ số rear để chỉ định phần tử cuối hàng đợi. Hình vẽ minh họa hàng đợi (Queue) Sử dụng mảng Q để chứa các phần tử và 2 biến chỉ số front, rear để chỉ định các phần tử trong mảng Q. II/ Cài đặt Queue (hàng đợi) 1. Khai báo cấu trúc hàng đợi // Khai báo cấu trúc của một Queue typedef struct { int front,rear; int nodes[MAXSIZE]; } queue; Khởi tạo hàng đợi rỗng void CreateQueue(queue &q) { q.front=-1; q.rear=-1; } 2. Các tác vụ trên Queue (hàng đợi) Kiểm tra hàng đợi có bị rỗng không bool EmptyQueue(queue q) { return ( q.front == q.rear); } Đưa một phần tử vào hàng đợi (Queue) void AddQueue (queue &q, int x) { q.rear=(q.rear+1) % MAXSIZE; q.nodes[q.rear]=x; } Lấy một phần tử ra khỏi hàng đợi (Queue) int RemoveQueue(queue &q) { int x; q.front=(q.front+1) % MAXSIZE; x=q.nodes[q.front]; return x; } Viết chương trình áp dụng Queue (hàng đợi) để nhập xuất một chuỗi ký tự. 2. Có thể áp dụng Queue (hàng đợi) để săp xếp bán vé xem phim cho khán giả tại rạp hát. BÀI TẬP