Dequeue และ Priority Queue ใน C++ STL

ภาพรวม Queue Variants

Queue แบบปกติเป็น FIFO (First In First Out) แต่มี 2 แบบเวเรียนที่สำคัญ:

1. Deque (Double-Ended Queue) - เพิ่ม/ลดได้ทั้ง 2 ข้าง
2. Priority Queue - จัดเรียงตาม Priority (ไม่ใช่ลำดับเข้ามา)

Part 1: Deque (Double-Ended Queue)

#include <deque>

คุณสมบัติ

• Random Access: operator[], at() - O(1)
• Insert/Delete ทั้ง Front และ Back - O(1) Amortized
• ไม่มีการจัดเรียงอัตโนมัติ (เก็บลำดับการ Insert)
• Iterator เป็น Random Access Iterator

ฟังก์ชันหลัก

ตัวอย่าง Deque

#include <iostream>
#include <deque>
using namespace std;

void printDeque(const deque& dq) {
    for (int x : dq) cout << x << " ";
    cout << endl;
}

int main() {
    deque dq;
    
    dq.push_back(10);   // [10]
    dq.push_front(20);  // [20, 10]
    dq.push_back(30);   // [20, 10, 30]
    dq.push_front(15);  // [15, 20, 10, 30]
    
    cout << "Deque: "; printDeque(dq);
    cout << "Size: " << dq.size() << endl;
    cout << "Front: " << dq.front() << endl;
    cout << "Back: " << dq.back() << endl;
    cout << "At(2): " << dq.at(2) << endl;  // 10
    
    dq.pop_front();   // Remove 15 → [20, 10, 30]
    cout << "After pop_front: "; printDeque(dq);
    
    dq.pop_back();    // Remove 30 → [20, 10]
    cout << "After pop_back: "; printDeque(dq);
    
    return 0;
}

ผลลัพธ์ Deque

Deque: 15 20 10 30
Size: 4
Front: 15
Back: 30
At(2): 10
After pop_front: 20 10 30
After pop_back: 20 10

Part 2: Priority Queue

#include <queue>

คุณสมบัติ

• Top Element = Highest Priority (Default: Max Heap)
• ไม่มี Random Access (ไม่มี operator[])
• Insert/Delete Top - O(log n)
• รองรับ Custom Comparator

ตัวอย่าง Priority Queue

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

void printPQ(priority_queue pq) {
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

int main() {
    // Max Heap (Default)
    priority_queue maxPQ;
    maxPQ.push(10);
    maxPQ.push(20);
    maxPQ.push(30);
    maxPQ.push(5);
    maxPQ.push(1);
    
    cout << "Max Heap: "; printPQ(maxPQ);  // 30 20 10 5 1
    
    // Min Heap
    priority_queue, greater> minPQ;
    minPQ.push(10);
    minPQ.push(20);
    minPQ.push(30);
    minPQ.push(5);
    minPQ.push(1);
    
    cout << "Min Heap: "; printPQ(minPQ);  // 1 5 10 20 30
    
    return 0;
}

ผลลัพธ์ Priority Queue

Max Heap: 30 20 10 5 1
Min Heap: 1 5 10 20 30

เปรียบเทียบ Deque vs Priority Queue vs Queue

การใช้งานร่วมกัน: Deque เป็น Container ของ Priority Queue

Priority Queue ใน STL ใช้ Container ภายใน (Default: vector) แต่สามารถระบุเป็น deque ได้:

// ใช้ deque เป็น underlying container
priority_queue> pq1;  // Max heap with deque
priority_queue, greater> pq2;  // Min heap with deque

ประยุกต์ใช้ Deque

• Sliding Window Maximum/Minimum
• Palindrome Checking
• Browser History (Back/Forward)
• Undo/Redo System
• BFS 0-1 Shortest Path (Deque as Queue)

ประยุกต์ใช้ Priority Queue

• Dijkstra / A* Pathfinding
• Huffman Coding
• Task Scheduling (OS)
• K-th Largest Element
• Event Simulation

Best Practices

• ใช้ deque เมื่อต้องการ Insert/Delete ทั้ง 2 ข้าง + Random Access
• ใช้ priority_queue เมื่อต้องการเข้าถึง Max/Min บ่อย
• หลีกเลี่ยงการ Copy Priority Queue (มีค่าใช้จ่ายสูง) ใช้ Reference หรือ Move
• สำหรับ Min Heap: priority_queue<T, vector<T>, greater<T>>
• Custom Struct: ใช้ Lambda หรือ Struct ที่มี operator()