Implementasi Queue

Implementasi queue yang benar memerlukan trik agar enqueue dan dequeue keduanya O(1). Tiga pendekatan utama: array dengan circular buffer, linked list dengan head/tail pointer, dan std::queue<T, Container> dari STL. Pada Chapter ini kita akan membedah ketiganya, memahami trik circular (tail + 1) % capacity yang mengatasi masalah pemborosan memori pada array queue, dan melihat bagaimana std::queue berperan sebagai adapter untuk container STL.

Pendekatan 1: Array dengan Circular Buffer #

Aturan #

Implementasi queue dengan array statis tanpa realokasi. Elemen di-dequeue dengan majukan pointer head, di-enqueue dengan majukan pointer tail. Saat pointer mencapai akhir array, ia wrap ke 0 dengan operasi modulo.

Mekanisme: Trik Circular #

flowchart LR subgraph Buffer["buf_[0..3] (kapasitas 4)"] S0["0"] S1["1"] S2["2"] S3["3"] end H["head_ = 0"] T["tail_ = 0"]

Pada awalnya head_ = tail_ = 0 (queue kosong). Setelah enqueue(1), enqueue(2), enqueue(3), enqueue(4):

head_ = 0 (elemen 1 di posisi 0)
tail_ = 0 (wrap! setelah posisi 3, kembali ke 0)
size_ = 4 (penuh)

Setelah dequeue dua kali (keluarkan 1, 2):

head_ = 2 (elemen 3 sekarang di depan)
tail_ = 0 (tetap)
size_ = 2

Sekarang enqueue(5), enqueue(6):

enqueue(5): tulis di buf_[0] (tail), maju tail_ ke 1
enqueue(6): tulis di buf_[1], maju tail_ ke 2
size_ = 4 (penuh lagi)

Slot yang ditinggalkan oleh dequeue tadi sekarang dipakai ulang — inilah inti circular buffer.

Kode: ArrayQueue #

cpp
template <typename T>
class ArrayQueue {
public:
    explicit ArrayQueue(std::size_t cap)
        : buf_(cap), cap_(cap), head_(0), tail_(0), size_(0) {}

    void enqueue(const T& v) {
        if (size_ == cap_) throw std::overflow_error("queue penuh");
        buf_[tail_] = v;
        tail_ = (tail_ + 1) % cap_;
        ++size_;
    }
    T dequeue() {
        if (size_ == 0) throw std::out_of_range("queue kosong");
        T v = buf_[head_];
        head_ = (head_ + 1) % cap_;
        --size_;
        return v;
    }
    const T& front() const {
        if (size_ == 0) throw std::out_of_range("queue kosong");
        return buf_[head_];
    }
    bool empty() const { return size_ == 0; }
    bool full() const { return size_ == cap_; }
    std::size_t size() const { return size_; }
private:
    std::vector<T> buf_;
    std::size_t cap_;
    std::size_t head_;
    std::size_t tail_;
    std::size_t size_;
};

Line-by-line #

buf_(cap), cap_(cap), head_(0), tail_(0), size_(0): member init list — buffer dialokasikan di constructor dengan ukuran cap. head_ dan tail_ sama-sama 0 (queue kosong).
buf_[tail_] = v; (di enqueue): tulis elemen baru di posisi tail. Bila tail sudah di posisi terakhir dan size < cap, elemen ditulis menimpa slot lama yang sudah di-dequeue.
tail_ = (tail_ + 1) % cap_; (di enqueue): maju tail dengan modulo. Bila tail di cap-1, hasil modulo kembali ke 0 — slot slot di awal array digunakan ulang.
head_ = (head_ + 1) % cap_; (di dequeue): maju head dengan modulo yang sama.
bool full() const { return size_ == cap_; }: queue penuh bila size_ == cap_. Modulo membuat head_ == tail_ tidak bisa dipakai untuk membedakan kosong vs penuh (keduanya sama), jadi kita andalkan size_ sebagai pembeda.

Pendekatan 2: Linked List Queue #

Mekanisme: head di Depan, tail di Belakang #

Singly linked list dengan dua pointer:

head_ menunjuk ke node depan (akan di-dequeue berikutnya).
tail_ menunjuk ke node belakang (tempat enqueue baru).

enqueue = push_back O(1) berkat tail pointer. dequeue = pop_front O(1) dengan update head.

Kode: ListQueue #

