Queue adalah struktur data linier dengan aturan FIFO (First In First Out) — elemen pertama yang masuk adalah yang pertama keluar. Bayangkan antrian kasir: orang pertama datang dilayani pertama, orang baru datang menempel di belakang. Pola ini muncul di banyak skenario: penjadwalan task OS, BFS traversal graph, buffer streaming multimedia, dan message queue pada sistem terdistribusi. Pada Chapter ini kita akan memahami operasi dasar queue (enqueue, dequeue, front), use case klasik, dan mengapa implementasi naif std::vector berbasis erase(begin()) menjadi O(n) — masalah yang akan dipecahkan di Chapter implementasi queue.

Mengapa FIFO Berguna #

FIFO cocok untuk masalah yang memerlukan pemeliharaan urutan kedatangan:

  • BFS (Breadth-First Search) — kunjungi node dalam urutan jarak dari sumber.
  • Scheduling — task yang datang lebih awal dilayani lebih awal (FCFS scheduler).
  • Buffer — paket data/pesan menunggu pemrosesan, diproses sesuai urutan kedatangan.
  • Producer-consumer — producer menambah item ke queue, consumer mengambil sesuai urutan.
  • Print spooler — dokumen dicetak sesuai urutan submit.

Tanpa FIFO, kita harus menyimpan timestamp atau urutan dan sorting — queue melakukan ini secara natural.

Anatomi Queue dan Operasi Dasar #

Queue memiliki operasi inti O(1) idealnya:

OperasiAksiKompleksitas ideal
enqueue(v) / push(v)Tambah v ke belakang (rear)O(1)
dequeue() / pop()Hapus elemen depan (front)O(1)
front()Lihat elemen depan tanpa hapusO(1)
empty()Apakah queue kosongO(1)
size()Jumlah elemenO(1)

Akses hanya dari dua sisi: rear untuk insert, front untuk remove. Tidak ada akses tengah seperti array.

Jebakan Implementasi Naif: std::vector #

Aturan #

Mengimplementasikan queue dengan std::vector<int> memakai push_back untuk enqueue dan erase(begin()) untuk dequeue terlihat natural. Sayangnya, erase(begin()) O(n) — semua elemen lain harus digeser ke depan.

Mekanisme: Vector Secara Internal #

std::vector menyimpan elemen dalam blok kontigu. erase(begin()) berarti menggeser elemen ke-1 hingga ke-(n-1) ke posisi 0 hingga n-2. Pada queue dengan 1 juta elemen, setiap dequeue memerlukan ~1 juta copy — sangat lambat.

Kode: NaiveQueue (Buruk!) #

cpp 
class NaiveQueue {
public:
    void enqueue(int v) { data_.push_back(v); }
    int dequeue() {
        int v = data_.front();
        data_.erase(data_.begin());  // O(n) — geser semua elemen
        return v;
    }
    int front() const { return data_.front(); }
    bool empty() const { return data_.empty(); }
    std::size_t size() const { return data_.size(); }
private:
    std::vector<int> data_;
};

Kompleksitas dequeue: O(n) — sangat buruk untuk queue dengan banyak operasi.

Workaround Naif: Vector + Index Front #

Daripada erase(begin()), kita pakai index front_idx yang naik setiap dequeue:

cpp 
void bfs_demo() {
    // ...
    std::vector<int> queue;
    std::size_t front_idx = 0;
    queue.push_back(1);
    // ...
    while (front_idx < queue.size()) {
        int cur = queue[front_idx++];
        // ...
    }
}

Keuntungan: dequeue O(1) — hanya increment index. Kerugian: memori tidak pernah dibebaskan; elemen “dequeue” tetap di vector hingga queue di-clear. Untuk queue yang sangat panjang dan aktif lama, memori membengkak.

Aturan #

BFS menjelajah graph layer demi layer dari sumber. Queue menyimpan node yang akan dikunjungi; dequeue satu node, enqueue semua neighbor yang belum dikunjungi.

Mekanisme: Queue Menjaga Urutan Jarak #

Bila kita enqueue node dengan jarak 1 dulu, lalu node dengan jarak 2, dan seterusnya — queue otomatis memproses berdasarkan jarak karena FIFO. Inilah mengapa BFS = queue (vs DFS = stack).

Kode: BFS Sederhana #

