Struktur Data - Queue dalam Bahasa Pemrogramman C++

Nama    : Aga Nafta Filadelfiano

NRP      : 5025251055
Kelas     : Struktur Data (D) 

Queue dalam Bahasa Pemrograman C++

1. Definisi Queue 

Queue adalah jenis struktur penyimpanan data linear yang memiliki 2 jalur berbeda yaitu satu untuk masuk (rear/belakang) dan satu untuk keluar (front/depan). Karakteristik tersebut membuat queue memiliki sifat First In First Out (FIFO), artinya elemen yang pertama masuk akan pertama kali keluar. 

Beberapa operasi dasar pada queue antara lain:

Enqueue : menambahkan elemen ke bagian belakang queue (rear)

Dequeue : menghapus elemen dari bagian depan queue (front)

Syntax Program:

Output:

Penjelasan Code:

#define MAX 5

Menyimpan nilai maksimal jumlah data yang disimpan dalam queue.

class Queue  

Menyimpan fungsi-fungsi dasar.

private: int arr[MAX]; int front, rear;   

Deklarasi variabel array of integer dengan identifier arr dengan jumlah data = 5, serta variabel front dan rear yang hanya dapat diakses didalam class (private).

Queue() { front = -1;  rear = -1;}  

Deklarasi awal ketika queue baru dibuat dan kosong, maka nilai front dan rear akan di flag = -1.

bool isEmpty(){ return (front == -1); }  

Mengecek apakah queue kosong. Mengembalikan nilai true jika front == -1, yang berarti belum ada elemen di dalam queue.

bool isFull(){ return (rear == MAX -1); } 

Mengecek apakah queue sudah penuh. Mengembalikan nilai true jika rear == MAX-1 (yaitu index 4), yang berarti seluruh slot array sudah terisi.

void enqueue(int x)

Deklarasi fungsi untuk menambahkan data bertipe integer x ke bagian belakang queue.

if (isFull())  

Memanggil fungsi isFull untuk mengecek apabila masih ada ruang pada queue, jika queue penuh maka akan dicetak cout << "Queue Overflow\n";

if (isEmpty())  

Memanggil fungsi isEmpty untuk mengecek apabila queue masih kosong, jika masih kosong maka front akan diinisialisasi = 0 untuk menjadi index pertama data di queue.

arr[++rear] = x;    

Menaikkan nilai rear terlebih dahulu sebesar 1(pre increment), kemudian menyimpan nilai x ke dalam array pada posisi rear yang baru. Lalu dicetak cout << "Elemen " << x << " masuk ke queue\n";

void dequeue()

Deklarasi fungsi untuk menghapus data yang berada di bagian depan queue.

if (isEmpty())

Memanggil fungsi isEmpty untuk mengecek apabila queue masih kosong, jika masih kosong maka akan dicetak cout << "Queue Underflow\n";

cout << "Elemen " << arr[front] << " keluar dari queue\n"; 

Mencetak elemen yang akan dihapus, yaitu data pada posisi front sebelum posisi front digeser.

if (front == rear) front = rear = -1;

Mengecek apakah elemen yang akan didequeue adalah elemen terakhir (hanya tersisa 1 data). Jika front == rear, artinya queue akan kosong setelah penghapusan, sehingga keduanya direset ke -1.

else front++;

Jika masih ada elemen lain setelah penghapusan, maka front digeser maju 1 posisi ke kanan sehingga elemen berikutnya menjadi elemen terdepan baru.

void display() 

Deklarasi fungsi untuk menampilkan seluruh isi queue.

if (isEmpty())

Memanggil fungsi isEmpty untuk mengecek apabila queue masih kosong, jika masih kosong maka akan dicetak cout << "Queue kosong\n";

for (int i = front; i <= rear; i++) cout << arr[i] << " ";

Melakukan perulangan dari index front sampai rear, kemudian mencetak setiap elemen array satu per satu yang dipisahkan spasi, sehingga seluruh isi queue ditampilkan secara berurutan.

Queue q;

Membuat object dengan identifier q dari class Queue.

