Modul 6 Struktur Data: Queue

Queue

Offline di Departemen Matematika

Published

November 15, 2024

Di praktikum kali ini, kita akan membahas tentang struktur data queue serta berbagai “implementasi”nya dalam Python (yaitu berbagai cara membuat struktur data queue di Python), baik menggunakan array maupun linked list.

Queue itu sendiri adalah suatu struktur data dengan dua ujung, di mana data bisa dimasukkan dari salah satu ujung tertentu (yang disebut rear) dan data bisa dikeluarkan dari ujung yang satunya lagi (yang disebut front). Queue dikatakan menganut prinsip FIFO (First In First Out), karena data yang pertama masuk akan menjadi data yang pertama keluar.

Kita akan menggunakan array dari numpy, sehingga perlu melakukan import:

import numpy as np

Queue Linear

Implementasi Queue dengan Array

class ArrayLinQueue:
    # definisikan queue dengan array
    def __init__(self, dtype, array_max):
        self.dtype = dtype
        self.array_max = array_max
        self.array = np.empty(array_max, dtype = dtype)
        self.front = -1
        self.rear = -1

    # mengetahui banyaknya elemen pada queue
    def get_size(self):
        # kasus saat queue kosong
        if self.is_empty():
            return 0

        # kasus queue tidak kosong
        else:
            size = (self.rear - self.front) + 1
            return size

    # mengetahui kapasitas sesungguhnya dari queue
    def get_capacity_array(self):
        return self.array_max

    # mengetahui kapasitas yang tersisa dari queue
    def get_capacity_queue(self):
        # kasus saat queue belum digunakan
        if self.front == -1:
            capacity_queue = self.array_max

        # kasus saat queue sudah digunakan
        else:
            capacity_queue = self.array_max - self.rear - 1 #perlu debugging ketika sudah full
        return capacity_queue

    # cek apakah queue kosong
    def is_empty(self):
        if self.front == -1:
            return True
        else:
            return False

    # cek apakah queue sudah penuh
    def is_full(self):
        if self.rear == self.array_max - 1:
            return True
        else:
            return False

    # metode enqueue
    def enqueue(self, newdata):
        # Kondisi ketika array penuh
        if self.is_full():
            print("Error enqueue: queue sudah memenuhi batas maksimum")

        # Kasus ketika queue masih kosong di awal
        elif self.front == -1:
            self.front += 1
            self.rear += 1
            self.array[self.rear] = newdata

        # kasus ketika queue sudah tidak kosong di awal
        else:
            self.rear += 1
            self.array[self.rear] = newdata

    # mengintip isi dari queue di awal
    def peek(self):
        if self.is_empty():
            print("Error peek: queue sedang kosong")
        else:
            return self.array[self.front]

    # metode dequeue
    def dequeue(self):
        # kasus saat queue kosong
        if self.is_empty():
            print("Error dequeue: queue sudah kosong sebelumnya")
            return None

        # kasus hanya satu elemen pada queue
        elif (self.get_size() == 1):
            # Jika di queue hanya ada satu elemen, dan ingin di-dequeue,
            # maka queue akan kosong setelah itu
            # kita reset queue kita jadi kosong
            output = self.array[self.front]
            self.front = -1
            self.rear = -1
            return output

        # kasus umum pada queue
        else:
            output = self.array[self.front]
            self.front += 1
            return output

    # mencetak semua elemen pada queue
    def print_storage(self):
        print(self.array)

    def display(self):
        return self.array

    # mencetak queue *versi lain
    def print_queue(self):
        print("front : ", end="")
        if self.is_empty():
            print("(tidak ada data) : rear")
        else:
            for i in range(self.front, self.rear): # i = front, ..., rear-1
                print(self.array[i], end=" | ")
            print(self.array[self.rear], end="") # untuk i = rear
            print(" : rear")

Contoh penggunaan Queue dengan Array

queueLinArray = ArrayLinQueue(dtype = int, array_max=10)

queueLinArray.get_capacity_array()

queueLinArray.print_queue()

front : (tidak ada data) : rear

queueLinArray.enqueue(1)
queueLinArray.print_queue()

front : 1 : rear

for i in range(3):
    queueLinArray.enqueue(i*5)

