Struktur Linear · Pelajaran 5 dari 10
Queue dan deque
9 menit baca · BelajarCode
Queue (antrean) bekerja seperti antrean loket: yang datang pertama dilayani pertama. Prinsip ini disebut FIFO (first in, first out). Operasinya enqueue (masuk di belakang) dan dequeue (keluar dari depan).
Jangan pakai list.pop(0) untuk antrean besar
list.pop(0) harus menggeser semua elemen sisanya, jadi O(n). Untuk antrean, pakai collections.deque yang menambah dan mengambil di kedua ujung dalam O(1).
1from collections import deque23antrean = deque()4antrean.append("Andi")5antrean.append("Bela")6antrean.append("Citra")7print("Dilayani:", antrean.popleft())8antrean.append("Dimas")9print("Antrean sekarang:", list(antrean))10print("Berikutnya:", antrean[0])Dilayani: Andi Antrean sekarang: ['Bela', 'Citra', 'Dimas'] Berikutnya: Bela
Simulasi loket
Tiga pelanggan datang pada menit tertentu dan butuh waktu layanan berbeda. Berapa lama setiap pelanggan menunggu jika hanya ada satu loket?
1from collections import deque23pelanggan = deque([("Andi", 0, 4), ("Bela", 1, 3), ("Citra", 2, 5), ("Dimas", 10, 2)])4waktu = 05total_tunggu = 06while pelanggan:7 nama, datang, layanan = pelanggan.popleft()8 mulai = max(waktu, datang)9 tunggu = mulai - datang10 waktu = mulai + layanan11 total_tunggu += tunggu12 print(f"{nama:<6} datang {datang:>2}, dilayani {mulai:>2}-{waktu:>2}, menunggu {tunggu}")13print("Rata-rata menunggu:", total_tunggu / 4, "menit")Andi datang 0, dilayani 0- 4, menunggu 0 Bela datang 1, dilayani 4- 7, menunggu 3 Citra datang 2, dilayani 7-12, menunggu 5 Dimas datang 10, dilayani 12-14, menunggu 2 Rata-rata menunggu: 2.5 menit
Simulasi antrean seperti ini dipakai untuk memutuskan berapa loket yang perlu dibuka di bank, rumah sakit, atau gerbang tol.
Deque: antrean dua ujung
Deque (double-ended queue) bisa ditambah dan diambil di kedua ujung. Contohnya memeriksa palindrom dengan mengambil karakter dari depan dan belakang sekaligus:
1from collections import deque23def palindrom(teks):4 huruf = deque(k.lower() for k in teks if k.isalnum())5 while len(huruf) > 1:6 if huruf.popleft() != huruf.pop():7 return False8 return True910print(palindrom("Kasur ini rusak"))11print(palindrom("Struktur data"))True False
Cek pemahaman
Struktur data apa yang tepat untuk sistem antrean tiket di stasiun?
Latihan
Antrean prioritas sederhana
Sebuah klinik punya dua antrean: darurat dan biasa. Pasien darurat selalu dilayani lebih dulu, tetapi di dalam masing-masing kelompok berlaku urutan datang. Buat program yang memproses kedatangan berikut lalu menampilkan urutan pelayanan: Andi (biasa), Bela (darurat), Citra (biasa), Dimas (darurat), Eka (biasa).
Pembahasan
1from collections import deque23darurat = deque()4biasa = deque()5for nama, jenis in [("Andi", "biasa"), ("Bela", "darurat"), ("Citra", "biasa"),6 ("Dimas", "darurat"), ("Eka", "biasa")]:7 (darurat if jenis == "darurat" else biasa).append(nama)89urutan = []10while darurat or biasa:11 urutan.append(darurat.popleft() if darurat else biasa.popleft())12print(" -> ".join(urutan))Bela -> Dimas -> Andi -> Citra -> Eka
Untuk prioritas yang lebih beragam, misalnya tingkat kedaruratan 1 sampai 5, struktur yang tepat adalah heap, dibahas di bab berikutnya.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.