Queue (antrian) adalah pasangan alami dari stack: jika stack melayani yang terakhir masuk lebih dulu, queue melayani yang paling awal datang. Aturan ini disebut FIFO (First In, First Out) dan meniru antrian loket yang kita alami setiap hari — nomor 101 dilayani sebelum nomor 102, tanpa kecuali. FIFO membuat queue menjadi struktur bawaan untuk setiap situasi “menunggu giliran”: buffer data yang datang lebih cepat daripada diproses, penjadwalan tugas, dan penelusuran graf level demi level (BFS). Chapter ini membangun antrian manual berbentuk circular buffer, lalu memakai std::queue untuk simulasi antrian loket dan std::deque untuk kebutuhan dua ujung.

Circular Buffer: Antrian dengan Array Tetap #

Cara paling ekonomis membangun antrian adalah array berkapasitas tetap dengan dua penunjuk: head (posisi elemen yang akan keluar) dan jumlah elemen yang sedang menunggu. Ketika penunjuk mencapai ujung array, ia kembali ke indeks 0 lewat operasi modulo — buffer “melingkar”, sehingga slot yang ditinggalkan elemen lama bisa dipakai lagi tanpa menggeser apa pun. Semua operasi bekerja di O(1): tidak ada pergeseran elemen seperti pada penyisipan di depan vector.

Program berikut mengimplementasikan antrian sirkular kapasitas 5 lalu menguji perilakunya, termasuk penolakan saat penuh dan pembungkusan indeks:

cpp 
// Antrian sirkular (circular buffer): FIFO dengan array berkapasitas tetap.
#include <iostream>
#include <vector>

class AntrianSirkular {
public:
    explicit AntrianSirkular(int kapasitas)
        : buffer_(kapasitas), kapasitas_(kapasitas), head_(0), jumlah_(0) {}

    bool penuh() const { return jumlah_ == kapasitas_; }
    bool kosong() const { return jumlah_ == 0; }

    bool enqueue(int nilai) {
        if (penuh()) return false;
        int ekor = (head_ + jumlah_) % kapasitas_;  // posisi melingkar
        buffer_[ekor] = nilai;
        ++jumlah_;
        return true;
    }

    bool dequeue(int& hasil) {
        if (kosong()) return false;
        hasil = buffer_[head_];
        head_ = (head_ + 1) % kapasitas_;  // head maju secara melingkar
        --jumlah_;
        return true;
    }

private:
    std::vector<int> buffer_;
    int kapasitas_;
    int head_;
    int jumlah_;
};

int main() {
    AntrianSirkular q(5);
    for (int n : {1, 2, 3, 4, 5}) {
        std::cout << "enqueue(" << n << ") -> "
                  << (q.enqueue(n) ? "ok" : "penuh") << '\n';
    }
    std::cout << "enqueue(6) -> " << (q.enqueue(6) ? "ok" : "penuh") << '\n';

    int keluar = 0;
    q.dequeue(keluar);
    std::cout << "dequeue() -> " << keluar << '\n';
    q.dequeue(keluar);
    std::cout << "dequeue() -> " << keluar << '\n';

    // Dua slot bebas; elemen baru melingkar menempati ujung buffer
    q.enqueue(6);
    q.enqueue(7);
    std::cout << "Isi antrian sekarang: ";
    while (q.dequeue(keluar)) {
        std::cout << keluar << ' ';
    }
    std::cout << "(urutan FIFO)\n";
    return 0;
}

Output yang Dihasilkan:

text 
enqueue(1) -> ok
enqueue(2) -> ok
enqueue(3) -> ok
enqueue(4) -> ok
enqueue(5) -> ok
enqueue(6) -> penuh
dequeue() -> 1
dequeue() -> 2
Isi antrian sekarang: 3 4 5 6 7 (urutan FIFO)

Bedah baris penting:

  1. Baris 13-19 (enqueue): posisi ekor dihitung dengan (head_ + jumlah_) % kapasitas_ — penjumlahan biasa yang “dilipat” kembali ke rentang 0..4. Bila antrian penuh, fungsi mengembalikan false alih-alih menimpa data.
  2. Baris 21-27 (dequeue): elemen di head_ diambil, lalu head_ maju satu dengan modulo yang sama. Slot lama otomatis menjadi cadangan untuk elemen berikutnya.
  3. Baris 37-42: lima enqueue mengisi seluruh kapasitas; percobaan keenam ditolak dengan pesan penuh — buffer tetap tidak melampaui 5 elemen.
  4. Baris 45-47: dua dequeue mengeluarkan 1 dan 2 sesuai urutan masuk, membuktikan sifat FIFO.
  5. Baris 51-52: enqueue(6) dan enqueue(7) menulis di indeks 0 dan 1 — slot yang ditinggalkan elemen lama, bukan di luar array.
  6. Baris 54-56: pengosongan antrian menghasilkan 3 4 5 6 7; elemen yang masuk belakangan keluar belakangan, meski datanya secara fisik tersimpan melingkar.

