Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Queue

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Queue

1. Điều kiện biên của queue vòng 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
2. Một số cách hiện thực queue liên tục Một array với front là phần tử đầu và tất cả các phần tử sẽ được dời lên khi lấy ra một phần tử. Một array có hai chỉ mục luôn tăng chỉ đến phần tử đầu và cuối. Một array vòng có chỉ mục front và rear và một ô luôn trống. Một array vòng có chỉ mục front và rear và một cờ (flag) cho biết queue là đầy (rỗng) chưa. Một array vòng với chỉ mục front và rear có các giá trị đặc biệt cho biết queue đang rỗng. Một array vòng với chỉ mục front và rear và một số chứa số phần tử của queue. 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
3. Hiện thực queue liên tục const int maxqueue = 10; // small value for testing template class Queue { public: Queue( ); bool empty( ) const; Error_code serve( ); Error_code append(const Entry &item); Error_code retrieve(Entry &item) const; protected: int count; int front, rear; Entry entry[maxqueue]; }; 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
4. Khởi tạo và kiểm tra rỗng Khởi tạo: template Queue ::Queue( ) { count = 0; rear = maxqueue − 1; front = 0; } Kiểm tra rỗng: Dùng biến count để template biết số phần tử bool Queue ::empty( ) const { trong queue return count == 0; } 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
5. Thêm một giá trị vào queue Giải thuật: 1. Nếu hàng đầy 1.1. Báo lỗi overflow 2. Tính toán vị trí cuối mới theo array vòng 3. Gán giá trị vào vị trí cuối mới này 4. Tăng số phần tử lên 1 4. Báo success front rear A B C D 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
6. Loại một giá trị khỏi queue Giải thuật: 1. Nếu hàng rỗng 1.1. Báo lỗi underflow 2. Tính toán vị trí đầu mới theo array vòng 3. Giảm số phần tử đi 1 3. Báo success front rear A B C D 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
7. Thêm/loại một giá trị – Mã C++ template Error_code Queue ::append(const Entry &item) { if (count >= maxqueue) return overflow; count++; rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1); entry[rear] = item; return success; } template Error_code Queue ::serve() { if (count <= 0) return underflow; count−−; front = ((front + 1) == maxqueue) ? 0 : (front + 1); return success; } 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
8. Ứng dụng: Giả lập phi trường Mô tả: 1. Sử dụng hàng đợi runway cho việc cất và hạ cánh. 2. Một máy bay có thể cất hoặc hạ cánh trong một đơn vị thời gian. 3. Tại một thời điểm, số máy bay đến là ngẫu nhiên. 4. Máy bay hạ cánh được ưu tiên trước máy bay cất cánh. 5. Các máy bay chờ cất/hạ cánh được chứa vào các hàng đợi tương ứng và với số lượng giới hạn. 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
9. Giả lập phi trường – Hàng đợi enum Runway_activity {idle, land, takeoff}; class Runway { public: Runway(int limit); Error_code can_land(const Plane ¤t); Error_code can_depart(const Plane ¤t); Runway_activity activity(int time, Plane &moving); void shut_down(int time) const; private: Extended queue landing; Extended queue takeoff; int queue_limit; }; 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
10. Giả lập phi trường – Hạ cánh Error_code Runway :: can_land(const Plane ¤t) { Error_code result; if (landing.size( ) < queue_limit) result = landing.append(current); else result = fail; num_land_requests++; if (result != success) num_land_refused++; else num_land_accepted++; return result; } 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
11. Giả lập phi trường – Xử lý Runway_activity Runway::activity(int time, Plane &moving) { Runway_activity in_progress; if (!landing.empty( )) { landing.retrieve(moving); in_progress = land; landing.serve( ); } else if (!takeoff.empty( )) { takeoff.retrieve(moving); in_progress = takeoff; takeoff.serve( ); } else in_progress = idle; return in_progress; } 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue
12. Giả lập phi trường – Giả lập for (int current_time = 0; current_time < end_time; current_time++) { int number_arrivals = variable.poisson(arrival_rate); for (int i = 0; i < number_arrivals; i++) { Plane current_plane(flight_number++, current_time, arriving); if (small_airport.can_land(current_plane) != success) current_plane.refuse( ); } int number_departures = variable.poisson(departure_rate); for (int j = 0; j < number_departures; j++) { Plane current_plane(flight_number++, current_time, departing); if (small_airport.can_depart(current_plane) != success) current_plane.refuse( ); } Plane moving_plane; switch (small_airport.activity(current_time, moving_plane)) { case land: moving_plane.land(current_time); break; case takeoff: moving_plane.fly(current_time); break; case idle: run_idle(current_time); } } 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 3: Queue