Implementasi Queue dan Deque
Bangun queue dengan deque Python, implementasikan queue melingkar, dan selesaikan maksimum sliding window menggunakan deque monotonik.
Implementasi Queue dan Deque adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Struktur Data Queue
Antrean adalah struktur data masuk-pertama, keluar-pertama (FIFO). Elemen pertama yang dimasukkan dengan enqueue adalah elemen pertama yang dikeluarkan dengan dequeue — seperti antrean pembayaran di toko. Operasi inti adalah enqueue (menambahkan ke bagian belakang) dan dequeue (menghapus dari bagian depan). Keduanya harus memerlukan O(1) agar antrean efisien.
Menggunakan list Python sebagai antrean terlihat menggoda, tetapi keliru: list.pop(0) memerlukan O(n) karena semua elemen harus bergeser. Alat yang tepat adalah collections.deque, yang menyediakan appendleft, append, popleft, dan pop dalam O(1).
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Kelas Queue Menggunakan Antrean Ujung Ganda
Bungkus deque dalam kelas Queue dengan operasi bernama agar sesuai dengan yang diharapkan pewawancara. Secara internal, enqueue memanggil append dan dequeue memanggil popleft. Operasi peek membaca queue[0] tanpa menghapusnya.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS dengan Antrean
Penerapan klasik antrean adalah Pencarian Lebar-Dahulu (BFS). Masukkan akar dengan enqueue; selama antrean tidak kosong, keluarkan sebuah simpul dengan dequeue, proses simpul tersebut, lalu masukkan tetangganya yang belum dikunjungi dengan enqueue. Karena simpul diproses tingkat demi tingkat, BFS secara alami menemukan jalur terpendek dalam graf tak berbobot. Antrean selalu memuat simpul dari paling banyak dua tingkat yang bersebelahan.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Queue Sirkular (LeetCode 622)
LeetCode 622 'Rancang Queue Sirkular': implementasikan antrean berkapasitas tetap yang berputar kembali ke awal. Gunakan larik berukuran k dan dua penunjuk: head dan tail. Masukkan elemen di ekor, keluarkan elemen di kepala, dan hitung posisi menggunakan modulo k. Variabel count membedakan kondisi penuh dan kosong (keduanya memiliki posisi awal dan akhir yang sama setelah modulo k jika tidak ada pembeda lain).
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMaksimum Jendela Geser dengan Antrean Ujung Ganda Monoton
LeetCode 239 'Maksimum Jendela Geser': untuk setiap jendela berukuran k, temukan elemen maksimum. Pendekatan coba semua kemungkinan memerlukan O(n*k). Pendekatan O(n) menggunakan antrean ujung ganda monoton menurun yang menyimpan indeks. Untuk setiap elemen baru: hapus indeks di luar jendela dari bagian depan; hapus indeks dengan nilai lebih kecil dari bagian belakang (indeks tersebut tidak mungkin menjadi maksimum pada jendela mana pun di masa mendatang). Bagian depan selalu menyimpan nilai maksimum.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Mengapa Menggunakan Queue, Bukan Hanya List, untuk Antrean?
list.pop(0) Python menghapus elemen pertama dalam O(n) karena setiap elemen yang tersisa harus bergeser satu posisi ke kiri. Untuk n penyisipan dan n penghapusan, totalnya menjadi O(n²). collections.deque adalah daftar tertaut ganda yang terdiri atas blok-blok berukuran tetap; popleft memerlukan O(1) karena hanya menyesuaikan sebuah penunjuk. Untuk BFS pada graf dengan 10^5 simpul, perbedaan antara O(n) dan O(n²) adalah perbedaan antara 100 ms dan 100 detik.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Penelusuran Tingkat demi Tingkat pada Pohon Biner (LeetCode 102)
LeetCode 102 'Penelusuran Tingkat demi Tingkat pada Pohon Biner': kembalikan semua nilai simpul tingkat demi tingkat. Gunakan antrean; pada awal setiap tingkat, catat ukuran antrean (yaitu jumlah simpul pada tingkat tersebut). Keluarkan tepat sejumlah itu simpul, kumpulkan nilainya, dan masukkan anak-anaknya ke antrean. Ulangi hingga antrean kosong.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]Antrean Prioritas dengan Modul Tumpukan
Modul heapq Python menyediakan tumpukan minimum (antrean prioritas): elemen terkecil selalu dikeluarkan terlebih dahulu. heapq.heappush(h, item) menambahkan elemen dalam O(log n), sedangkan heapq.heappop(h) menghapus elemen minimum dalam O(log n). Untuk tugas seperti algoritma Dijkstra dan masalah k-teratas, heapq menggantikan antrean sederhana.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Pola Wallpaper: Antrean untuk Tangga Kata
LeetCode 127 'Tangga Kata': temukan jumlah minimum penggantian satu karakter untuk mengubah satu kata menjadi kata lain, dengan hanya menggunakan kata-kata dalam kamus. Modelkan sebagai graf yang setiap sisinya menghubungkan kata-kata yang berbeda satu karakter. BFS pada graf ini menemukan jalur terpendek (jumlah langkah minimum) dalam O(n * L²), dengan n sebagai ukuran kamus dan L sebagai panjang kata.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5Struktur Antrean Dua Ujung
collections.deque adalah antrean dua ujung: Anda dapat menambahkan dan menghapus elemen secara efisien dari kedua ujung. Metode: appendleft dan popleft untuk bagian depan; append dan pop untuk bagian belakang. Dengan demikian, struktur ini dapat berfungsi sebagai antrean FIFO (menambahkan di belakang lalu mengeluarkan dari depan) maupun tumpukan LIFO (append lalu pop). Nilai maksimum pada jendela geser menggunakan kedua ujung: hapus indeks lama dari kiri dan hapus nilai yang lebih kecil dari kanan.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Rangkuman: Antrean vs Antrean Dua Ujung vs Tumpukan
Pilih alat yang tepat untuk masalahnya. Gunakan antrean sederhana (antrean dua ujung) untuk pemrosesan FIFO dan BFS. Gunakan antrean monoton saat Anda memerlukan nilai maksimum atau minimum pada jendela geser — struktur ini mempertahankan invarian terurut dengan menghapus elemen yang didominasi. Gunakan antrean prioritas (modul tumpukan) saat Anda memerlukan nilai minimum atau maksimum global tanpa bergantung pada urutan, misalnya dalam algoritma Dijkstra atau masalah k-teratas. Mengetahui alat mana yang harus digunakan dan alasannya adalah keterampilan penting yang diuji pewawancara.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: collections.deque menyediakan operasi memasukkan dan mengeluarkan elemen dalam O(1), sehingga menjadi implementasi antrean yang tepat di Python, BFS menggunakan antrean untuk memproses simpul tingkat demi tingkat dan menemukan jalur terpendek dalam graf tak berbobot, serta antrean dua ujung monoton menurun menyelesaikan masalah maksimum jendela geser dalam O(n) dengan menghapus indeks yang didominasi. Selanjutnya, kita akan membahas pola tumpukan monoton secara mendalam.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Implementasi Queue dan Deque” gratis?
Ya — teks lengkap “Implementasi Queue dan Deque” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Implementasi Queue dan Deque”?
Bangun queue dengan deque Python, implementasikan queue melingkar, dan selesaikan maksimum sliding window menggunakan deque monotonik. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Implementasi Queue dan Deque” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Implementasi Stack dan Penerapannya
- Implementasi Queue dan Deque
- Pola Stack Monotonik
- Simulasi Saling Menggunakan Stack dan Queue