cpp
template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

template <typename T>
class ListQueue {
public:
    ListQueue() : head_(nullptr), tail_(nullptr), size_(0) {}
    ~ListQueue() {
        while (head_ != nullptr) {
            Node<T>* nx = head_->next;
            delete head_;
            head_ = nx;
        }
    }
    void enqueue(const T& v) {
        Node<T>* n = new Node<T>(v);
        if (tail_ == nullptr) head_ = tail_ = n;
        else { tail_->next = n; tail_ = n; }
        ++size_;
    }
    T dequeue() {
        if (head_ == nullptr) throw std::out_of_range("queue kosong");
        T v = head_->nilai;
        Node<T>* old = head_;
        head_ = head_->next;
        if (head_ == nullptr) tail_ = nullptr;  // queue jadi kosong
        delete old;
        --size_;
        return v;
    }
    const T& front() const {
        if (head_ == nullptr) throw std::out_of_range("queue kosong");
        return head_->nilai;
    }
    bool empty() const { return head_ == nullptr; }
    std::size_t size() const { return size_; }
private:
    Node<T>* head_;
    Node<T>* tail_;
    std::size_t size_;
};

Line-by-line #

if (tail_ == nullptr) head_ = tail_ = n; (di enqueue): kasus queue kosong — node baru sekaligus jadi head dan tail.
else { tail_->next = n; tail_ = n; }: tail lama menunjuk ke node baru, lalu tail diperbarui. O(1).
if (head_ == nullptr) tail_ = nullptr; (di dequeue): bila dequeue mengosongkan queue, tail juga harus di-set nullptr. Tanpa ini, tail menjadi dangling pointer.

Pendekatan 3: std::queue<T, Container> #

Sama seperti std::stack, std::queue adalah adapter. Container default adalah std::deque (double-ended queue, dibahas Chapter deque). Container harus mendukung front(), back(), push_back(), pop_front() — syarat yang dipenuhi std::deque dan std::list (bukan std::vector yang hanya pop_back).

cpp
std::queue<int> q1;                              // default: deque
std::queue<int, std::list<int>> q2;              // list

Operasi yang disediakan: push (enqueue), pop (dequeue), front, back, empty, size.

Kode Lengkap Implementasi Queue #

cpp
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stdexcept>
#include <string>

// 1. Array-based queue dengan circular trick
template <typename T>
class ArrayQueue {
public:
    explicit ArrayQueue(std::size_t cap)
        : buf_(cap), cap_(cap), head_(0), tail_(0), size_(0) {}

    void enqueue(const T& v) {
        if (size_ == cap_) throw std::overflow_error("queue penuh");
        buf_[tail_] = v;
        tail_ = (tail_ + 1) % cap_;
        ++size_;
    }
    T dequeue() {
        if (size_ == 0) throw std::out_of_range("queue kosong");
        T v = buf_[head_];
        head_ = (head_ + 1) % cap_;
        --size_;
        return v;
    }
    const T& front() const {
        if (size_ == 0) throw std::out_of_range("queue kosong");
        return buf_[head_];
    }
    bool empty() const { return size_ == 0; }
    bool full() const { return size_ == cap_; }
    std::size_t size() const { return size_; }
private:
    std::vector<T> buf_;
    std::size_t cap_;
    std::size_t head_;
    std::size_t tail_;
    std::size_t size_;
};

// 2. Linked list queue
template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

template <typename T>
class ListQueue {
public:
    ListQueue() : head_(nullptr), tail_(nullptr), size_(0) {}
    ~ListQueue() {
        while (head_ != nullptr) {
            Node<T>* nx = head_->next;
            delete head_;
            head_ = nx;
        }
    }
    void enqueue(const T& v) {
        Node<T>* n = new Node<T>(v);
        if (tail_ == nullptr) head_ = tail_ = n;
        else { tail_->next = n; tail_ = n; }
        ++size_;
    }
    T dequeue() {
        if (head_ == nullptr) throw std::out_of_range("queue kosong");
        T v = head_->nilai;
        Node<T>* old = head_;
        head_ = head_->next;
        if (head_ == nullptr) tail_ = nullptr;  // queue jadi kosong
        delete old;
        --size_;
        return v;
    }
    const T& front() const {
        if (head_ == nullptr) throw std::out_of_range("queue kosong");
        return head_->nilai;
    }
    bool empty() const { return head_ == nullptr; }
    std::size_t size() const { return size_; }
private:
    Node<T>* head_;
    Node<T>* tail_;
    std::size_t size_;
};

