Queue Dalam Python. Struktur Data #4

Photo by Hal Gatewood on Unsplash

Pada praktikum kali ini saya akan menjelaskan apa itu Queue Dalam Python. Nama saya Gilang Fastya Wijaya, mahasiswa Teknologi Informasi. Di sini, saya akan menjelaskan konsep queue pada bahasa pemrograman python.

DASAR TEORI

Queue adalah struktur data yang mengikuti prinsip FIFO First In, First Out. Berbeda dengan Stack yang pakai LIFO (yang terakhir masuk justru pertama keluar, seperti tumpukan buku). Queue lebih adil, elemen masuk dari satu ujung (rear) dan keluar dari ujung lainnya (front).

Queue mempunyai 4 operasi dasar, semua operasinya efisien dengan waktu O(1) :
1. Enqueue (Tambah elemen baru di bagian belakang antrian)
2. Dequeue (Hapus elemen paling depan)
3. Front (Intip elemen paling depan tanpa menghapusnya)
4. Rear (Intip elemen paling belakang tanpa menghapusnya)

IMPLEMENTASI

Ada 4 cara implementasi Queue di python, dari yang paling simpel sampai paling manual :

1. Menggunakan List

Pakai append() untuk enqueue dan pop(0) untuk dequeue. Tapi pop(0) punya kompleksitas O(n) karena semua elemen harus digeser dan cocok hanya untuk data kecil atau latihan.

# python program to demonstrate queue implementation using list
queue = []

# append() function to enqueue element in the queue
queue.append('a')
queue.append('i')
queue.append('u')
queue.append('e')
queue.append('o')

print('Initial queue')
print(queue)

# pop() function to dequeue element form queue in FIFO order
print('\nElements dequeued from queue :')
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print('\nQueue after removing elements')
print(queue)

# uncomenting print(queue.pop()) will cause an IndexError as the queue is noe empty

Output :

2. Menggunakan collections.deque

Deque dioptimasi untuk operasi di kedua ujun, baik append() maupun popleft() sama-sama O(1). Ini pilihan yang paling direkomendasikan untuk Queue di Python.

# python program to demonstrate queue implementation using collections.deque
from collections import deque

queue = deque()

# append() function to enqueue element in the queue
queue.append('a')
queue.append('i')
queue.append('u')
queue.append('e')
queue.append('o')

print('Initial queue')
print(queue)

# popLeft() function to dequeue element form stack in LIFO order
print('\nElements dequeued from queue :')
print(queue.popleft())
print(queue.popleft())
print(queue.popleft())

print('\nQueue after removing elements')
print(queue)

# uncomenting print(queue.pop()) will cause an IndexError as the queue is noe empty

Output :

3. Menggunakan queue.Queue

Modul bawaan Python dengan fitur paling lengkap. Bisa set batas kapasitas lewat maxsize, cek kondisi penuh/kosong, dan aman dipakai di aplikasi multithreading.

# python program to demonstrate queue implementation using queue module
from queue import Queue

# Initializing a queue
qu = Queue(maxsize=5)

# qsize() show the number of elements in the queue
print(qu.qsize())

# put() function to enqueue element in the queue
qu.put('a')
qu.put('i')
qu.put('u')
qu.put('e')
qu.put('o')

print("Full : ", qu.full())
print("Size : ", qu.qsize())

# get() function to dequeue element form queue
print("\nElements dequeue from the queue")
print(qu.get())
print(qu.get())
print(qu.get())

print("\nEmpty : ", qu.empty())
print("Full : ", qu.full())

Output :

4. Menggunakan Single Linked List

Get Gilang Fastya Wijaya’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Ini cara manual, bikin class Queue sendiri dari nol. Paling bagus buat benar-benar ngerti cara kerjanya di balik layar, tanpa bergantung modul bawaan Python.

