Deque

Deque (Double-Ended Queue) menggeneralisasi stack dan queue — elemen dapat ditambah atau dihapus dari kedua ujung (front dan back) dalam O(1). Bayangkan deck kartu yang dapat diambil dari atas atau bawah. Inilah struktur paling fleksibel di antara queue dan stack: deque dapat berperilaku sebagai stack (push_back/pop_back), sebagai queue (push_back/pop_front), atau sebagai keduanya secara bersamaan. Pada Chapter ini kita akan memahami implementasi std::deque STL (chunked array), operasi yang didukung, dan aplikasi utamanya: sliding window maximum dengan deque monotonic yang menjadi pondasi banyak algoritma O(n).

Anatomi Deque #

Deques mendukung empat operasi inti O(1):

Operasi	Aksi
`push_back(v)`	Tambah di belakang
`push_front(v)`	Tambah di depan
`pop_back()`	Hapus dari belakang
`pop_front()`	Hapus dari depan
`front()`, `back()`	Akses ujung tanpa hapus

Berbeda dari queue yang hanya satu arah, deque memungkinkan dua arah.

Implementasi std::deque #

std::deque bukan array kontigu penuh seperti std::vector. Ia menggunakan chunked array — kumpulan blok berukuran tetap (mis. 512 byte) yang di-link via peta pointer. Operasi push_front mengalokasikan chunk baru di depan bila chunk depan penuh; push_back menambah chunk baru di belakang bila chunk belakang penuh.

flowchart TD Map["peta pointer"] Map --> C0["Chunk 0<br/>[a, b, c]"] Map --> C1["Chunk 1<br/>[d, e, f]"] Map --> C2["Chunk 2<br/>[g, h, _]"] Style["front = chunk 0 [0]<br/>back = chunk 2 [1]"]

Konsekuensi:

Akses acak [i] tetap O(1) — index chunk + offset dalam chunk.
Cache locality lebih rendah dari vector (chunk terpisah), tetapi lebih tinggi dari linked list.
Memori overhead: 1 pointer per elemen (di chunk peta), tetapi chunk sendiri kontigu — overhead rata-rata kecil.

Perbandingan Struktur Linear #

Struktur	push_front	push_back	pop_front	pop_back	Random access	Memori
`std::vector`	O(n)	O(1) amort	O(n)	O(1)	O(1)	Kontigu
`std::deque`	O(1)	O(1)	O(1)	O(1)	O(1)	Chunked
`std::list`	O(1)	O(1)	O(1)	O(1)	Tidak	Pointer per elemen

Demo std::deque #

Mekanisme: Empat Operasi Dasar #

cpp
#include <iostream>
#include <deque>

void demo_deque() {
    std::deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(5);
    d.push_front(1);

    std::cout << "deque setelah 4 operasi: ";
    for (int x : d) std::cout << x << ' ';
    std::cout << '\n';

    d.pop_front();
    d.pop_back();
    std::cout << "setelah pop_front + pop_back: ";
    for (int x : d) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    std::cout << "size  = " << d.size() << '\n';
}

Output yang Dihasilkan:

text
deque setelah 4 operasi: 1 5 10 20 
setelah pop_front + pop_back: 5 10 
front = 5, back = 10
size  = 2

d.push_front(5); d.push_front(1);: dua elemen ditambah di depan, urutan 1 (paling depan) lalu 5. Deque tumbuh ke kiri.
d.push_back(10); d.push_back(20);: dua elemen ditambah di belakang, urutan 10 lalu 20. Deque tumbuh ke kanan.
Hasil [1, 5, 10, 20]: kombinasinya — 1, 5 dari push_front (urutan terbalik); 10, 20 dari push_back (urutan asli).
pop_front + pop_back: keluarkan 1 (front) dan 20 (back). Hasil [5, 10].

Aplikasi Utama: Sliding Window Maximum #

Aturan #

Diberikan array a dan window size k, untuk setiap window berukuran k (dari kiri ke kanan), temukan nilai maksimum di dalam window. Soal LeetCode #239.

Mekanisme: Monotonic Deque #

Naif: untuk setiap window, scan elemen — O(n·k). Pendekatan deque monotonic menurun O(n) total:

Iterasi i dari 0 ke n-1.
Buang indeks lama: bila dq.front() <= i - k (di luar window), pop_front.
Jaga monotonic: bila a[dq.back()] <= a[i], pop_back — elemen yang lebih kecil dari a[i] di belakang deque tidak akan pernah jadi max (karena a[i] lebih besar dan lebih baru).
Push i ke deque.
Output max = a[dq.front()] saat i >= k - 1 (window sudah lengkap).

Invariant: deque selalu berisi indeks dengan nilai a[i] menurun dari front ke back. Front selalu menyimpan max window saat ini.

flowchart LR A["window: [1, 3, -1]"] -->|"deque: [3, -1]"| M1["max = 3"] A2["geser ke [3, -1, -3]"] -->|"deque: [3, -1, -3]"| M2["max = 3"]

Kode: Sliding Window Maximum O(n) #

cpp
std::vector<int> sliding_window_max(const std::vector<int>& a, int k) {
    std::vector<int> hasil;
    std::deque<int> dq;  // menyimpan indeks, nilai a[i] menurun dari front
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        // Buang indeks yang di luar window
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        // Buat deque menurun: buang belakang yg lebih kecil dari a[i]
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) hasil.push_back(a[dq.front()]);
    }
    return hasil;
}