queueLinArray.print_queue()

front : 1 | 0 | 5 | 10 : rear

queueLinArray.print_storage()

[                  1                   0                   5
                  10 7599578574504329216 3761739758475294518
 3617566120052078381 3256163233075901495 4050536193999398197
 8026364514949935924]

print(f"Banyaknya elemen pada queue: {queueLinArray.get_size()}")
print(f"Kapasitas yang tersedia: {queueLinArray.get_capacity_queue()}")

Banyaknya elemen pada queue: 4
Kapasitas yang tersedia: 6

queueLinArray.dequeue()

print(f"Banyaknya elemen pada queue: {queueLinArray.get_size()}")
print(f"Kapasitas yang tersedia: {queueLinArray.get_capacity_queue()}")
queueLinArray.print_queue()

Banyaknya elemen pada queue: 3
Kapasitas yang tersedia: 6
front : 0 | 5 | 10 : rear

for i in range(queueLinArray.get_size()):
    queueLinArray.dequeue()

queueLinArray.dequeue()

Error dequeue: queue sudah kosong sebelumnya

Implementasi Queue dengan Linked List

# definisikan node dari suatu linked list
class SLNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class SLLinQueue:
    # definisikan queue dengan linked list
    def __init__(self):
        # head=front, tail=rear
        self.front = None
        self.rear = None

    # cek apakah queue kosong
    def is_empty(self):
        if self.front == None:
            return True
        else:
            return False

    # mengetahui banyaknya elemen pada queue
    def get_size(self):
        size = 0
        temp = self.front
        while (temp != None):
            size += 1
            temp = temp.next
        return size

    # insert di akhir linked list
    def enqueue(self, newdata):
        newnode = SLNode(newdata)

        # kasus saat queue kosong
        if self.is_empty():
            self.front = newnode
            self.rear = newnode

        # kasus saat queue tidak kosong
        else:
            self.rear.next = newnode
            self.rear = newnode

    # mengintip isi dari queue di awal
    def peek(self):

        # kasus saat queue kosong
        if self.is_empty():
            print("Error peek: queue sedang kosong")
            return None

        # kasus saat queue tidak kosong
        else:
            return self.front.data

    # hapus di awal linked list
    def dequeue(self):

        # kasus saat queue kosong
        if self.is_empty():
            print("Error dequeue: queue sudah kosong")
            return None

        # kasus saat queue tidak kosong
        else:
            output = self.front.data
            temp = self.front
            self.front = self.front.next
            del temp # hapus node yang tidak penting
            return output

    # cetak queue yang dimiliki
    def print_queue(self):
        print("front : ", end="")

        # kasus saat queue kosong
        if self.is_empty():
            print("(tidak ada data) : rear")

        # kasus queue tidak kosong
        else:
            temp = self.front
            while temp != None:
                if temp.next != None:
                    print(temp.data, end = " | ")
                else:
                    print(temp.data, end="")
                temp = temp.next
            print(" : rear")

    # cetak queue yang dimiliki *versi lain
    def print_storage(self):
        print("front -> ", end="")

        # kasus saat queue kosong
        if self.is_empty():
            print("None <- rear")

        # kasus queue tidak kosong
        else:
            temp = self.front
            while temp != None:
                if temp.next != None:
                    print(temp.data, end = " -> ")
                else:
                    print(temp.data, end = " <- ")
                temp = temp.next
            print("rear")

Contoh Penggunaan Queue dengan Linked List

queueLinLinked = SLLinQueue()

queueLinLinked.print_queue()

front : (tidak ada data) : rear

queueLinLinked.enqueue(1)
queueLinLinked.print_queue()

front : 1 : rear

for i in range(3):
    queueLinLinked.enqueue(i*5)

queueLinLinked.print_queue()

front : 1 | 0 | 5 | 10 : rear

queueLinLinked.print_storage()

front -> 1 -> 0 -> 5 -> 10 <- rear

queueLinLinked.get_size()

queueLinLinked.dequeue()

queueLinLinked.print_storage()

front -> 0 -> 5 -> 10 <- rear

for i in range(queueLinLinked.get_size()):
    queueLinLinked.dequeue()

queueLinLinked.print_storage()

front -> None <- rear

