Queue dengan Linked List

Oke temen temen semua, jika sebelumnya kita sudah membahas Queue dengan Array, kali ini kita akan menggunakan Linked List untuk membuat antrian. Bagi yang belum tau apa itu Queue? Queue atau antrian merupakan struktur data yang berisi kumpulan data dimana Queue ini bersifat FIFO (First In First Out) yaitu data yang pertama masuk akan menjadi yang pertama keluar. Untuk lebih detailnya sudah kita bahas sebelumnya disini. Sekarang kita fokus ke implementasinya.

Penggunaan Linked List pada Queue ini sama saja dengan menggunakan Linked List pada umumnya. Hanya saja kita lebih fokus ke sifat dari Queue tersebut, yaitu FIFO (First In First Out). Jadi sangat disarankan bagi kamu yang belum memahami mengenai Linked List untuk dapat memahaminya terlebih dahulu.

Operasi Dequeue

Operasi dequeue pada Queue yang menerapkan linked list akan menghapus node yang berada di bagian awal linked list yaitu node front/head. Kemudian node front pun akan digantikan dengan node setelahnya dan node akan digeser.

Seperti pada ilustrasi di samping, terdapat proses dequeue yaitu dengan mengeluarkan node bernilai 9. Pengeluarkan ini akan memutuskan pointer pada node 9 yang menunjuk ke node selanjutnya. Kemudian, node setelah node front akan menjadi node front yang baru.

Operasi Enqueue

Operasi enqueue pada Queue yang menerapkan linked list akan menambahkan node baru dibagian akhir linked list, jadi node baru tersebut akan menjadi tail/rear pada linked list. Seperti pada ilustrasi di atas, dimana terdapat queue dengan linked list dan sedang terjadi enqueue yaitu penambahan node dengan nilai 15. Karena penambahan di akhir maka node yang ditambahkan harus menunjuk ke null, kemudian node rear dengan nilai 7 akan ditunjuk ke node yang baru yaitu node 15.

Penerapan dalam C++

Source Code

#include <iostream>
using namespace std;

// node using struct
struct antrian{
    string nama;
    int umur;

    antrian *next;
}; 
antrian *head, *tail, *newNode, *cur, *del;

// prototipe fungsi
int countAntrian();
bool isEmpty();
void enqueue(string nama, int umur);
void dequeue();
void display();
void clear();

/*
 * Main Function
 */
int main(){

    enqueue("Kang Mikirin Kode", 23);
    display();

    enqueue("Ezio", 29);
    enqueue("Hayabusa", 35);
    enqueue("Sarah Kerrigan", 26);
    enqueue("Yuki", 20);
    enqueue("Arthas Menethil", 40);
    display();

    dequeue();
    dequeue();
    display();
 
    clear();
    display();

    cout << "Jumlah antrian: " << countAntrian() << endl;
    return 0;
}

/*
 * Operasi Linked List
 */

// penambahan data antrian
void enqueue(string nama, int umur){
    if(isEmpty()){
        head = new antrian();
        head->nama = nama;
        head->umur = umur;
        head->next = NULL;
        tail = head;
        cout << "berhasil menambahkan elemen baru" << endl;
    } else{
        newNode = new antrian();
        newNode->nama = nama;
        newNode->umur = umur;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        cout << "berhasil menambahkan elemen baru" << endl;
    }
}


// pengeluaran data antrian
void dequeue(){
    if(isEmpty()){
        cout << "Antrian kosong" << endl;
    } else{
        del = head;
        head = head->next;
        del->next = NULL;
        delete del; 
        cout << "berhasil mengeluarkan elemen pertama" << endl;
    }
}

// fungsi untuk menghitung jumlah node (elemen) pada queue
int countAntrian(){
    if(head == NULL){
        return 0;
    } else{
        int counter = 0;
        cur = head;
        while(cur != NULL){
            counter++;
            cur = cur->next;
        }
        return counter;
    }
}

// fungsi untuk mengecek bahwa antrian kosong atau tidak
bool isEmpty(){
    if(countAntrian() == 0){
        return true;
    } else{
        return false;
    }
}


// fungsi untuk mencetak nilai pada antrian
void display(){
    cout << "Data Antrian:" << endl;
    if(isEmpty()){
        cout << "Antrian kosong" << endl;
    } else{
        cout << "Jumlah data: " << countAntrian() << endl;
        cur = head;
        int nomor = 0;
        while(cur != NULL){
            cout << nomor+1 << ". " << cur->nama << " - " << cur->umur << " tahun." << endl;
            cur = cur->next;
            nomor++;
        }
    }
    cout << endl;
}

// fungsi untuk menghapus seluruh data pada antrian
void clear(){
    if(isEmpty()){
        cout << "Antrian Kosong" << endl;
    } else {
        head->next = NULL;
        head = NULL;
        cout << "menghapus seluruh data pada Queue" << endl;
        
        cur = head;
        while(cur != NULL){
            del = cur;
            cur = cur->next;
            
            // menghapus node
            del->next = NULL;
            delete del;
        }
        head = NULL;
    }
}

Output

berhasil menambahkan elemen baru
Data Antrian:
Jumlah data: 1
1. Kang Mikirin Kode - 23 tahun.

berhasil menambahkan elemen baru
berhasil menambahkan elemen baru
berhasil menambahkan elemen baru
berhasil menambahkan elemen baru
berhasil menambahkan elemen baru
Data Antrian:
Jumlah data: 6
1. Kang Mikirin Kode - 23 tahun.
2. Ezio - 29 tahun.
3. Hayabusa - 35 tahun.
4. Sarah Kerrigan - 26 tahun.
5. Yuki - 17 tahun.
6. Arthas Menethil - 40 tahun.

berhasil mengeluarkan elemen pertama
berhasil mengeluarkan elemen pertama
Data Antrian:
Jumlah data: 4
1. Hayabusa - 35 tahun.
2. Sarah Kerrigan - 26 tahun.
3. Yuki - 17 tahun.
4. Arthas Menethil - 40 tahun.

menghapus seluruh data pada Queue
Data Antrian:
Antrian kosong

Jumlah antrian: 0

Kesimpulan

Queue dengan menggunakan Linked List pada dasarnya sama dengan menggunakan Linked List pada umumnya. Hanya saja lebih menekankan pada sifat FIFO dari Queue tersebut. Oke teman teman kita sudah mengimplementasikan Linked List pada Queue. Terima kasih Sudah membaca.

Keep ngoding and have a nice day