Line-by-line #

std::deque<int> dq;: deque menyimpan indeks (bukan nilai) agar kita tahu posisi window. Urutan indeks meningkat (push_back i setiap iterasi), tetapi nilai a[i] menurun.
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();: buang indeks yang sudah di luar window. Window adalah [i-k+1, i], jadi indeks <= i-k harus keluar.
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();: hapus indeks di belakang yang nilainya <= a[i]. Mereka tidak akan pernah menjadi max — a[i] lebih besar dan akan bertahan lebih lama di window.
dq.push_back(i);: tambah indeks saat ini. Setelah langkah 2 dan 3, deque berisi indeks dengan nilai menurun dari front ke back.
if (i >= k - 1) hasil.push_back(a[dq.front()]);: bila window sudah lengkap (sudah ada k elemen dari indeks i-k+1 hingga i), output max = a[dq.front()].

Kompleksitas: O(n) time, O(k) space. Setiap indeks masuk dan keluar deque maksimal satu kali.

Kode Lengkap Deque #

cpp
#include <iostream>
#include <deque>
#include <vector>
#include <list>
#include <algorithm>

void demo_deque() {
    std::deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(5);
    d.push_front(1);

    std::cout << "deque setelah 4 operasi: ";
    for (int x : d) std::cout << x << ' ';
    std::cout << '\n';

    d.pop_front();
    d.pop_back();
    std::cout << "setelah pop_front + pop_back: ";
    for (int x : d) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    std::cout << "size  = " << d.size() << '\n';
}

// Sliding window max dengan deque — O(n) total
std::vector<int> sliding_window_max(const std::vector<int>& a, int k) {
    std::vector<int> hasil;
    std::deque<int> dq;  // menyimpan indeks, nilai a[i] menurun dari front
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        // Buang indeks yang di luar window
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        // Buat deque menurun: buang belakang yg lebih kecil dari a[i]
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) hasil.push_back(a[dq.front()]);
    }
    return hasil;
}

int main() {
    std::cout << "=== std::deque Basic ===\n";
    demo_deque();

    std::cout << "\n=== Sliding Window Maximum ===\n";
    std::vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    std::cout << "array: ";
    for (int x : a) std::cout << x << ' ';
    std::cout << "\nwindow size k=" << k << '\n';
    auto maxes = sliding_window_max(a, k);
    std::cout << "max per window: ";
    for (int x : maxes) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "\n=== Komparasi Struktur ===\n";
    std::vector<int> v = {1, 2, 3};
    std::list<int> l = {1, 2, 3};
    std::deque<int> d2 = {1, 2, 3};
    std::cout << "vector  front: " << v.front() << ", back: " << v.back() << '\n';
    std::cout << "list    front: " << l.front() << ", back: " << l.back() << '\n';
    std::cout << "deque   front: " << d2.front() << ", back: " << d2.back() << '\n';
    // Operasi yang dimungkinkan
    std::cout << "\npush_front/pop_front:\n";
    std::cout << "  vector : tidak efisien (O(n))\n";
    std::cout << "  list   : O(1)\n";
    std::cout << "  deque  : O(1)\n";

    return 0;
}

Output yang Dihasilkan:

text
=== std::deque Basic ===
deque setelah 4 operasi: 1 5 10 20 
setelah pop_front + pop_back: 5 10 
front = 5, back = 10
size  = 2

=== Sliding Window Maximum ===
array: 1 3 -1 -3 5 3 6 7 
window size k=3
max per window: 3 3 5 5 6 7 

=== Komparasi Struktur ===
vector  front: 1, back: 3
list    front: 1, back: 3
deque   front: 1, back: 3

push_front/pop_front:
  vector : tidak efisien (O(n))
  list   : O(1)
  deque  : O(1)

max per window: 3 3 5 5 6 7: untuk setiap window 3-elemen pada array [1, 3, -1, -3, 5, 3, 6, 7], max adalah 3 (window 1: [1,3,-1]), 3 (window 2: [3,-1,-3]), 5, 5, 6, 7. Sesuai.
Total O(n): setiap indeks masuk deque sekali dan keluar maksimal sekali. Total operasi deque 2n — bukan n·k seperti naif.

Aplikasi Deque #

Aplikasi	Cara Pakai
Sliding window max/min	Monotonic deque — Chapter ini dan Chapter monotonic-queue
Work stealing scheduler	Worker mencuri task dari kedua ujung deque
Browser history	Push back saat navigasi; pop_back untuk back; pop_front untuk clear lama
Undo + Redo	Stack undo di back, queue redo di front
Multi-producer queue	Producer menambah dari kedua ujung berdasarkan prioritas

Ringkasan #

Deque adalah queue dua arah: push/pop O(1) di kedua ujung (front dan back).
std::deque memakai chunked array — akses acak O(1), cache locality sedang (lebih baik dari linked list).
std::vector tidak cocok untuk push_front (O(n)); pilih std::deque bila butuh operasi dua arah.
Sliding window max memanfaatkan deque monotonic: deque berisi indeks dengan nilai a[i] menurun dari front ke back. O(n) total.
Aplikasi luas: work stealing scheduler, browser history, undo+redo, dan semua algoritma sliding window.
Chapter berikutnya akan membahas monotonic stack — varian serupa untuk masalah tanpa constraint window size.