Perhatikan trade-off desain ini: kapasitas tetap membuat operasi sangat cepat dan tanpa alokasi memori, tetapi antrian bisa “penuh” meski memori masih tersedia. Implementasi produksi biasanya memperluas buffer secara dinamis — pola doubling yang sama seperti pada dynamic array.

Simulasi Antrian dengan std::queue #

STL menyediakan std::queue sebagai container adapter: pembungkus tipis yang hanya membuka push (masuk), pop (keluar), front (melihat terdepan), dan back. Karena operasinya dibatasi, kita tidak bisa menyusup dan merusak urutan dari tengah — batasan yang justru melindungi logika FIFO. Program berikut mensimulasikan antrian loket dan menampilkan deque untuk perbandingan:

cpp 
// Simulasi antrian layanan dengan std::queue, plus std::deque dua ujung.
#include <deque>
#include <iostream>
#include <queue>
#include <string>

int main() {
    // Bagian 1: antrian loket berbasis std::queue (FIFO murni)
    std::queue<int> antrian;
    std::cout << "-- Simulasi antrian loket --\n";
    for (int nomor : {101, 102, 103}) {
        antrian.push(nomor);
        std::cout << "Pelanggan " << nomor << " datang dan mengambil nomor\n";
    }
    while (!antrian.empty()) {
        std::cout << "Melayani nomor " << antrian.front() << '\n';
        antrian.pop();
    }

    // Datang dan dilayani bergantian: urutan tetap dijaga
    antrian.push(104);
    std::cout << "Pelanggan 104 datang\n";
    std::cout << "Melayani nomor " << antrian.front() << '\n';
    antrian.pop();
    antrian.push(105);
    std::cout << "Pelanggan 105 datang\n";
    std::cout << "Melayani nomor " << antrian.front() << '\n';
    antrian.pop();

    // Bagian 2: std::deque — antrian dua ujung
    std::deque<std::string> jalur;
    jalur.push_back("Budi");    // masuk dari belakang
    jalur.push_back("Siti");
    jalur.push_front("Dewi");   // masuk dari depan
    std::cout << "Isi deque            : ";
    for (std::size_t i = 0; i < jalur.size(); ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << jalur[i];
    }
    std::cout << '\n';
    jalur.pop_front();
    std::cout << "Depan setelah pop_front: " << jalur.front() << '\n';
    jalur.pop_back();
    std::cout << "Belakang setelah pop_back: " << jalur.back() << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
-- Simulasi antrian loket --
Pelanggan 101 datang dan mengambil nomor
Pelanggan 102 datang dan mengambil nomor
Pelanggan 103 datang dan mengambil nomor
Melayani nomor 101
Melayani nomor 102
Melayani nomor 103
Pelanggan 104 datang
Melayani nomor 104
Pelanggan 105 datang
Melayani nomor 105
Isi deque            : Dewi Budi Siti
Depan setelah pop_front: Budi
Belakang setelah pop_back: Budi

Bedah baris penting:

  1. Baris 9-19: tiga pelanggan mengantri, lalu satu loop while melayani mereka persis urut 101, 102, 103 — front() membaca terdepan, pop() melepasnya.
  2. Baris 21-29: pelanggan datang dan dilayani bergantian; urutan tetap terjaga karena setiap push(104) menempatkan 104 di belakang apa pun yang belum terlayani.
  3. Baris 31-34: std::deque menerima elemen dari dua arah — push_back("Budi") dari belakang, lalu push_front("Dewi") melompati semuanya.
  4. Baris 41-43: pop_front dan pop_back melepas elemen dari arah mana pun; isi deque Dewi Budi Siti tersisa Budi setelah kedua ujungnya dipotong.

Deque: Antrian Dua Ujung #

Nama deque adalah singkatan dari double-ended queue: antrian yang boleh dimasuki dan dikeluarkan dari depan maupun belakang, semuanya O(1). Deque adalah generalisasi — jadikan hanya ujung belakang aktif dan Anda punya stack, hanya depan aktif dan Anda punya queue. Karena itu std::queue standar secara default diimplementasikan di atas std::deque, dan deque juga menjadi tempat parkir nyaman untuk algoritma seperti BFS yang membutuhkan antrean cepat. Di section ini, BFS pada chapter Graph akan memakai pola front-lalu-pop yang sama seperti simulasi loket di atas.

Antrian menyelesaikan masalah giliran, tetapi banyak kasus lain menuntut lompatan instan: “berapa harga mangga?” tidak boleh menelusuri seluruh daftar. Struktur berikutnya, hash table, menjawab kebutuhan pencarian langsung itu.

Rujukan resmi: std::queue dan std::deque .