สมมติว่าเราต้องการออกแบบไดเรกทอรีโทรศัพท์ที่รองรับการดำเนินการต่อไปนี้ −
get − จะให้หมายเลขที่ยังไม่ได้มอบหมายให้ใคร
check − จะตรวจสอบว่าหมายเลขว่างหรือไม่
release − จะรีไซเคิลหรือปล่อยหมายเลข
ใช้ initializer เพื่อกำหนดหมายเลข n ตัวในตอนแรก
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดเซต s
กำหนดคิว available
initializer จะรับ maxNumbers
N := maxNumbers
ลูป i := 0 ถึง N-1 ทำ −
แทรก i ลงใน available
กำหนดฟังก์ชัน get()
ถ้าขนาดของ available เป็น 0 แล้ว −
คืนค่า -1
x := สมาชิกแรกของ available
แทรก x ลงใน s
ลบสมาชิกออกจาก available
คืนค่า x
กำหนดฟังก์ชัน check() รับ number
ถ้า number >= N หรือ number < 0 แล้ว −
คืนค่า false
คืนค่า true ถ้า number ไม่อยู่ใน s
กำหนดฟังก์ชัน release() รับ number
ถ้า check(number) แล้ว −
คืนค่า
x := number
ลบ x ออกจาก s
แทรก x ลงใน available
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#include <bits/stdc++.h> using namespace std; class PhoneDirectory { public: set<int> s; queue<int> available; int N; PhoneDirectory(int maxNumbers){ N = maxNumbers; for (int i = 0; i < N; i++) { available.push(i); } } int get(){ if (available.size() == 0) return -1; int x = available.front(); s.insert(x); available.pop(); return x; } bool check(int number){ if (number >= N || number < 0) return false; return s.find(number) == s.end(); } void release(int number){ if (check(number)) return; int x = number; s.erase(x); available.push(x); } }; main(){ PhoneDirectory ob(3); cout << (ob.get()) << endl; cout << (ob.get()) << endl; cout << (ob.check(2)) << endl; cout << (ob.get()) << endl; cout << (ob.check(2)) << endl; ob.release(2); cout << (ob.check(2)) << endl; } อินพุท
ob.get(); ob.get(); ob.check(2); ob.get(); ob.check(2); ob.release(2); ob.check(2);
เอาต์พุท
0 1 1 2 0 1
