Belajar Data Structure - Stack & Queue
Stack (LIFO) dan Queue (FIFO) adalah dua prinsip akses yang membentuk banyak algoritma. Di episode ini kalian memahami array-backed vs linked-list-backed, operasi push/pop/enqueue/dequeue, serta mempraktikkan valid parentheses checker dan BFS traversal grid sederhana.
#Pendahuluan
Setelah di episode 5 kita memahami linked list — singly, doubly, dan circular — pada episode ini kita mempelajari dua struktur data linear paling penting: stack (LIFO: Last In, First Out) dan queue (FIFO: First In, First Out). Keduanya bukan sekadar abstraksi teori — mereka adalah fondasi dari banyak algoritma dan sistem nyata.
Stack dan queue bisa diimplementasikan dengan array maupun linked list, dan masing-masing memiliki trade-off. Memahami kapan harus menggunakan mana — dan mengapa — adalah keterampilan yang akan kalian pakai dalam coding interview dan production code.
#Stack (LIFO)
#Konsep Dasar
Stack seperti tumpukan piring: piring terakhir yang diletakkan (top) adalah yang pertama diambil. Operasi utamanya:
- Push: tambahkan elemen ke atas stack
- Pop: hapus elemen dari atas stack
- Peep/Top: lihat elemen paling atas tanpa menghapus
- IsEmpty: cek apakah stack kosong
#Array-Backed Stack
class ArrayStack:
def __init__(self):
self.items = []
def push(self, value):
self.items.append(value)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)#Linked-List-Backed Stack
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedStack:
def __init__(self):
self.top = None
self._size = 0
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
self._size += 1
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
value = self.top.value
self.top = self.top.next
self._size -= 1
return value
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.top.value
def is_empty(self):
return self.top is None#Perbandingan Implementasi
| Aspek | Array-Backed | Linked-List-Backed |
|---|---|---|
| Push | Amortized O(1) | O(1) |
| Pop | O(1) | O(1) |
| Memori | Lebih efisien (cache-friendly) | Lebih boros (pointer overhead) |
| Implementasi | Lebih sederhana | Lebih verbose |
#Aplikasi Stack
- Undo/redo: editor teks, graphic editor
- Expression evaluation: konversi infix ke postfix, evaluasi postfix
- DFS: traversal graph/tekyanan menggunakan stack
- Function call: call stack di runtime bahasa pemrograman
#Queue (FIFO)
#Konsep Dasar
Queue seperti antrian di kasir: orang pertama yang antri (front) adalah yang pertama dilayani. Operasi utamanya:
- Enqueue: tambahkan elemen ke belakang queue
- Dequeue: hapus elemen dari depan queue
- Front: lihat elemen paling depan tanpa menghapus
- IsEmpty: cek apakah queue kosong
#Circular Buffer Queue
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.items = [None] * capacity
self.front = 0
self.rear = -1
self._size = 0
def enqueue(self, value):
if self.is_full():
raise IndexError("Queue is full")
self.rear = (self.rear + 1) % self.capacity
self.items[self.rear] = value
self._size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
value = self.items[self.front]
self.front = (self.front + 1) % self.capacity
self._size -= 1
return value
def front_value(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items[self.front]
def is_empty(self):
return self._size == 0
def is_full(self):
return self._size == self.capacity#Deque (Double-Ended Queue)
Deque memungkinkan insert dan delete di kedua ujung — gabungan stack dan queue. Bisa diimplementasikan dengan doubly linked list atau circular buffer.
#Monotonic Stack
Monotonic stack adalah stack yang elemen-elemennya selalu dalam urutan tertentu (monotonically increasing atau decreasing). Berguna untuk menyelesaikan masalah seperti "next greater element" dan "daily temperatures".
#Praktik: Valid Parentheses
Masalah klasik yang diselesaikan dengan stack:
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0Alur eksekusi untuk "({[]})":
(→ push ke stack:['(']{→ push:['(', '{'][→ push:['(', '{', '[']]→ cocok dengan[, pop:['(', '{']}→ cocok dengan{, pop:['('])→ cocok dengan(, pop:[]- Stack kosong → valid!
#Praktik: BFS Grid Sederhana
from collections import deque
def bfs_grid(grid, start, end):
rows, cols = len(grid), len(grid[0])
queue = deque([(start[0], start[1], 0)])
visited = {(start[0], start[1])}
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c, dist = queue.popleft()
if (r, c) == end:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == 0
and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
grid = [
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
[1, 1, 0, 0]
]
print(bfs_grid(grid, (0, 0), (3, 3)))Tip
BFS menggunakan queue untuk mengeksplorasi semua tetangga pada level yang sama sebelum pindah ke level berikutnya. Ini menjamin shortest path pada graph unweighted — kalian akan belajar lebih dalam tentang BFS dan DFS di episode 16.
#Penutup
Inti yang harus dibawa pulang:
- Stack (LIFO): push/pop/peek di satu ujung; array-backed atau linked-list-backed.
- Queue (FIFO): enqueue/dequeue; circular buffer atau linked list.
- Deque: double-ended queue — insert/delete di kedua ujung.
- Stack digunakan untuk: undo, expression evaluation, DFS.
- Queue digunakan untuk: BFS, job scheduler, scheduling.
- Praktik: valid parentheses (stack) dan BFS grid (queue).
Di episode 7 selanjutnya kita akan membahas hash table (hash map) — struktur data yang memungkinkan lookup rata-rata O(1) dengan hash function, collision handling via chaining dan open addressing, serta kapan harus menggunakannya. Pastikan kalian sudah paham stack karena hash table akan menyelesaikan masalah yang sebelumnya diselesaikan oleh stack!