Bài 2: Hàng đợi (Queue)

Chia sẻ: Nguyenvan Tung | Ngày: | Loại File: PPT | Số trang:11

Thêm vào BST

Báo xấu

193
lượt xem 31
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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,...)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài 2: Hàng đợi (Queue)

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;
Bai 2. HÀNG ĐỢI (QUEUE) ̀ CBGD: Trần Việt Khánh
• 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) MỤC TIÊU  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,...)
I/ Định nghĩa II/ Cài đặt Queue (hàng đợi) NỘI DUNG 1. Khai báo cấu trúc của một hàng đợi 2. 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)
II/ Cài đặt Queue (hàng đợi) 1. Khai báo cấu trúc hàng đợi 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. // Khai báo cấu trúc của một Queue typedef struct { int front,rear; int nodes[MAXSIZE]; } queue;
2. Các tác vụ trên Queue (hàng đợi) • Khởi tạo hàng đợi rỗng void CreateQueue(queue &q) { q.front=-1; q.rear=-1; } • 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; }
BÀI TẬP 1. 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.