Queue atau dalam bahasa Indonesia yang berarti antrean adalah struktur data yang menyusun elemen-elemen data dalam urutan linier. Memiliki prinsip dasar berupa FIFO (First In First Out) yang berarti elemen data yang pertama dimasukkan ke dalam antrean akan menjadi yang pertama pula untuk dikeluarkan.
A. Implementasi Queue dengan List
Dengan menggunakan metode list Python untuk menyimpan elemen Queue. Elemen baru akan ditambahkan ke bagian belakang dengan append(). Elemen akan dihapus dari bagian depan menggunakan pop().
Operasi pencarian dan penghapusan elemen di tengah antrian yang kurang efisien karena membutuhkan waktu yang lebih lama untuk mengakses elemen tersebut dibandingkan dengan array. Berikut adalah contoh kode programnya.
class QueueList:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
return None
def front (self):
return self.queue[0]
if not self.is_empty():
return self.queue[0]
return None
def rear (self):
return self.queue[-1]
if not self.is_empty():
return self.queue[-1]
return None
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
queue = QueueList()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Queue setelah enqueue: ", queue.queue)
print("Front queue: ", queue.front())
print("Rear queue: ", queue.rear())
print("Size queue: ", queue.size())
print("Dequeue: ", queue.dequeue())- Enqueue() digunakan untuk menambahkan elemen menggunakan append().
- Dequeue() digunakan untuk menghapus elemen menggunakan pop().
- Front() digunakan untuk melihat elemen pertama dalam antrean.
- Rear() digunakan untuk melihat elemen terakhir dalam antrean.
- is_empty() mengecek apakah queue kosong
- size() menghitung jumlah dan ukuran elemen dalam antrean.
B. Implementasi Queue dengan collections.deque
Collections.deque dalam Python adalah struktur data yang berfungsi sebagai double-ended queue (deque), memungkinkan penambahan dan penghapusan elemen dari kedua ujungnya dengan efisien, lebih baik daripada list untuk operasi antrian (FIFO) dan tumpukan (LIFO).
Operasi popleft() dalam deque memiliki kompleksitas O(1), sehingga tidak memerlukan pergeseran elemen seperti pada list. Berikut adalah contoh kode programnya.
from collections import deque
class QueueDeque:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
return self.queue.popleft()
if not self.is_empty():
return self.queue.popleft()
return None
def front (self):
return self.queue[0]
if not self.is_empty():
return self.queue[0]
return None
def rear (self):
return self.queue[-1]
if not self.is_empty():
return self.queue[-1]
return None
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
queue = QueueDeque()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Queue setelah enqueue: ", list(queue.queue))
print("Front queue: ", queue.front())
print("Rear queue: ", queue.rear())
print("Size queue: ", queue.size())
print("Dequeue: ", queue.dequeue())- from collections import deque digunakan untuk mengimpor deque dari modul collections.
- popleft() digunakan untuk menghapus elemen dari depan dengan kompleksitas O(1).
C. Implementasi Queue dengan queue.Queue
Metode Queue dengan queue.Queue berasal dari modul queue di Python. Modul ini digunakan untuk manajemen antrian yang aman untuk multi-threading. Seperti inilah contoh implementasinya.
from queue import Queue
queue = Queue()
queue.put(10)
queue.put(20)
queue.put(30)
print("Queue size : ", queue.qsize())
print("Dequeue : ", queue.get())
print("Queue size setelah dequeue : ", queue.qsize())- from queue import Queue digunakan untuk mengimpor kelas Queue dari modul queue.
- queue = Queue() digunakan untuk membuat objek antrian kosong.
- put() digunakan untuk menambahkan elemen ke dalam antrian.
- queue.qsize() untuk mengembalikan jumlah elemen dalam antrian.
- queue.get() untuk menghapus dan mengembalikan elemen terdepan dalam antrian.
D. Implementasi Queue dengan Linked List
Queue dengan Linked List adalah implementasi antrian yang menggunakan node yang saling terhubung, bukan array atau deque.
Linked List lebih efisien dibandingkan array jika terjadi banyak operasi enqueue dan dequeue karena tidak perlu menggeser elemen. Memungkinkan penyimpanan secara dinamis tanpa batasan ukuran tetap. Berikut adalah contoh kode programnya.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class QueueLinkedList:
def __init__(self):
self.front = self.rear = None
def enqueue(self, data):
new_node = Node(data)
if self.rear is None:
self.front = self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.front is None:
return None
dequeued_element = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return dequeued_element
def is_empty(self):
return self.front is None
def front_element(self):
return self.front.data if self.front else None
def rear_element(self):
return self.rear.data if self.rear else None
queue = QueueLinkedList()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Dequeued Element: ", queue.dequeue())
print("Front Element: ", queue.front_element())
print("Rear Element: ", queue.rear_element())Metode utama pada kode ini adalah enqueue() untuk mengambahkan elemen, dequeue() untuk menghapus elemen. Adapun front_element() dan rear_element() untuk melihat elemen pertama dan terakhir pada antrian.
Latihan dan Tugas
class QueueList:
def __init__(self, capacity=10):
self.queue = []
self.capacity = capacity
def enqueue(self, ticket_id):
if len(self.queue) >= self.capacity:
print(f"Antrian penuh! Pelanggan {ticket_id} harus menunggu.")
return
if '7' in ticket_id:
print(f"VIP Customer {ticket_id} langsung mendapatkan kursi.")
return
self.queue.append(ticket_id)
print(f"Pelanggan {ticket_id} masuk ke antrian.")
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
print("Antrian kosong!")
return None
def front(self):
if not self.is_empty():
return self.queue[0]
return None
def rear(self):
if not self.is_empty():
return self.queue[-1]
return None
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
def display(self):
print("Antrian saat ini:", self.queue)
# Contoh penggunaan
queue = QueueList()
queue.enqueue("DZ16")
queue.enqueue("DZ17") # VIP
queue.enqueue("DZ18")
queue.enqueue("DZ19")
queue.enqueue("DZ20")
queue.display()
print("Front queue:", queue.front())
print("Rear queue:", queue.rear())
print("Size queue:", queue.size())
print("Dequeue:", queue.dequeue())
queue.display()Kode di atas adalah program sederhana untuk antrian pemesanan tiket bioskop, berikut penjelasannya.
- __init__(self, capacity=10) untuk menginialisasi queue berbasis list dengan kapasitas maksimal 10.
- enqueue(self, ticket_id) untuk menambahkan elemen ke dalam antrian, dan mengecek nomor tiket yang berisi angka 7 adalah VIP.
- dequeue(self) untuk menghapus dan mengembalikan elemen pertama dari antrian.
- front(self) untuk mengembalikan elemen pertama tanpa menghapusnya, dan berisi None apabila antrian kosong.
- rear(self) untuk mengembalikan elemen terakhir tanpa menghapusnya, dan berisi None apabila antrian kosong.
- is_empty(self) untuk mengecek apakah antrian kosong.
- size(self) untuk menghitung ukuran antrian atau elemen di dalam antrian.
- display(self) untuk menampilkan isi antrian dalam bentuk list.
class QueueFotokopi:
def __init__(self):
self.queue = []
def enqueue(self, order_id, num_pages):
if num_pages < 10:
print(f"Pesanan {order_id} dengan {num_pages} halaman langsung diproses (Fast Track).")
return
if num_pages > 100:
self.queue.append((order_id, 100))
self.queue.append((order_id, num_pages - 100))
print(f"Pesanan {order_id} dengan {num_pages} halaman dipecah menjadi dua tahap.")
else:
self.queue.append((order_id, num_pages))
print(f"Pesanan {order_id} dengan {num_pages} halaman masuk ke antrian.")
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
print("Antrian kosong!")
return None
def front(self):
return self.queue[0] if not self.is_empty() else None
def rear(self):
return self.queue[-1] if not self.is_empty() else None
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
def display(self):
print("Antrian fotokopi saat ini:", self.queue)
# Contoh penggunaan
queue = QueueFotokopi()
queue.enqueue("DZA16", 5) # Fast Track
queue.enqueue("DZA17", 50) # Antri biasa
queue.enqueue("DZA18", 150) # Dipecah menjadi dua tahap
queue.enqueue("DZA19", 8) # Fast Track
queue.display()
print("Front queue:", queue.front())
print("Rear queue:", queue.rear())
print("Size queue:", queue.size())
print("Dequeue:", queue.dequeue())
queue.display()Kode di atas adalah program sederhana untuk antrian layanan fotokopi kampus, berikut penjelasannya.
- enqueue(self, order_id, num_pages) untuk menginialisasi jika halaman kurang dari 10, maka akan langsung diproses (fast track). Jika lebih dari 100 halaman, akan dipecah menjadi 2 tahap dengan 100 halaman pertama dan sisanya pesanan baru. Jika halaman diantara 10 sampai 100, akan langsung masuk ke dalam antrian.
- Fungsi sisanya berfungsi seperti pada program sebelumnya.
class QueueParkir:
def __init__(self, kapasitas=15):
self.queue = []
self.kapasitas = kapasitas
self.prioritas = []
def enqueue(self, vehicle_number, is_eco_friendly=False):
if is_eco_friendly:
self.prioritas.append(vehicle_number)
print(f"Kendaraan {vehicle_number} mendapat prioritas masuk parkiran lebih dulu.")
else:
if self.size() < self.kapasitas:
self.queue.append(vehicle_number)
print(f"Kendaraan {vehicle_number} masuk ke antrian parkir.")
else:
print(f"Parkiran penuh! Kendaraan {vehicle_number} harus menunggu.")
def dequeue(self):
if self.prioritas:
return self.prioritas.pop(0)
if not self.is_empty():
return self.queue.pop(0)
print("Tidak ada kendaraan dalam parkiran!")
return None
def front(self):
return self.prioritas[0] if self.prioritas else (self.queue[0] if not self.is_empty() else None)
def rear(self):
return self.queue[-1] if self.queue else (self.prioritas[-1] if self.prioritas else None)
def is_empty(self):
return len(self.queue) == 0 and len(self.prioritas) == 0
def size(self):
return len(self.queue) + len(self.prioritas)
def display(self):
print(f"Antrian prioritas: {self.prioritas}")
print(f"Antrian parkiran: {self.queue}")
# Contoh penggunaan
parkiran = QueueParkir()
parkiran.enqueue("MA16")
parkiran.enqueue("MA17", True)
parkiran.enqueue("MA18")
parkiran.enqueue("MA19", True)
parkiran.display()
print("Front queue:", parkiran.front())
print("Rear queue:", parkiran.rear())
print("Size queue:", parkiran.size())
print("Dequeue:", parkiran.dequeue())
parkiran.display()Kode di atas adalah program sederhana dari antrian layanan parkir mall, berikut adalah penjelasannya.
- __init__(self, kapasitas=15) untuk menginialisasi kapasitas maksimal adalah 15, sesuai dengan perintah yang diminta.
- enqueue(self, vehicle_number, is_eco_friendly=False) untuk memisahkan antara kendaraan kendaraan ramah lingkungan dan kendaraan biasa. Jika ada kendaraan ramah lingkungan, akan dimasukkan ke dalam prioritas. Jika kendaraan biasa dan parkiran belum penuh, akan dimasukkan ke dalam reguler. Jika penuh, kendaraan menunggu.
- Fungsi sisanya berfungsi seperti pada program sebelumnya.
class QueueSertifikat:
def __init__(self, kapasitas=20):
self.queue = []
self.kapasitas = kapasitas
self.jalur_prestasi = []
def enqueue(self, student_id, is_prestasi=False):
if is_prestasi:
self.jalur_prestasi.append(student_id)
print(f"Mahasiswa {student_id} langsung mengambil sertifikat (Jalur Prestasi).")
else:
if self.size() < self.kapasitas:
self.queue.append(student_id)
print(f"Mahasiswa {student_id} masuk ke antrian reguler.")
else:
print(f"Antrian penuh! Mahasiswa {student_id} harus menunggu.")
def dequeue(self):
if self.jalur_prestasi:
return self.jalur_prestasi.pop(0)
if not self.is_empty():
return self.queue.pop(0)
print("Antrian kosong!")
return None
def front(self):
return self.jalur_prestasi[0] if self.jalur_prestasi else (self.queue[0] if not self.is_empty() else None)
def rear(self):
return self.queue[-1] if self.queue else (self.jalur_prestasi[-1] if self.jalur_prestasi else None)
def is_empty(self):
return len(self.queue) == 0 and len(self.jalur_prestasi) == 0
def size(self):
return len(self.queue) + len(self.jalur_prestasi)
def display(self):
print(f"Jalur Prestasi: {self.jalur_prestasi}")
print(f"Antrian Reguler: {self.queue}")
# Contoh penggunaan
antrian = QueueSertifikat()
antrian.enqueue("TE16")
antrian.enqueue("TE17", True)
antrian.enqueue("TE18")
antrian.enqueue("AE19", True)
antrian.display()
print("Mahasiswa pertama dalam antrian:", antrian.front())
print("Mahasiswa terakhir dalam antrian:", antrian.rear())
print("Jumlah mahasiswa dalam antrian:", antrian.size())
print("Dequeue mahasiswa:", antrian.dequeue())
antrian.display()Kode di atas adalah program sederhana dari antrian pengambilan sertifikat di kampus, berikut adalah penjelasannya.
- enqueue(student_id, is_prestasi=False) untuk menginialisasi antrian mahasiswa berprestasi. Jika mahasiswa bernilai True akan langsung masuk ke dalam antrian prestasi. Jika antrian reguler penuh (20 mahasiswa) maka akan masuk ke jalur reguler terpisah.
- Fungsi sisanya berfungsi seperti pada program sebelumnya.