Modul 7 Struktur Data: Queue dan berbagai implementasinya

Kembali ke Struktur Data (dengan Python)

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

Implementasi (linear) queue dengan array

class ArrayLinQueue:
    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
    
    def get_size(self):
        size = (self.rear - self.front) + 1
        return size

    def get_capacity_array(self):
        return self.array_max

    def get_capacity_queue(self):
        if self.front == -1:
            capacity_queue = self.array_max
        else:
            capacity_queue = self.array_max - self.front
        return capacity_queue
    
    def is_empty(self):
        if self.front == -1:
            return True
        else:
            return False
    
    def is_full(self):
        if self.rear == self.array_max - 1:
            return True
        else:
            return False
    
    def enqueue(self, newdata):
        if self.is_full():
            print("Error enqueue: queue sudah penuh sebelumnya")
        elif self.front == -1:
            self.front += 1
            self.rear += 1
            self.array[self.rear] = newdata
        else:
            self.rear += 1
            self.array[self.rear] = newdata
    
    def peek(self):
        if self.is_empty():
            print("Error peek: queue sedang kosong")
        else:
            return self.array[self.front]
    
    def dequeue(self):
        if self.is_empty():
            print("Error dequeue: queue sudah kosong sebelumnya")
            return None
        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
        else:
            output = self.array[self.front]
            self.front += 1
            return output
    
    def print_storage(self):
        print(self.array)

    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")

arraylinqueue = ArrayLinQueue(int, 5)

arraylinqueue.print_queue()

front : (tidak ada data) : rear

arraylinqueue.print_storage()

[                  0 4602678819172646912 4607182418800017408
 4609434218613702656 4611686018427387904]

arraylinqueue.enqueue(-18)
arraylinqueue.enqueue(67)
arraylinqueue.enqueue(32)

arraylinqueue.print_queue()

front : -18 | 67 | 32 : rear

arraylinqueue.print_storage()

[                -18                  67                  32
 4609434218613702656 4611686018427387904]

print(arraylinqueue.front)
print(arraylinqueue.rear)

0
2

arraylinqueue.enqueue(-29)

arraylinqueue.print_queue()

front : -18 | 67 | 32 | -29 : rear

arraylinqueue.print_storage()

[                -18                  67                  32
                 -29 4611686018427387904]

print(arraylinqueue.front)
print(arraylinqueue.rear)

0
3

print(arraylinqueue.peek())

-18

arraylinqueue.print_queue()

front : -18 | 67 | 32 | -29 : rear

nilai = arraylinqueue.dequeue()
print(nilai)

-18

arraylinqueue.print_queue()

front : 67 | 32 | -29 : rear

arraylinqueue.print_storage()

[                -18                  67                  32
                 -29 4611686018427387904]

print(arraylinqueue.front)
print(arraylinqueue.rear)

1
3

print(arraylinqueue.dequeue())

67

arraylinqueue.print_queue()

front : 32 | -29 : rear

print(arraylinqueue.dequeue())
print(arraylinqueue.dequeue())

32
-29

arraylinqueue.print_queue()

front : (tidak ada data) : rear

print(arraylinqueue.front)
print(arraylinqueue.rear)

-1
-1

print(arraylinqueue.dequeue())

Error dequeue: queue sudah kosong sebelumnya
None

arraylinqueue.enqueue(-25)
arraylinqueue.enqueue(13)
arraylinqueue.enqueue(48)
arraylinqueue.enqueue(-87)
arraylinqueue.enqueue(38)

arraylinqueue.print_queue()

front : -25 | 13 | 48 | -87 | 38 : rear

arraylinqueue.print_storage()

[-25  13  48 -87  38]

print(arraylinqueue.is_full())

True

print(arraylinqueue.front)
print(arraylinqueue.rear)

0
4

arraylinqueue.enqueue(-53)

Error enqueue: queue sudah penuh sebelumnya

print(arraylinqueue.dequeue())
print(arraylinqueue.dequeue())

-25
13

arraylinqueue.print_queue()

front : 48 | -87 | 38 : rear

arraylinqueue.print_storage()

[-25  13  48 -87  38]

print(arraylinqueue.front)
print(arraylinqueue.rear)

2
4

arraylinqueue.enqueue(-53)

Error enqueue: queue sudah penuh sebelumnya

Implementasi circular queue dengan array