queueLinLinked.dequeue()

Error dequeue: queue sudah kosong

Circular Queue

Masalah utama dalam linear queue dengan array adalah saat melakukan enqueue dan dequeue, kedua pointer hanya akan berjalan ke kanan. Artinya ketika pointer depan telah sampai ke indeks terakhir di array, program akan menganggap queue telah penuh, meskipun elemen di indeks awal array sudah di dequeue.

Untuk mengatasi hal ini, kita dapat membuat pointer depan kembali ke awal jika pointer tersebut telah melewati indeks terakhir dari array dan lanjut mengisi queue mulai dari indeks pertama hingga pointer depan bertemu dengan pointer belakang. Implementasi queue seperti ini disebut circular queue.

Implementasi Circular Queue dengan Array

# mulai dari sini, untuk memudahkan circular queue
# akan disebut sebagai queue saja

class ArrayCircQueue:
    # definisikan queue dengan array
    def __init__(self, dtype, max):
        self.dtype = dtype
        self.max = max
        self.array = np.empty(max, dtype=dtype)
        self.front = -1
        self.rear = -1

    # cek apakah queue kosong
    def is_empty(self):
        if self.front == -1:
            return True
        else:
            return False

    # cek apakah queue penuh
    def is_full(self):
        # kasus saat rear modulo max sama dengan front
        # dapat dibayangkan sebagai rear tepat di belakang front
        # pada diagram array lingkaran
        if self.front == (self.rear + 1) % self.max:
            return True
        else:
            return False

    # mengetahui banyaknya elemen pada queue
    def get_size(self):
        # kasus saat kosong
        if self.is_empty():
            size = 0

        # kasus front di belakang rear
        elif self.front <= self.rear:
            size = (self.rear - self.front) + 1

        # kasus rear di belakang front
        else:
            size = self.max - (self.front - self.rear - 1)

        return size

    # mengetahui kapasitas queue
    def get_capacity(self):
        return self.max

    # metode enqueue
    def enqueue(self, newdata):

        # kasus queue penuh
        if self.is_full():
            print("Error enqueue: queue sudah penuh sebelumnya")

        # kasus queue kosong
        elif self.front == -1:
            self.front += 1
            self.rear += 1
            self.array[self.rear] = newdata

        # kasus ketika queue sudah tidak kosong
        else:
            self.rear = (self.rear + 1) % self.max # hanya berbeda di sini
            self.array[self.rear] = newdata

    # mengintip isi dari queue di awal
    def peek(self):
        if self.is_empty():
            print("Error peek: queue sedang kosong")
        else:
            return self.array[self.front]

    # mnetode dequeue
    def dequeue(self):

        # kasus ketika queue kosong
        if self.is_empty():
            print("Error dequeue: queue sudah kosong sebelumnya")
            return None

        # kasus hanya satu elemen pada queue
        elif (self.get_size() == 1):
            # Jika di queue hanya ada satu elemen, dan ingin di-dequeue,
            # maka queue akan kosong setelah itu
            output = self.array[self.front]
            self.front = -1
            self.rear = -1
            return output

        # kasus umum pada queue
        else:
            output = self.array[self.front]
            self.front = (self.front + 1) % self.max # hanya berbeda di sini
            return output

    # mencetak semua elemen pada queue
    def print_storage(self):
        print(self.array)

    # mencetak semua elemen pada queue *versi lain
    def print_queue(self):
        print("front : ", end="")

        # kasus saat queue kosong
        if self.is_empty():
            print("(tidak ada data) : rear")

        # kasus saat queue tidak kosong
        else:
            # i = front, ..., rear-1 (kurang lebih begitu)
            i = self.front
            while i != self.rear:
                print(self.array[i], end=" | ")
                i = (i + 1) % self.max
            # untuk i = rear
            print(self.array[self.rear], end="")
            print(" : rear")

queueCircArray = ArrayCircQueue(dtype = int, max = 9)

queueCircArray.print_queue()

front : (tidak ada data) : rear

queueCircArray.print_storage()

[102469711431981               0               0               0
               0               0               0               0
               0]

queueCircArray.enqueue(65)
queueCircArray.enqueue(-11)
queueCircArray.enqueue(43)

queueCircArray.print_storage()