q.enqueue(10); q.enqueue(20); q.enqueue(30);

Memanggil fungsi enqueue yang melakukan input data secara berurutan pada queue q.

q.display();

Memanggil fungsi display dan menampilkan output

q.dequeue();

Memanggil fungsi dequeue untuk menghapus data terdepan pada queue, yaitu 10.

q.display();

Memanggil fungsi display yang menampilkan seluruh isi queue setelah front dihapus.

2. Implementasi Queue dengan Linked List

Pada implementasi ini, setiap elemen disebut sebagai Node yang menyimpan data dan alamat (pointer) ke node setelahnya. Penanda Front selalu menunjuk ke node paling depan dan Rear untuk node paling belakang dari list tersebut.

Syntax Program:

Output:

Penjelasan Code:

struct Node

Deklarasi variabel struct dengan identifier Node untuk menyimpan informasi tiap nodenya.

int data;

Deklarasi variabel integer dengan identifier data untuk menyimpan nilai data.

Node* next;

Deklarasi pointer dengan identifier next yang berfungsi menyimpan alamat memori dari node berikutnya (node di bawahnya).

class Queue {

Deklarasi class dengan identifier Queue untuk menyimpan fungsi-fungsi dasar.

private: Node *front, *rear;

Deklarasi pointer front dan rear yang hanya bisa diakses di dalam class untuk menandai elemen terdepan(front) dan terakhir(rear) dalam queue.

Queue() { front = rear = NULL; }

Deklarasi awal ketika queue baru dibuat dan kosong, maka nilai front dan rear = NULL.

bool isEmpty() return (front == NULL);

Fungsi bertipe boolean untuk mengecek apakah queue kosong. Mengembalikan nilai true jika front ++ NULL, yang berarti tidak ada node di dalam queue.

void enqueue(int x)

Deklarasi fungsi untuk menambahkan data bertipe integer x ke bagian belakang queue.

Node* newNode = new Node();

Perintah untuk mengalokasikan memori baru secara dinamis untuk membuat node baru.

newNode->data = x;

Mengisi variabel data pada node baru dengan nilai dari variabel x

newNode->next = NULL;

Mengisi pointer next pada node baru dengan nilai NULL, karena node baru ini akan menjadi elemen paling belakang sehingga tidak menunjuk ke node manapun.

if (rear == NULL) front = rear = newNode;

Mengecek apakah queue masih kosong. Jika rear == NULL, berarti node baru adalah satu-satunya elemen, sehingga front dan rear langsung menunjuk ke node baru tersebut.

else {

    rear->next = newNode;

    rear = newNode;}

Jika queue sudah berisi elemen, maka pointer next dari node rear yang lama diarahkan ke node baru, kemudian rear diperbarui untuk menunjuk ke node baru tersebut sebagai elemen paling belakang yang baru.

void dequeue()

Deklarasi fungsi untuk menghapus data yang berada di bagian depan queue.

Node* temp = front;

Menyimpan alamat node front saat ini ke variabel sementara temp, agar node tersebut bisa dihapus dari memori setelah front digeser.

front = front->next;

Menggeser pointer front ke node berikutnya, sehingga elemen kedua menjadi elemen terdepan baru setelah elemen pertama dihapus.

if (front == NULL) rear = NULL;

Mengecek apakah setelah penghapusan queue menjadi kosong. Jika front == NULL, berarti tidak ada elemen tersisa, sehingga rear direset NUL.

delete temp;

Menghapus node lama yang disimpan di variabel temp.

void display()

Deklarasi fungsi untuk menampilkan seluruh isi queue.

Node* temp = front;

Membuat pointer sementara temp yang menunjuk ke front, digunakan sebagai pointer traversal untuk menelusuri node satu per satu tanpa mengubah posisi front yang asli.

while (temp != NULL) {

    cout << temp->data << " ";

    temp = temp->next;}

Melakukan perulangan selama temp tidak NULL. Setiap iterasi mencetak data dari node yang sedang ditunjuk, lalu temp digeser ke node berikutnya melalui pointer next.

Source Code: GitHub