class ArrayCircQueue:
    def __init__(self, dtype, max):
        self.dtype = dtype
        self.max = max
        self.array = np.empty(max, dtype=dtype)
        self.front = -1
        self.rear = -1
    
    def is_empty(self):
        if self.front == -1:
            return True
        else:
            return False
    
    def is_full(self):
        if self.front == (self.rear + 1) % self.max:
            return True
        else:
            return False

    def get_size(self):
        if self.is_empty():
            size = 0
        elif self.front <= self.rear:
            size = (self.rear - self.front) + 1
        else:
            size = self.max - (self.front - self.rear - 1)
        return size

    def get_capacity(self):
        return self.max
    
    def enqueue(self, newdata):
        if self.is_full():
            print("Error enqueue: queue sudah penuh sebelumnya")
        elif self.front == -1:
            self.front += 1
            self.rear += 1
            self.array[self.rear] = newdata
        else:
            self.rear = (self.rear + 1) % self.max # hanya berbeda di sini
            self.array[self.rear] = newdata
    
    # Masih sama persis
    def peek(self):
        if self.is_empty():
            print("Error peek: queue sedang kosong")
        else:
            return self.array[self.front]
    
    def dequeue(self):
        if self.is_empty():
            print("Error dequeue: queue sudah kosong sebelumnya")
            return None
        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
        else:
            output = self.array[self.front]
            self.front = (self.front + 1) % self.max # hanya berbeda di sini
            return output
    
    def print_storage(self):
        print(self.array)

    def print_queue(self):
        print("front : ", end="")
        if self.is_empty():
            print("(tidak ada data) : rear")
        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")

arraycircqueue = ArrayCircQueue(int, 5)
arraycircqueue.print_queue()

front : (tidak ada data) : rear

arraycircqueue.print_storage()

[4607182418800017408 4613374868287651840 4618441417868443648
 4622241330054037504 4625478292286210048]

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

arraycircqueue.print_queue()

front : 65 | -11 | 43 : rear

arraycircqueue.print_storage()

[                 65                 -11                  43
 4622241330054037504 4625478292286210048]

print(arraycircqueue.front)
print(arraycircqueue.rear)

0
2

arraycircqueue.enqueue(97)
arraycircqueue.enqueue(-12)

arraycircqueue.print_queue()

front : 65 | -11 | 43 | 97 | -12 : rear

arraycircqueue.enqueue(41)

Error enqueue: queue sudah penuh sebelumnya

arraycircqueue.print_storage()