int main() {
    std::cout << "=== ArrayQueue (circular, kapasitas 4) ===\n";
    ArrayQueue<int> aq(4);
    aq.enqueue(1);
    aq.enqueue(2);
    aq.enqueue(3);
    aq.enqueue(4);
    std::cout << "full? " << std::boolalpha << aq.full() << '\n';
    std::cout << "deq = " << aq.dequeue() << '\n';
    std::cout << "deq = " << aq.dequeue() << '\n';
    aq.enqueue(5);  // reuse slot 0 dan 1 yang sudah dequeue
    aq.enqueue(6);
    std::cout << "size = " << aq.size() << '\n';
    while (!aq.empty()) std::cout << "  " << aq.dequeue() << '\n';

    std::cout << "\n=== ListQueue (linked list) ===\n";
    ListQueue<std::string> lq;
    lq.enqueue("alpha");
    lq.enqueue("beta");
    lq.enqueue("gamma");
    std::cout << "front = " << lq.front() << '\n';
    std::cout << "deq   = " << lq.dequeue() << '\n';
    std::cout << "deq   = " << lq.dequeue() << '\n';
    std::cout << "size  = " << lq.size() << '\n';

    std::cout << "\n=== std::queue (default deque) ===\n";
    std::queue<int> q1;
    q1.push(10); q1.push(20); q1.push(30);
    std::cout << "front = " << q1.front() << '\n';
    std::cout << "back  = " << q1.back() << '\n';
    q1.pop();
    std::cout << "front = " << q1.front() << '\n';

    std::cout << "\n=== std::queue berbasis list ===\n";
    std::queue<int, std::list<int>> q2;
    q2.push(7); q2.push(8); q2.push(9);
    std::cout << "front = " << q2.front() << '\n';
    q2.pop();
    std::cout << "front = " << q2.front() << '\n';

    return 0;
}

Output yang Dihasilkan:

text
=== ArrayQueue (circular, kapasitas 4) ===
full? true
deq = 1
deq = 2
size = 4
  3
  4
  5
  6

=== ListQueue (linked list) ===
front = alpha
deq   = alpha
deq   = beta
size  = 1

=== std::queue (default deque) ===
front = 10
back  = 30
front = 20

=== std::queue berbasis list ===
front = 7
front = 8

full? true: setelah 4 enqueue pada kapasitas 4, queue penuh. full() menggunakan size_ == cap_ — bukan head_ == tail_ (yang ambigu).
deq = 1, deq = 2: dua dequeue dari depan — keluar 1 lalu 2. head_ sekarang di indeks 2.
enqueue(5), enqueue(6): tulis di slot 0 dan 1 (yang sudah kosong karena dequeue tadi) — circular buffer bekerja. tail_ wrap dari 0 ke 1 ke 2.
Output 3 4 5 6: dequeue mengeluarkan sisanya — 3 dan 4 (sisa awal), lalu 5 dan 6 (yang baru saja ditulis di slot reuse).

Tabel Perbandingan Implementasi Queue #

Aspek	ArrayQueue (circular)	ListQueue (linked list)	std::queue (deque)
`enqueue`	O(1)	O(1)	O(1)
`dequeue`	O(1)	O(1)	O(1)
Kapasitas	Tetap (fixed)	Dinamis	Dinamis
Memori per elemen	Hanya data	Data + 8 byte pointer	Sedang (deque chunked)
Cache locality	Tinggi	Rendah	Sedang
Use case	Buffer kapasitas tetap (ring buffer)	Queue tak terbatas	Produksi default

Ringkasan #

Array circular buffer: trik modulo (tail + 1) % cap mengizinkan reuse slot yang sudah dequeue. O(1) untuk semua operasi.
Pembeda kosong vs penuh pada circular buffer: field size_ terpisah, atau sacrifice satu slot.
Linked list queue: head di depan, tail di belakang, kedua operasi O(1) berkat tail pointer.
std::queue<T, Container> adalah adapter STL; default container std::deque, bisa diganti std::list. Tidak mendukung std::vector (karena pop_front O(n) pada vector).
Untuk produksi, std::queue<T> (deque) biasanya pilihan terbaik; ArrayQueue cocok untuk fixed buffer.