1. Definisi Queue

Queue merupakan salah satu abstract data type. Seperti yang telah dibahas sebelumnya bahwa ADT atau abstract data type adalah pendefinisian tipe data dan operasi yang dapat dilakukan oleh tipe data tersebut. Artinya kita dapat membuat sebuah tipe data yang operasinya dapat kita sesuaikan dengan kebutuhan kita.

Contoh dalam kasus Queue yang merupakan sebuah data type yang memiliki sifat seperti antrian sehingga disebut dengan Queue. Dengan menggunakan queue maka data akan disusun secara linear berbaris. Perbedaannya dengan ADT linear serupa seperti stack adalah pada queue data memiliki sifat FIFO (First In First Out) yang artinya data yang pertama kali diinput akan pertama kali juga dikeluarkan yang mana hal tersebut kebalikan dari Stack.

Pada Queue kita dapat melakukan operasi:

1. Enqueue, menambahkan element baru pada akhir antrian
2. Dequeue, menghapus element pertama pada antrian (queue)
3. Peek/Front, melihat element pertama pada antrian (queue)
4. IsEmpty, memeriksa apakah queue kosong atau tidak
5. Size, melihat panjang dari queue saat itu

2. Implementasi Queue

Sebenarnya pada python kita dapat menggunakan banyak cara untuk mendefinisikan queue seperti menggunakan library queue yang tinggal digunakan dengan cara mengimportnya. Namun, pada pertemuan kali ini kita akan mencoba mendefinisikan queue dengan menggunakan class - object dalam bentuk list dan mencoba mendefinisikan setiap operasinya dalam bentuk method pada class yang didefinisikan. Untuk lebih jelasnya perhatikan kode berikut:

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def size(self):
        return len(self.items)
    
    def Peek(self):
        return self.items[0]

Kode di atas adalah struktur class dari Queue yang terdiri dari queue yang terbuat dari list dan operasi operasi yang akan dimiliki oleh class tersebut dalam bentuk method-methodnya. Mari kita beda satu satu:

1. Pendefinisian Queue

def __init__(self):
        self.items = []

Pertama kode di atas adalah untuk mendefinisikan object dari class queue yang akan memiliki atribute bernama items berbentuk list.

2. IsEmpty Operation

def is_empty(self):
        return self.items == []

Kode di atas adalah operasi untuk mengecek apakah queue tersebut sedang kosong atau tidak dengan mengecek apakah items saat ini == [] atau list kosong yang akan mengembalikan nilai true jika queue memang benar kosong.

3. Enqueue Operation

def enqueue(self, item):
        self.items.append(item)

Kode di atas adalah operasi enqueue yang akan menambahkan nilai/element baru pada list.

4. Dequeue Operation

def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

Kode di atas akan melakukan operasi dequeue atau mengeluarkan nilai paling awal, untuk itu dilakukan pop(0) atau pop pada element indeks 0 jika queue tidak kosong.

5. Size Operation

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

Kode di atas digunakan untuk mengecek berapa jumlah data yang sudah tersimpan dalam queue dengan cara mengecek len dari list. Operasi size ini dapat dikembangkan untuk membuat operasi IsFull jika kita ingin membatasi panjang dari Queue sehingga jika Queue sudah penuh maka operasi Enqueue tidak dapat dilakukan lagi.

6. Peek Operation

def Peek(self):
        return self.items[0]

Operasi peek atau front yaitu operasi untuk melihat nilai apa yang berada di posisi terdepan dari queue. Hal tersebut dapat dilakukan dengan mengembalikan nilai pada indeks 0 list.

Adapun untuk menggunakan class di atas dapat digunakan kode di bawah ini:

q = Queue()
print(q.is_empty())  # output: True

q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
print(q.Peek()) # output:a
print(q.size())  # output: 3

print(q.dequeue())  # output: a
print(q.dequeue())  # output: b
print(q.dequeue())  # output: c
print(q.dequeue())  # output: None

print(q.is_empty())  # output: True

Output:

True
a
3
a
b
c
None
True

2.1 Implementasi Queue dengan Class

Adapun kita dapat menerapkan implementasi class untuk membuat queue. Dengan menggunakan class maka sifat dari queue akan terasa, karena kita tidak dapat melakukan pengaksesan data berdasarkan indeksnya seperti list sehingga sifat dari FIFO pada setiap operasinya lebih terasa.

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

    def Enqueue(self, data):
        new_node = Queue()
        new_node.data = data
        new_node.next = None
        if (self.data == None):
            self.data = new_node.data
            self.next = None
        else:
            current_node = self
            while (current_node.next != None):
                current_node = current_node.next
            current_node.next = new_node

    def Dequeue(self):
        if (self == None):
            pass
        else:
            data_keluar = self.data
            self.data = self.next.data
            self.next = self.next.next
            return data_keluar

    def Tampil(self):
        start = self
        while (start.next != None):
            print(start.data, end=' ')
            start = start.next
        print(start.data)

    def Peek(self):
        return self.data

    def IsEmpty(self):
        return self.next == None


new_queue = Queue()
print("Is Empty?", new_queue.IsEmpty())
new_queue.Enqueue(1)
new_queue.Enqueue(2)
new_queue.Enqueue(3)
new_queue.Tampil()
print("Dequeue :", new_queue.Dequeue())
new_queue.Enqueue(4)
new_queue.Enqueue(10)
new_queue.Tampil()
print("Peek :", new_queue.Peek())
print("Is Empty?", new_queue.IsEmpty())

Output:

Is Empty? True
1 2 3
Dequeue : 1
2 3 4 10
Peek : 2
Is Empty? False