[ 65 -11  43  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

0
4

print(arraycircqueue.peek())

65

arraycircqueue.print_queue()

front : 65 | -11 | 43 | 97 | -12 : rear

print(arraycircqueue.dequeue())

65

arraycircqueue.print_queue()

front : -11 | 43 | 97 | -12 : rear

arraycircqueue.print_storage()

[ 65 -11  43  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

1
4

print(arraycircqueue.dequeue())
print(arraycircqueue.dequeue())

-11
43

arraycircqueue.print_queue()

front : 97 | -12 : rear

print(arraycircqueue.front)
print(arraycircqueue.rear)

3
4

arraycircqueue.print_storage()

[ 65 -11  43  97 -12]

arraycircqueue.enqueue(-74)

arraycircqueue.print_queue()

front : 97 | -12 | -74 : rear

arraycircqueue.print_storage()

[-74 -11  43  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

3
0

arraycircqueue.enqueue(19)

arraycircqueue.print_queue()

front : 97 | -12 | -74 | 19 : rear

arraycircqueue.print_storage()

[-74  19  43  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

3
1

arraycircqueue.enqueue(85)

arraycircqueue.print_queue()

front : 97 | -12 | -74 | 19 | 85 : rear

arraycircqueue.print_storage()

[-74  19  85  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

3
2

arraycircqueue.enqueue(-31)

Error enqueue: queue sudah penuh sebelumnya

print(arraycircqueue.dequeue())

97

arraycircqueue.print_queue()

front : -12 | -74 | 19 | 85 : rear

arraycircqueue.print_storage()

[-74  19  85  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

4
2

print(arraycircqueue.dequeue())

-12

arraycircqueue.print_queue()

front : -74 | 19 | 85 : rear

arraycircqueue.print_storage()

[-74  19  85  97 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

0
2

arraycircqueue.enqueue(27)

arraycircqueue.print_queue()

front : -74 | 19 | 85 | 27 : rear

arraycircqueue.print_storage()

[-74  19  85  27 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

0
3

print(arraycircqueue.dequeue())

-74

arraycircqueue.print_queue()

front : 19 | 85 | 27 : rear

arraycircqueue.print_storage()

[-74  19  85  27 -12]

print(arraycircqueue.front)
print(arraycircqueue.rear)

1
3

Implementasi (linear) queue dengan linked list

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

class SLLinQueue:
    def __init__(self):
        # head=front, tail=rear
        self.front = None
        self.rear = None
    
    def is_empty(self):
        if self.front == None:
            return True
        else:
            return False
    
    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)
        if self.is_empty():
            self.front = newnode
            self.rear = newnode
        else:
            self.rear.next = newnode
            self.rear = newnode
    
    def peek(self):
        if self.is_empty():
            print("Error peek: queue sedang kosong")
            return None
        else:
            return self.front.data

    # hapus di awal linked list
    def dequeue(self):
        if self.is_empty():
            print("Error dequeue: queue sudah kosong sebelumnya")
            return None
        else:
            output = self.front.data
            temp = self.front
            self.front = self.front.next
            del temp
            return output
    
    def print_queue(self):
        print("front : ", end="")
        if self.is_empty():
            print("(tidak ada data) : rear")
        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")

    def print_storage(self):
        print("front -> ", end="")
        if self.is_empty():
            print("None <- rear")
        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")

sllinqueue = SLLinQueue()
sllinqueue.print_queue()
sllinqueue.print_storage()

front : (tidak ada data) : rear
front -> None <- rear

sllinqueue.enqueue(10)
sllinqueue.print_queue()
sllinqueue.print_storage()

front : 10 : rear
front -> 10 <- rear

sllinqueue.enqueue(98)
sllinqueue.print_queue()
sllinqueue.print_storage()

front : 10 | 98 : rear
front -> 10 -> 98 <- rear

sllinqueue.enqueue(-43)
sllinqueue.print_queue()
sllinqueue.print_storage()

front : 10 | 98 | -43 : rear
front -> 10 -> 98 -> -43 <- rear

print(sllinqueue.peek())

10

sllinqueue.print_queue()
sllinqueue.print_storage()

front : 10 | 98 | -43 : rear
front -> 10 -> 98 -> -43 <- rear

print(sllinqueue.dequeue())

10

sllinqueue.print_queue()
sllinqueue.print_storage()

front : 98 | -43 : rear
front -> 98 -> -43 <- rear

Implementasi circular queue dengan (circular) linked list

class SLCircQueue:
    def __init__(self):
        # head=front, tail=rear
        self.front = None
        self.rear = None
    
    def is_empty(self):
        if self.front == None:
            return True
        else:
            return False
    
    def get_size(self):
        size = 0
        temp = self.front
        if temp == None:
            return size
        else:
            size += 1
            temp = temp.next
        while (temp != self.front):
            size += 1
            temp = temp.next
        return size

    def enqueue(self, newdata):
        newnode = SLNode(newdata)
        if self.is_empty():
            self.front = newnode
            self.rear = newnode
            newnode.next = newnode
        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")

slcircqueue = SLCircQueue()
slcircqueue.print_queue()
slcircqueue.print_storage()

front : (tidak ada data) : rear
front -> None (<- rear)

slcircqueue.enqueue(-91)
slcircqueue.print_queue()
slcircqueue.print_storage()

front : -91 : rear
front -> -91 (<- rear) -> front

slcircqueue.enqueue(14)
slcircqueue.print_queue()
slcircqueue.print_storage()

front : -91 | 14 : rear
front -> -91 -> 14 (<- rear) -> front

slcircqueue.enqueue(30)
slcircqueue.print_queue()
slcircqueue.print_storage()

front : -91 | 14 | 30 : rear
front -> -91 -> 14 -> 30 (<- rear) -> front

slcircqueue.peek()

-91

slcircqueue.print_queue()
slcircqueue.print_storage()

front : -91 | 14 | 30 : rear
front -> -91 -> 14 -> 30 (<- rear) -> front

print(slcircqueue.dequeue())

-91

slcircqueue.print_queue()
slcircqueue.print_storage()

front : 14 | 30 : rear
front -> 14 -> 30 (<- rear) -> front

(TODO) Pengayaan: Deque atau double-ended queue (DEQ)