[ 65 -11  43   0   0   0   0   0   0]

queueCircArray.print_queue()

front : 65 | -11 | 43 : rear

print(queueCircArray.front)
print(queueCircArray.rear)

0
2

for i in range(6):
    queueCircArray.enqueue(i*4 + 1)

queueCircArray.print_storage()

[ 65 -11  43   1   5   9  13  17  21]

queueCircArray.enqueue(41)

Error enqueue: queue sudah penuh sebelumnya

queueCircArray.dequeue()

queueCircArray.print_storage()
queueCircArray.print_queue()

[ 65 -11  43   1   5   9  13  17  21]
front : -11 | 43 | 1 | 5 | 9 | 13 | 17 | 21 : rear

queueCircArray.enqueue(9)

queueCircArray.print_storage()
queueCircArray.print_queue()

[  9 -11  43   1   5   9  13  17  21]
front : -11 | 43 | 1 | 5 | 9 | 13 | 17 | 21 | 9 : rear

print(queueCircArray.front)
print(queueCircArray.rear)

1
0

for i in range(3):
    queueCircArray.dequeue()

queueCircArray.print_storage()
queueCircArray.print_queue()

[  9 -11  43   1   5   9  13  17  21]
front : 5 | 9 | 13 | 17 | 21 | 9 : rear

print(queueCircArray.front)
print(queueCircArray.rear)

4
0

Implementasi Circular Queue dengan Linked List

class SLNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class SLCircQueue:

    # definisikan queue dengan linked list
    def __init__(self):
        # head=front, tail=rear
        self.front = None
        self.rear = None

    # cek apakah queue kosong
    def is_empty(self):
        if self.front == None:
            return True
        else:
            return False

    # mengetahui banyaknya elemen pada queue
    def get_size(self):
        size = 0
        temp = self.front

        # kasus saat queue kosong
        if temp == None:
            return size

        # kasus linked list tidak kosong
        else:
            size += 1
            temp = temp.next
        while (temp != self.front):
            size += 1
            temp = temp.next
        # alasan pemisahan adalah sebagai penanda kapan traversal
        # perlu dihentikan

        return size

    # metode enqueue
    def enqueue(self, newdata):
        newnode = SLNode(newdata)

        # kasus saat queue kosong
        if self.is_empty():
            self.front = newnode
            self.rear = newnode
            newnode.next = newnode

        # kasus queue tidak kosong
        else:
            self.rear.next = newnode
            self.rear = newnode
            newnode.next = self.front

    # masih sama persis
    def peek(self):
        if self.is_empty():
            print("Error peek: queue sedang kosong")
            return None
        else:
            return self.front.data

    def dequeue(self):
        if self.is_empty():
            print("Error dequeue: queue sudah kosong sebelumnya")
            return None
        elif (self.front == self.rear): # sama saja self.get_size() == 1
            output = self.front.data
            del self.front
            self.front = None
            self.rear = None
            return output
        else:
            output = self.front.data
            temp = self.front
            self.front = self.front.next
            del temp
            self.rear.next = self.front
            return output

    def print_queue(self):
        print("front : ", end="")
        if self.is_empty():
            print("(tidak ada data) : rear")
        else:
            temp = self.front
            while temp.next != self.front:
                print(temp.data, end = " | ")
                temp = temp.next
            print(temp.data, end="")
            print(" : rear")

    def print_storage(self):
        print("front -> ", end="")
        if self.is_empty():
            print("None (<- rear)")
        else:
            temp = self.front
            while temp.next != self.front:
                print(temp.data, end = " -> ")
                temp = temp.next
            print(temp.data, end = "")
            print(" (<- rear) -> front")

queueDLinked = SLCircQueue()

queueDLinked.print_queue()

front : (tidak ada data) : rear

queueDLinked.print_storage()

front -> None (<- rear)

queueDLinked.enqueue(65)
queueDLinked.enqueue(-11)
queueDLinked.enqueue(43)

queueDLinked.print_queue()
queueDLinked.print_storage()

front : 65 | -11 | 43 : rear
front -> 65 -> -11 -> 43 (<- rear) -> front

queueDLinked.is_empty()

False

queueDLinked.dequeue()

