Double-Ended Priority Queue ใน C++ โดยใช้ Set

บทนำ

Double-Ended Priority Queue (Deque Priority Queue) คือโครงสร้างข้อมูลที่รองรับการเข้าถึงและลบทั้งค่าต่ำสุดและค่าสูงสุดได้อย่างมีประสิทธิภาพ ใน C++ สามารถนำ `std::set` มาใช้งานได้โดยตรง เนื่องจาก set จัดเก็บข้อมูลเรียงลำดับอัตโนมัติ

เมธอดที่รองรับ

• size() - คืนขนาดของคิว
• is_empty() - ตรวจสอบว่าคิวว่างหรือไม่
• insert(x) - เพิ่มสมาชิกใหม่
• get_start() - ดึงค่าต่ำสุด (ซ้ายสุด)
• get_end() - ดึงค่าสูงสุด (ขวาสุด)
• delete_start() - ลบค่าต่ำสุด
• delete_end() - ลบค่าสูงสุด

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct doubleEndedQueue {
    set<int> s;
    int size() {
        return s.size();
    }
    string is_empty() {
        return s.size() == 0 ? "True" : "False";
    }
    void insert(int x) {
        s.insert(x);
    }
    int get_start() {
        return *(s.begin());
    }
    int get_end() {
        return *(s.rbegin());
    }
    void delete_start() {
        if (s.size() == 0) return;
        s.erase(s.begin());
    }
    void delete_end() {
        if (s.size() == 0) return;
        auto end = s.end();
        end--;
        s.erase(end);
    }
};

int main() {
    doubleEndedQueue d;
    cout << "is empty: " << d.is_empty() << endl;
    d.insert(1);
    d.insert(2);
    d.insert(3);
    d.insert(4);
    d.insert(5);
    cout << "is empty: " << d.is_empty() << endl;
    cout << "end: " << d.get_end() << endl;
    d.delete_end();
    cout << "end: " << d.get_end() << endl;
    cout << "start: " << d.get_start() << endl;
    d.delete_start();
    cout << "start: " << d.get_start() << endl;
    return 0;
}

ผลลัพธ์

is empty: True
is empty: False
end: 5
end: 4
start: 1
start: 2

คำอธิบาย

`std::set` ใช้ Red-Black Tree ด้านใน ทำให้การ insert, delete, และการเข้าถึง min/max ใช้เวลา O(log n) ซึ่งเหมาะสำหรับ Priority Queue แบบ Double-Ended

สรุป

การใช้ set สร้าง Double-Ended Priority Queue ได้ง่ายและมีประสิทธิภาพ ไม่ต้องเขียนโครงสร้างข้อมูลซับซ้อนเอง