cpp 
void bfs_demo() {
    std::vector<std::vector<int>> adj(6);
    adj[1] = {2, 3};
    adj[2] = {4};
    adj[3] = {4};
    adj[4] = {5};

    std::vector<bool> visited(6, false);
    std::vector<int> queue;
    std::size_t front_idx = 0;

    queue.push_back(1);
    visited[1] = true;

    std::cout << "BFS traversal dari 1: ";
    while (front_idx < queue.size()) {
        int cur = queue[front_idx++];
        std::cout << cur << ' ';
        for (int neighbor : adj[cur]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    std::cout << '\n';
}

Line-by-line #

  1. std::vector<bool> visited(6, false);: tracking node yang sudah masuk queue — mencegah enqueue dua kali.
  2. queue.push_back(1); visited[1] = true;: enqueue sumber sekaligus tandai visited. Penting: tandai saat enqueue, bukan saat dequeue — mencegah node yang sama di-enqueue berkali-kali oleh beberapa neighbor.
  3. int cur = queue[front_idx++];: dequeue dengan increment index. O(1).
  4. for (int neighbor : adj[cur]): iterasi neighbor. Bila belum visited, enqueue dan tandai.
  5. Output 1 2 3 4 5: layer demi layer — 1 dulu, lalu 2 dan 3 (jarak 1), lalu 4 (jarak 2), lalu 5 (jarak 3).

Use Case 2: Task Buffer (Producer-Consumer Sederhana) #

Pola producer-consumer: producer menambah task ke queue, consumer mengambil sesuai FIFO. Implementasi sederhana:

cpp 
void task_buffer_demo() {
    NaiveQueue q;
    q.enqueue(101);  // task A
    q.enqueue(102);  // task B
    q.enqueue(103);  // task C

    std::cout << "Memproses task FIFO:\n";
    while (!q.empty()) {
        std::cout << "  proses task " << q.dequeue() << '\n';
    }
}

Output yang Dihasilkan:

text 
Memproses task FIFO:
  proses task 101
  proses task 102
  proses task 103

Task diproses sesuai urutan enqueue — producer-consumer dengan single consumer. Sistem produksi menambah sinkronisasi (mutex + condition variable) untuk multi-threaded.

Kode Lengkap Konsep Queue #

cpp 
#include <iostream>
#include <vector>
#include <string>

// Queue sederhana berbasis vector (naif: O(n) dequeue)
class NaiveQueue {
public:
    void enqueue(int v) { data_.push_back(v); }
    int dequeue() {
        int v = data_.front();
        data_.erase(data_.begin());  // O(n) — geser semua elemen
        return v;
    }
    int front() const { return data_.front(); }
    bool empty() const { return data_.empty(); }
    std::size_t size() const { return data_.size(); }
private:
    std::vector<int> data_;
};

// Demo BFS sederhana pada graf (adjacency list)
void bfs_demo() {
    std::vector<std::vector<int>> adj(6);
    adj[1] = {2, 3};
    adj[2] = {4};
    adj[3] = {4};
    adj[4] = {5};

    std::vector<bool> visited(6, false);
    std::vector<int> queue;
    std::size_t front_idx = 0;

    queue.push_back(1);
    visited[1] = true;

    std::cout << "BFS traversal dari 1: ";
    while (front_idx < queue.size()) {
        int cur = queue[front_idx++];
        std::cout << cur << ' ';
        for (int neighbor : adj[cur]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    std::cout << '\n';
}

// Demo buffer antrian: proses task berurutan
void task_buffer_demo() {
    NaiveQueue q;
    q.enqueue(101);
    q.enqueue(102);
    q.enqueue(103);

    std::cout << "Memproses task FIFO:\n";
    while (!q.empty()) {
        std::cout << "  proses task " << q.dequeue() << '\n';
    }
}

int main() {
    std::cout << "=== Naive Queue (vector) ===\n";
    NaiveQueue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    std::cout << "front = " << q.front() << '\n';
    std::cout << "deq   = " << q.dequeue() << '\n';
    std::cout << "deq   = " << q.dequeue() << '\n';
    std::cout << "size  = " << q.size() << '\n';

    std::cout << "\n=== Task Buffer FIFO ===\n";
    task_buffer_demo();

    std::cout << "\n=== BFS dengan Queue ===\n";
    bfs_demo();

    return 0;
}

Output yang Dihasilkan:

text 
=== Naive Queue (vector) ===
front = 1
deq   = 1
deq   = 2
size  = 1

=== Task Buffer FIFO ===
Memproses task FIFO:
  proses task 101
  proses task 102
  proses task 103

=== BFS dengan Queue ===
BFS traversal dari 1: 1 2 3 4 5

Queue vs Stack: Kapan Pilih Yang Mana #

AspekStack (LIFO)Queue (FIFO)
Akses keluarTop (terakhir masuk)Front (pertama masuk)
Use case alamiBacktracking, undo, DFSBFS, scheduling, buffer
Implementasi mudahstd::vector naturalButuh trik circular atau linked list
Reversal otomatisYa — output kebalikan inputTidak — output sesuai input

Ringkasan #

  • Queue adalah struktur FIFO dengan operasi enqueue, dequeue, front, idealnya O(1).
  • Implementasi naif std::vector + erase(begin()) memberikan dequeue O(n) — tidak dapat diterima.
  • Workaround: vector + index front (O(1) dequeue tetapi memori membengkak), atau circular buffer / linked list (akan dibahas Chapter implementasi queue).
  • Use case klasik: BFS, scheduling FCFS, producer-consumer, print spooler.
  • Aturan praktis: DFS pakai stack, BFS pakai queue — keduanya natural untuk traversal masing-masing.