queueDLinked.print_queue()
queueDLinked.print_storage()

front : -11 | 43 : rear
front -> -11 -> 43 (<- rear) -> front

queueDLinked.peek()

-11

for i in range(queueDLinked.get_size()):
    queueDLinked.dequeue()

queueDLinked.is_empty()

True

Membuat User Interface untuk Struktur Data Queue

Perkenalan Jupyter Widgets

Menggunakan program bagi orang yang mengerti pastilah mudah untuk melihat apa maksud dari tampilan pada sebuah file notebook. Namun, pada satu sisi ketika anda ingin menampilkan hasil pekerjaan anda pada rekan atau kolega, teman, atau bahkan dosen tidak harus anda menampilkan tampilan yang lumayan sulit untuk dipahami.

Oleh karena itu anda bisa mnenggunakan Jupyter Widgets untuk menampilkan pekerjaan anda menjadi lebih mudah untuk dilihat.

Apa itu Jupyter Widgets?

Jupyter widgets, atau ipywidgets, adalah komponen UI (User Interface) interaktif dalam notebook Jupyter yang memungkinkan interaksi pengguna dengan kode, data, dan visualisasi. Widget ini dibangun di atas framework Jupyter dan memungkinkan Anda membuat kontrol interaktif seperti slider, tombol, dropdown, dan kotak teks yang bisa dihubungkan langsung dengan kode Python secara real-time.

Manfaat Jupyter widget:

Interaktivitas: Widget memungkinkan pengguna untuk menyesuaikan parameter, melihat perubahan, dan memanipulasi data secara dinamis tanpa harus menjalankan ulang sel secara manual.
Eksplorasi Data: Slider, tombol, dan widget lainnya memudahkan eksplorasi data secara interaktif, seperti mengatur parameter visualisasi.
Output Langsung: Widget menampilkan output yang berubah berdasarkan input pengguna, sehingga cocok untuk membuat dashboard, aplikasi, atau laporan interaktif dalam notebook.

Install widgets dengan menggunakan kode berikut:

Dengan pip:

pip install ipywidgets

Dengan conda:

conda install -c conda-forge ipywidgets

import ipywidgets as widgets

Widgets merupakan sebuah objek, ingat kembali pada praktikum OOP bahwa kita bisa import object tersebut dari sebuah package. Penggunaan metode pada package akan sama dengan metode biasanya.

Misal kita ingin buat slider bilangan bulat, maka kita bisa membuatnya dengan cara berikut.

widgets.IntSlider()

Atau dengan cara yang lebih mudah yaitu kita ambil saja objeknya sebagai berikut.

from ipywidgets import IntSlider
from IPython.display import display

slider = IntSlider()

display(slider)

display(slider)

Perhatikan bahwa jika kita memanggil slider pada dua cell berbeda, kedua slider bergerak secara bersamaan. Hal ini karena objek pada cell adalah objek yang sama dengan yang kita definisikan sebelumnya. Oleh karena itu, untuk menutupnya dapat digunakan metode close() berikut.

# tutup semua slider dengan variabel "slider"
slider.close()

Selain membuat slider, kita juga dapat membuat tombol atau text box dengan menggunakan Button, ToggleButton, Text, FloatText, IntText

from ipywidgets import Button, ToggleButton, Text, IntText, FloatText, Label

tombol = Button(
    description = "Klik Aku",
    disabled = False,
    button_style='', # 'success', 'info', 'warning', 'danger' or ''
    tooltip='Pastikan anda yakin',
    icon='clipboard' # (FontAwesome names without the `fa-` prefix)
)
display(tombol)

def hasil_click(b):
  print("Aku telah di klik")

tombol.on_click(hasil_click)

Aku telah di klik
Aku telah di klik

toggle = ToggleButton(
    value=False,
    description="Click me",
    disabled=False,
    button_style='', # 'success', 'info', 'warning', 'danger' or ''
    tooltip='Description',
    icon='check' # (FontAwesome names without the `fa-` prefix)
)


display(toggle)

text_box = Text(
    value= '',
    placeholder='Masukkan Input',
    description='String:',
    disabled=False
)

display(text_box)

text_box_angka = FloatText(
    value= 0,
    description='Number:',
    disabled=False
)
display(text_box_angka)

