Circular queue (ring buffer) adalah queue berbasis array yang menggunakan trik modulo agar slot yang sudah di-dequeue dapat dipakai ulang tanpa menggeser elemen. Tanpa trik ini, queue array statis menjadi O(n) per dequeue (karena geser) atau memori membengkak (karena slot tidak pernah dipakai ulang). Pada Chapter ini kita akan membedah trik modulo (tail + 1) % capacity, masalah ambiguitas “kosong vs penuh” saat head == tail, dan dua solusi untuk masalah tersebut. Circular queue adalah dasar dari banyak sistem produksi: kernel ring buffer, network packet queue, dan audio buffer streaming.

Mengapa Circular Queue #

Array queue naif (menggeser elemen pada erase(begin())) O(n) per dequeue. Solusi naive lain: gunakan index front_idx yang maju — dequeue O(1), tetapi memori membengkak karena slot yang ditinggalkan tidak pernah dipakai ulang.

Circular queue menyelesaikan kedua masalah:

  1. enqueue dan dequeue keduanya O(1).
  2. Slot yang sudah di-dequeue dipakai ulang — memori statis tidak membengkak.

Saat tail mencapai akhir array, ia wrap ke 0 dengan operasi modulo. Head juga wrap dengan cara yang sama.

Trik Modulo #

Operasi kunci pada circular queue:

cpp 
tail_ = (tail_ + 1) % capacity;

Bila tail_ di posisi capacity - 1 (indeks terakhir), maka (capacity - 1 + 1) % capacity = 0 — tail wrap ke awal array. Operasi yang sama berlaku untuk head.

Masalah Ambiguitas Kosong vs Penuh #

Saat head_ == tail_, kondisi ini bisa berarti:

  1. Queue kosong — tidak ada elemen, head dan tail sama-sama menunjuk ke awal.
  2. Queue penuh — head dan tail sama setelah elemen terakhir di-enqueue (atau awalnya head sama dengan tail sebelum operasi).

Dua solusi:

Solusi A: Field size_ terpisah #

Simpan size_ eksplisit. empty() = size_ == 0, full() = size_ == cap_. Buffer penuh bisa menampung cap_ elemen.

Solusi B: Sacrifice satu slot #

Alokasikan cap + 1 slot, tetapi hanya isi cap elemen. empty() = head_ == tail_, full() = (tail_ + 1) % buf.size() == head_. Memori overhead: 1 slot per queue.

Implementasi Circular Queue (Solusi B: Sacrifice Slot) #

Kode: CircularQueue #

cpp 
template <typename T>
class CircularQueue {
public:
    explicit CircularQueue(std::size_t cap)
        : buf_(cap + 1), head_(0), tail_(0) {}  // +1 untuk pembeda kosong/penuh

    void enqueue(const T& v) {
        if (full()) throw std::overflow_error("queue penuh");
        buf_[tail_] = v;
        tail_ = (tail_ + 1) % buf_.size();
    }

    T dequeue() {
        if (empty()) throw std::out_of_range("queue kosong");
        T v = buf_[head_];
        head_ = (head_ + 1) % buf_.size();
        return v;
    }

    const T& front() const {
        if (empty()) throw std::out_of_range("queue kosong");
        return buf_[head_];
    }

    bool empty() const { return head_ == tail_; }
    bool full() const { return (tail_ + 1) % buf_.size() == head_; }

    std::size_t size() const {
        return (tail_ + buf_.size() - head_) % buf_.size();
    }

private:
    std::vector<T> buf_;
    std::size_t head_;
    std::size_t tail_;
};

