📖 1. Konsep Dasar Queue

🔄 Prinsip FIFO

Elemen masuk dari REAR, keluar dari FRONT

📌 Visualisasi Queue

🌍 Analogi Kehidupan Nyata

🎖️ Konteks Pertahanan

• Antrian pesan militer — Menjaga urutan kronologis informasi
• Task scheduling radar — Pemrosesan sinyal berurutan
• Buffer surveillance — Data video/audio disimpan sementara sebelum diproses

📝 Karakteristik Queue

1. Dua ujung berbeda: FRONT (keluar) dan REAR (masuk)
2. Operasi terbatas: Insert di rear, delete di front
3. Akses terbatas: Tidak bisa akses elemen tengah langsung
4. Urutan terjaga: Sesuai waktu kedatangan

📖 2. ADT Queue

⚙️ Operasi Dasar Queue

💻 Interface Queue C++

template <typename T>
class QueueADT {
public:
    virtual void enqueue(const T& item) = 0;
    virtual T dequeue() = 0;
    virtual T front() const = 0;
    virtual bool isEmpty() const = 0;
    virtual bool isFull() const = 0;
    virtual int size() const = 0;
    virtual ~QueueADT() {}
};
                    

🧠 Quiz: Trace Operasi Queue

enqueue(10), enqueue(20), enqueue(30), 
dequeue(), front(), enqueue(40), size()
                        

📖 3. Queue dengan Array Linear

Implementasi sederhana dengan dua variabel penunjuk:

• front — indeks elemen terdepan
• rear — indeks elemen terakhir

📊 Visualisasi Array Linear

💻 Implementasi Enqueue

void enqueue(const T& item) {
    if (isFull()) {
        throw overflow_error("Queue penuh!");
    }
    rearIndex++;
    data[rearIndex] = item;
    count++;
}
                    

Kompleksitas: O(1)

💻 Implementasi Dequeue

T dequeue() {
    if (isEmpty()) {
        throw underflow_error("Queue kosong!");
    }
    T item = data[frontIndex];
    frontIndex++;
    count--;
    return item;
}
                    

Kompleksitas: O(1)

⚠️ Masalah: False Overflow

📊 Contoh False Overflow

Array capacity = 5

Tidak bisa enqueue meski ada 3 slot kosong!

🔧 Solusi False Overflow

📖 4. Circular Queue

🔄 Konsep Circular Queue

📐 Formula Circular Queue

Operator modulo (%) memastikan indeks "wrap-around"

💻 Enqueue Circular

void enqueue(const T& item) {
    if (isFull()) {
        throw overflow_error("Queue penuh!");
    }
    rearIndex = (rearIndex + 1) % capacity; // Circular!
    data[rearIndex] = item;
    count++;
}
                    

Kompleksitas: O(1)

💻 Dequeue Circular

T dequeue() {
    if (isEmpty()) {
        throw underflow_error("Queue kosong!");
    }
    T item = data[frontIndex];
    frontIndex = (frontIndex + 1) % capacity; // Circular!
    count--;
    return item;
}
                    

Kompleksitas: O(1)

📊 Visualisasi Wrap-Around

🧠 Quiz: Circular Queue Trace

enqueue(A), enqueue(B), enqueue(C), 
dequeue(), dequeue(), enqueue(D), 
enqueue(E), enqueue(F)
                        

❓ Mengapa Perlu Variabel Count?

📖 5. Queue dengan Linked List

📊 Visualisasi Linked Queue

🏗️ Struktur Node

template <typename T>
struct Node {
    T data;
    Node* next;
    
    Node(const T& value) : data(value), next(nullptr) {}
};
                    

💻 Enqueue (Linked List)

void enqueue(const T& item) {
    Node* newNode = new Node(item);
    
    if (isEmpty()) {
        frontPtr = newNode;
        rearPtr = newNode;
    } else {
        rearPtr->next = newNode;
        rearPtr = newNode;
    }
    count++;
}
                    

Kompleksitas: O(1)

💻 Dequeue (Linked List)

T dequeue() {
    if (isEmpty()) {
        throw underflow_error("Queue kosong!");
    }
    Node* temp = frontPtr;
    T item = temp->data;
    frontPtr = frontPtr->next;
    if (frontPtr == nullptr) {
        rearPtr = nullptr;  // Queue jadi kosong
    }
    delete temp;
    count--;
    return item;
}
                    

❓ Mengapa Perlu Pointer Rear?

📊 Perbandingan Implementasi

📖 6. Deque (Double-Ended Queue)

🔄 Visualisasi Deque

⚙️ Operasi Deque

Semua operasi: O(1)

🔀 Variasi Deque

💻 insertFront (Circular)

void insertFront(const T& item) {
    if (isFull()) {
        throw overflow_error("Deque penuh!");
    }
    // Geser front ke belakang (circular)
    frontIndex = (frontIndex - 1 + capacity) % capacity;
    data[frontIndex] = item;
    count++;
}
                    

Note: + capacity untuk menghindari indeks negatif

📖 7. Aplikasi Queue

• 🖨️ Print Spooler — Antrian dokumen cetak
• 🌐 BFS Traversal — Pencarian level-by-level
• ⏰ Task Scheduling — Round-robin CPU scheduling
• 📡 Buffering — I/O buffer, network packet
• 🎮 Simulasi — Simulasi antrian sistem

🎖️ Aplikasi Pertahanan

• Message Queue — Antrian pesan komunikasi militer
• Radar Processing — Buffer sinyal radar
• Command Queue — Antrian perintah C4ISR
• Event Logging — Log kejadian kronologis

🔧 Queue dengan Dua Stack

template <typename T>
class QueueUsingTwoStacks {
    stack<T> stackIn;   // Untuk enqueue
    stack<T> stackOut;  // Untuk dequeue
    
public:
    void enqueue(const T& item) {
        stackIn.push(item);  // O(1)
    }
    
    T dequeue() {
        if (stackOut.empty()) {
            // Transfer dari stackIn ke stackOut
            while (!stackIn.empty()) {
                stackOut.push(stackIn.top());
                stackIn.pop();
            }
        }
        T item = stackOut.top();
        stackOut.pop();
        return item;
    }
};
                    

Amortized: O(1)

📖 8. STL Queue & Deque

C++ menyediakan std::queue dan std::deque

💻 std::queue

#include <queue>
using namespace std;

queue<int> q;

q.push(10);        // Enqueue
q.push(20);
q.push(30);

cout << q.front(); // 10
cout << q.back();  // 30

q.pop();           // Dequeue (hapus 10)
cout << q.size();  // 2
                    

💻 std::deque

#include <deque>
using namespace std;

deque<int> dq;

dq.push_back(10);   // Insert rear
dq.push_front(5);   // Insert front
dq.push_back(15);

// Deque: [5, 10, 15]

cout << dq[1];      // 10 (random access!)

dq.pop_front();     // Hapus 5
dq.pop_back();      // Hapus 15