Sekarang mari kita implementasikan widgets sebelumnya dengan membuat interface untuk memasukkan dan mengeluarkan nilai dari queue menggunakan tombol dan text box.

from ipywidgets import IntText, Button, Label
from IPython.display import display

# Mendefinisikan Queue yang digunakan dengan array circular queue
size = 5
queue = ArrayCircQueue(dtype = int, max = size)

# Membuat text box untuk enqueue nilai baru
enqueue_input = IntText(description='Enqueue: ')

# Membuat tombol untuk enqueue dan dequeue
enqueue_button = Button(description="Enqueue")
dequeue_button = Button(description="Dequeue")

# Menampilkan semua elemen pada Queue
queue_display = Label(value=str(queue.print_queue()))

# Membuat fungsi untuk melakukan enqueue
def enqueue_handler(b):
    value = enqueue_input.value
    result = queue.enqueue(value)
    queue_display.value = str(queue.print_queue())

# Membuat fungsi untuk melakukan dequeue
def dequeue_handler(b):
    result = queue.dequeue()
    queue_display.value = f"Dequeued: {result} | {queue.print_queue()}"

# Ketika tombol diklik, maka fungsi sebelumnya akan dijalankan
enqueue_button.on_click(enqueue_handler)
dequeue_button.on_click(dequeue_handler)

# Menampilkan UI
display(enqueue_input, enqueue_button, dequeue_button, queue_display)

front : (tidak ada data) : rear

front : 1 : rear
front : 1 | 2 : rear
front : 1 | 2 | 3 : rear
front : 1 | 2 | 3 | 4 : rear
front : 1 | 2 | 3 | 4 | 5 : rear
Error enqueue: queue sudah penuh sebelumnya
front : 1 | 2 | 3 | 4 | 5 : rear
front : 2 | 3 | 4 | 5 : rear
front : 3 | 4 | 5 : rear
front : 4 | 5 : rear
front : 5 : rear
front : (tidak ada data) : rear
Error dequeue: queue sudah kosong sebelumnya
front : (tidak ada data) : rear

Atau jika kalian ingin melihat bagaimana cara circular queue bekerja pada array, kalian bisa menampilkan array keseluruhan yang digunakan dengan print_storage().

# Mendefinisikan Queue yang digunakan dengan array circular queue
size = 5
queue = ArrayCircQueue(dtype = int, max = size)

# Membuat text box untuk enqueue nilai baru
enqueue_input = IntText(value=0, description='Enqueue: ')

# Membuat tombol untuk enqueue dan dequeue
enqueue_button = Button(description="Enqueue")
dequeue_button = Button(description="Dequeue")

# Menampilkan semua elemen pada Queue
queue_display = Label(value=str(queue.print_storage()))

# Membuat fungsi untuk melakukan enqueue
def enqueue_handler(b):
    value = enqueue_input.value
    result = queue.enqueue(value)
    queue_display.value = str(queue.print_storage())

# Membuat fungsi untuk melakukan dequeue
def dequeue_handler(b):
    result = queue.dequeue()
    queue_display.value = f"Dequeued: {result} | {queue.print_storage()}"

# Ketika tombol diklik, maka fungsi sebelumnya akan dijalankan
enqueue_button.on_click(enqueue_handler)
dequeue_button.on_click(dequeue_handler)

# Menampilkan UI
display(enqueue_input, enqueue_button, dequeue_button, queue_display)

[            0 2523989131520 2523989133760 2523989131840             0]

[            1 2523989131520 2523989133760 2523989131840             0]
[            1             2 2523989133760 2523989131840             0]
[            1             2             3 2523989131840             0]
[1 2 3 4 0]
[1 2 3 4 5]
Error enqueue: queue sudah penuh sebelumnya
[1 2 3 4 5]
[1 2 3 4 5]
[1 2 3 4 5]
[7 2 3 4 5]
[7 7 3 4 5]
Error enqueue: queue sudah penuh sebelumnya
[7 7 3 4 5]
[7 7 3 4 5]
[7 7 3 4 5]
[7 7 3 4 5]
[7 7 3 4 5]
[7 7 3 4 5]
Error dequeue: queue sudah kosong sebelumnya
[7 7 3 4 5]