Line-by-line #

  1. buf_(cap + 1): alokasikan satu slot lebih banyak dari kapasitas yang diminta. Slot ekstra ini tidak pernah diisi — hanya sebagai pembeda kosong vs penuh.
  2. tail_ = (tail_ + 1) % buf_.size(); (di enqueue): majukan tail dengan modulo. Bila tail di indeks terakhir, wrap ke 0.
  3. head_ = (head_ + 1) % buf_.size(); (di dequeue): majukan head dengan modulo yang sama.
  4. bool empty() const { return head_ == tail_; }: queue kosong ketika head mengejar tail (tidak ada elemen di antara keduanya).
  5. bool full() const { return (tail_ + 1) % buf_.size() == head_; }: queue penuh ketika tail “hampir” mengejar head — slot ekstra mencegah kondisi ini menjadi sama dengan empty.
  6. std::size_t size() const { return (tail_ + buf_.size() - head_) % buf_.size(); }: hitung elemen antara head dan tail. + buf_.size() menghindari hasil negatif pada modulo (bila tail < head setelah wrap).

Demo Visual Circular Queue #

Kode berikut mencetak isi buffer dan posisi head/tail setelah setiap operasi — sehingga kita bisa melihat wrap secara visual:

cpp 
void dump() const {
    std::cout << "  buf = [";
    for (std::size_t i = 0; i < buf_.size(); ++i) {
        std::cout << buf_[i];
        if (i + 1 < buf_.size()) std::cout << ", ";
    }
    std::cout << "]  head=" << head_ << " tail=" << tail_
              << " size=" << size() << (empty() ? " (empty)" : (full() ? " (full)" : ""))
              << '\n';
}

Kode Lengkap dengan Demo #

cpp 
#include <iostream>
#include <vector>
#include <stdexcept>

template <typename T>
class CircularQueue {
public:
    explicit CircularQueue(std::size_t cap)
        : buf_(cap + 1), head_(0), tail_(0) {}  // +1 untuk pembeda kosong/penuh

    void enqueue(const T& v) {
        if (full()) throw std::overflow_error("queue penuh");
        buf_[tail_] = v;
        tail_ = (tail_ + 1) % buf_.size();
    }

    T dequeue() {
        if (empty()) throw std::out_of_range("queue kosong");
        T v = buf_[head_];
        head_ = (head_ + 1) % buf_.size();
        return v;
    }

    const T& front() const {
        if (empty()) throw std::out_of_range("queue kosong");
        return buf_[head_];
    }

    bool empty() const { return head_ == tail_; }
    bool full() const { return (tail_ + 1) % buf_.size() == head_; }

    std::size_t size() const {
        return (tail_ + buf_.size() - head_) % buf_.size();
    }

    void dump() const {
        std::cout << "  buf = [";
        for (std::size_t i = 0; i < buf_.size(); ++i) {
            std::cout << buf_[i];
            if (i + 1 < buf_.size()) std::cout << ", ";
        }
        std::cout << "]  head=" << head_ << " tail=" << tail_
                  << " size=" << size() << (empty() ? " (empty)" : (full() ? " (full)" : ""))
                  << '\n';
    }

private:
    std::vector<T> buf_;
    std::size_t head_;
    std::size_t tail_;
};

int main() {
    CircularQueue<int> cq(4);  // kapasitas efektif 4 (butuh 5 slot)
    std::cout << "Circular queue kapasitas 4 (buffer 5 slot):\n";
    cq.dump();

    std::cout << "\n--- enqueue 4 elemen ---\n";
    for (int i = 1; i <= 4; ++i) {
        cq.enqueue(i);
        std::cout << "enqueue(" << i << ")";
        cq.dump();
    }
    std::cout << "full? " << std::boolalpha << cq.full() << '\n';

    std::cout << "\n--- dequeue 2 ---\n";
    std::cout << "deq = " << cq.dequeue() << '\n';
    std::cout << "deq = " << cq.dequeue() << '\n';
    cq.dump();

    std::cout << "\n--- enqueue 5, 6 (wrap) ---\n";
    cq.enqueue(5);
    cq.dump();
    cq.enqueue(6);
    cq.dump();
    std::cout << "full? " << cq.full() << '\n';

    std::cout << "\n--- dequeue semua ---\n";
    while (!cq.empty()) {
        std::cout << "deq = " << cq.dequeue() << '\n';
        cq.dump();
    }

    return 0;
}