class Queue:
  def __init__(self):
    self.queue = list()

  def addtoqu(self,dataval):
    # insert method to add element
    if dataval not in self.queue:
      self.queue.insert(0,dataval)
      return True
    return false

  # pop method to remove element
  def removefromq(self):
    if len(self.queue)>0:
      return self.queue.pop()
    return ("No elements in Queue!")

  def size(self):
    return len(self.queue)

TheQueue = Queue()
print(TheQueue.addtoqu("Jan"))
print(TheQueue.addtoqu("Feb"))
print(TheQueue.addtoqu("March"))
print(TheQueue.addtoqu("April"))
print(TheQueue.size())
print(TheQueue.removefromq())
print(TheQueue.removefromq())
print(TheQueue.size())

Output :

KESIMPULAN

Queue itu sederhana, elemen masuk dari belakang, keluar dari depan adalah prinsip FIFO yang adil dan konsisten. Untuk keperluan umum, pakai collections.deque. Kalau butuh fitur kontrol kapasitas atau thread-safe, pakai queue.Queue. Dan kalau lagi belajar dari dasar, implementasi manual dengan Linked List adalah yang paling bikin paham.

TUGAS

Rangkumlah tentang algoritma pencarian dan pengurutan dalam python !

Algoritma pencarian (searching) dipakai untuk menemukan elemen tertentu dari sekumpulan data. Sedangkan algoritma pengurutan (sorting) dipakai untuk menyusun elemen-elemen tersebut sesuai urutan tertentu, bisa dari kecil ke besar, atau sebaliknya.

Algoritma Pencarian

1.Linear search
Cek elemen satu per satu dari awal sampai ketemu. Simpel, cocok untuk data sembarang yang belum terurut. Kelemahannya, makin banyak data makin lama.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i      # ketemu, kembalikan index
    return -1            # tidak ditemukan

data = [5, 3, 8, 1, 9]
print(linear_search(data, 8)) # > 2
print(linear_search(data, 7)) # > -1

2.Binary Search
Cari dari tengah, kalau target lebih kecil cari di kiri, lebih besar cari di kanan. Setiap langkah membuang setengah data. Jauh lebih cepat, tapi data harus sudah terurut.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if   arr[mid] == target: return mid
        elif arr[mid] < target:  low  = mid + 1
        else:                    high = mid - 1
    return -1

data = [1, 3, 5, 7, 9, 11]  # harus terurut!
print(binary_search(data, 7)) # > 3
print(binary_search(data, 6)) # > -1

ALGORITMA PENGURUTAN

1.Bubble Sort
Bandingkan dua elemen bersebelahan, kalau urutannya salah ditukar. Diulang sampai semua benar. Paling gampang dipahami tapi lambat untuk data besar.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([64, 34, 25, 12, 22]))

2.Selection Sort
Cari elemen terkecil dari yang belum terurut, taruh di depan. Ulangi terus. Jumlah pertukaran lebih sedikit dibanding Bubble Sort.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]: min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([29, 10, 14, 37, 13]))

3.Insertion Sort
Ambil satu elemen, sisipkan ke posisi yang tepat di bagian yang sudah terurut. Mirip cara ngurutin kartu di tangan. Bagus untuk data kecil atau yang hampir terurut.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]; j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]; j -= 1
        arr[j+1] = key
    return arr

print(insertion_sort([12, 11, 13, 5, 6]))

KESIMPULAN

Binary Search kalau datanya sudah terurut jauh lebih cepat. Kalau belum terurut, pakai Linear Search. Untuk pengurutan di dunia nyata cukup pakai sorted() bawaan Python. Bubble, Selection, dan Insertion Sort berguna untuk belajar konsep, bukan untuk data besar.

REFERENSI

Suamanda Ika Novichasari, M.Kom. (2024). Queue dalam Python. Modul 4 Praktikum Struktur Data. Universitas Tidar.

GITHUB

StrukturData/Pertemuan 4 at main · gilangfastya/StrukturData