Belajar Data Structure - Deque & Circular Buffer
Deque memungkinkan O(1) insert dan delete di kedua ujung. Di episode ini kalian memahami circular buffer sebagai implementasi deque, monotonic deque untuk sliding window maximum, serta mempraktikkan undo/redo buffer dan fixed-size caching.
#Pendahuluan
Setelah di episode 8 kita memahami priority queue dan binary heap — akses elemen berdasarkan prioritas — pada episode ini kita mempelajari deque (double-ended queue) dan circular buffer. Deque adalah generalisasi dari stack dan queue: ia memungkinkan insert dan delete di kedua ujung dengan O(1).
Deque mungkin terdengar seperti "queue yang bisa diakses dari dua sisi", tetapi kombinasi ini menghasilkan pola yang sangat powerful — terutama monotonic deque yang menjadi solusi optimal untuk sliding window maximum, salah satu masalah interview paling populer.
#Konsep Dasar
#Double-Ended Queue
Deque (disebut "deck") mendukung empat operasi utama:
| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Insert front | O(1) | Tambah di depan |
| Insert rear | O(1) | Tambah di belakang |
| Delete front | O(1) | Hapus dari depan |
| Delete rear | O(1) | Hapus dari belakang |
#Circular Buffer (Ring Buffer)
Circular buffer adalah array fixed-size yang "membungkus" — ketika index mencapai akhir, ia kembali ke awal. Ini memungkinkan O(1) insert/delete di kedua ujung tanpa perlu pointer seperti linked list.
Front pointer → [3] [5] [7] [9] [11]
← Rear pointerKetika rear pointer mencapai akhir array, ia kembali ke index 0 (jika slot tersedia).
#Implementasi Circular Buffer
class CircularBuffer:
def __init__(self, capacity):
self.capacity = capacity
self.buffer = [None] * capacity
self.front = 0
self.rear = -1
self._size = 0
def push_front(self, value):
if self.is_full():
raise IndexError("Buffer is full")
self.front = (self.front - 1) % self.capacity
self.buffer[self.front] = value
self._size += 1
def push_rear(self, value):
if self.is_full():
raise IndexError("Buffer is full")
self.rear = (self.rear + 1) % self.capacity
self.buffer[self.rear] = value
self._size += 1
def pop_front(self):
if self.is_empty():
raise IndexError("Buffer is empty")
value = self.buffer[self.front]
self.front = (self.front + 1) % self.capacity
self._size -= 1
return value
def pop_rear(self):
if self.is_empty():
raise IndexError("Buffer is empty")
value = self.buffer[self.rear]
self.rear = (self.rear - 1) % self.capacity
self._size -= 1
return value
def is_empty(self):
return self._size == 0
def is_full(self):
return self._size == self.capacity#Aplikasi Deque
#Sliding Window Maximum (Monotonic Deque)
Monotonic deque adalah deque yang elemen-elemennya selalu dalam urutan tertentu (monotonically increasing atau decreasing). Ini memungkinkan kita menyelesaikan sliding window maximum dalam O(n):
from collections import deque
def max_sliding_window(nums, k):
result = []
dq = deque()
for i in range(len(nums)):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))Monotonic deque menjaga indeks dengan nilai dalam urutan menurun. Elemen yang lebih kecil dari elemen baru dihapus karena mereka tidak akan pernah menjadi maximum selama elemen baru masih ada di window.
#Undo/Redo Buffer
Dua deque — satu untuk undo, satu untuk redo — memungkinkan editor teks melakukan undo dan redo dengan O(1):
class UndoRedoBuffer:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
def perform(self, action):
self.undo_stack.append(action)
self.redo_stack.clear()
def undo(self):
if not self.undo_stack:
return None
action = self.undo_stack.pop()
self.redo_stack.append(action)
return action
def redo(self):
if not self.redo_stack:
return None
action = self.redo_stack.pop()
self.undo_stack.append(action)
return action#Fixed-Size Caching
Circular buffer alami untuk caching: ketika buffer penuh, elemen terlama otomatis tergantikan saat elemen baru ditambahkan.
#Perbandingan dengan Stack dan Queue
| Operasi | Stack | Queue | Deque |
|---|---|---|---|
| Insert front | Tidak | Tidak | O(1) |
| Insert rear | O(1) push | O(1) enqueue | O(1) |
| Delete front | Tidak | O(1) dequeue | O(1) |
| Delete rear | O(1) pop | Tidak | O(1) |
Tip
Di Python, collections.deque sudah merupakan implementasi doubly-linked deque yang teroptimasi. Gunakan ini untuk production code, bukan implementasi custom.
#Penutup
Inti yang harus dibawa pulang:
- Deque: O(1) insert/delete di kedua ujung — generalisasi stack dan queue.
- Circular buffer: array fixed-size yang membungkus; efisien memori dan cache-friendly.
- Monotonic deque: solusi optimal O(n) untuk sliding window maximum.
- Aplikasi: sliding window, undo/redo, fixed-size caching.
- Python
collections.dequeadalah implementasi production-ready.
Ini adalah episode terakhir di Fase 2: Struktur Linear. Di episode 10 selanjutnya kita memasuki Fase 3: Trees dengan membahas binary tree — node dengan left dan right child, empat macam traversals, representasi node vs array, serta cara menghitung height, size, dan max-width. Trees adalah lompatan besar dari linear structures — bersiaplah!