Output yang Dihasilkan:

text 
Circular queue kapasitas 4 (buffer 5 slot):
  buf = [0, 0, 0, 0, 0]  head=0 tail=0 size=0 (empty)

--- enqueue 4 elemen ---
enqueue(1)  buf = [1, 0, 0, 0, 0]  head=0 tail=1 size=1
enqueue(2)  buf = [1, 2, 0, 0, 0]  head=0 tail=2 size=2
enqueue(3)  buf = [1, 2, 3, 0, 0]  head=0 tail=3 size=3
enqueue(4)  buf = [1, 2, 3, 4, 0]  head=0 tail=4 size=4 (full)
full? true

--- dequeue 2 ---
deq = 1
deq = 2
  buf = [1, 2, 3, 4, 0]  head=2 tail=4 size=2

--- enqueue 5, 6 (wrap) ---
  buf = [1, 2, 3, 4, 5]  head=2 tail=0 size=3
  buf = [6, 2, 3, 4, 5]  head=2 tail=1 size=4 (full)
full? true

--- dequeue semua ---
deq = 3
  buf = [6, 2, 3, 4, 5]  head=3 tail=1 size=3
deq = 4
  buf = [6, 2, 3, 4, 5]  head=4 tail=1 size=2
deq = 5
  buf = [6, 2, 3, 4, 5]  head=0 tail=1 size=1
deq = 6
  buf = [6, 2, 3, 4, 5]  head=1 tail=1 size=0 (empty)
  1. enqueue(4) → head=0 tail=4 size=4 (full): 4 elemen dimuat, tail berada di indeks 4 (slot ekstra). Karena (4+1)%5=0 dan 0 == head, full() true — slot ekstra belum ditulis, mencegah ambiguitas dengan empty.
  2. deq = 1, deq = 2 → head=2 tail=4: head maju dua kali. Tail tetap di 4. Size jadi 2.
  3. enqueue(5) → tail=0 (wrap!): tail dari indeks 4 wrap ke 0 berkat modulo. Elemen 5 ditulis di buf_[4] (sebelum wrap), tail sekarang di 0.
  4. enqueue(6) → buf_[0] = 6: elemen 6 ditulis di buf_[0] — slot yang tadinya di-dequeue (elemen 1). Inilah inti circular buffer: slot reuse.
  5. deq = 3, 4, 5, 6: dequeue mengikuti urutan enqueue — 3 dan 4 dulu (sisa dari batch pertama), lalu 5 dan 6 (yang baru saja di-enqueue di slot yang dipakai ulang). Head berakhir di 1 setelah semua di-dequeue.
  6. Akhir head=1 tail=1 size=0 (empty): head dan tail sama — empty terdeteksi dengan benar, bukan full.

Aplikasi Nyata Circular Queue #

AplikasiCara Pakai
Kernel ring buffer (dmesg)Log kernel disimpan di circular buffer ukuran tetap; entry lama ditimpa entry baru
Audio buffer (ALSA, PulseAudio)Sample audio menunggu diputar; producer (app) dan consumer (sound card) berbagi ring
Network packet queuePaket menunggu transmisi; kapasitas tetap untuk membatasi backpressure
Keyboard buffer (BIOS)Keystroke menunggu OS baca; buffer 16 byte klasik di BIOS IBM PC
OpenGL swap chainFrame buffer yang siap ditampilkan di-queue circular

Ringkasan #

  • Circular queue = array queue dengan trik modulo (idx + 1) % capacity untuk wrap pointer.
  • Slot yang sudah di-dequeue dipakai ulang — tidak ada geser elemen, tidak ada memori membengkak.
  • Masalah ambiguitas head == tail: dua solusi — field size_ terpisah, atau sacrifice satu slot.
  • Implementasi solusi B (cap + 1 slot) memungkinkan empty dan full dideteksi murni dari head_ dan tail_.
  • Aplikasi nyata: kernel ring buffer, audio buffer, network queue, keyboard buffer, swap chain grafis.