Queue C++

Implementasi Struktur Data Queue: Konsep FIFO dalam Pemrograman

Definisi Queue (Antrian)

Queue adalah struktur data linear yang sekumpulan elemennya dikelola menggunakan prinsip FIFO (First-In-First-Out). Artinya, elemen yang pertama kali masuk akan menjadi yang pertama kali keluar.

Dalam Queue, manipulasi data dilakukan di dua ujung yang berbeda:

• Rear (Belakang): Tempat untuk menambahkan elemen baru (Enqueue).

• Front (Depan): Tempat untuk menghapus atau mengambil elemen (Dequeue).

Analogi Dunia Nyata

Konsep ini sangat umum kita temui sehari-hari:

1. Antrian Tiket Bioskop: Orang yang datang paling awal akan dilayani dan keluar dari antrian terlebih dahulu.

2. Jalan Satu Arah: Mobil yang pertama kali masuk ke jalan tersebut akan menjadi yang pertama keluar di ujung jalan.

3. Printer Queue: Dokumen yang dikirim pertama ke printer akan dicetak lebih dulu.

Operasi Utama pada Queue

Untuk memanipulasi Queue, kita menggunakan dua operasi utama:

• Enqueue: Menambahkan elemen ke posisi paling belakang (rear).

• Dequeue: Menghapus elemen dari posisi paling depan (front).

Selain itu, terdapat operasi pendukung seperti isEmpty() untuk mengecek apakah antrian kosong dan isFull() untuk mengecek apakah antrian sudah mencapai kapasitas maksimal (pada implementasi array).

1. Implementasi Queue Menggunakan Array

Implementasi ini menggunakan array statis dengan ukuran tetap (MAX). Kita perlu melacak indeks front dan rear untuk mengetahui posisi elemen.

Kode Program:

#include <iostream>
using namespace std;
#define MAX 5
class Queue {
private:
    int arr[MAX];
    int front, rear;
public:
    Queue() {
        front = -1;
        rear = -1;
    }
    bool isEmpty() {
        return (front == -1);
    }
    bool isFull() {
        return (rear == MAX - 1);
    }
    void enqueue(int x) {
        if (isFull()) {
            cout << "Queue Overflow\n";
            return;
        }
        if (isEmpty()) {
            front = 0;
        }
        arr[++rear] = x;
        cout << "Elemen " << x << " masuk ke queue\n";
    }
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow\n";
            return;
        }
        cout << "Elemen " << arr[front] << " keluar dari queue\n";
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
    }
    void display() {
        if (isEmpty()) {
            cout << "Queue kosong\n";
            return;
        }
        cout << "Isi Queue: ";
        for (int i = front; i <= rear; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};
int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();
    q.dequeue();
    q.display();
    return 0;
}

Output:

Source code:Queue menggunakan array

Pada implementasi ini, jika kita terus melakukan enqueue dan dequeue, indeks rear akan mencapai MAX-1 meskipun ada ruang kosong di depan. Inilah batasan array statis yang biasanya diatasi dengan konsep Circular Queue.

2. Implementasi Queue Menggunakan Linked List

Implementasi ini bersifat dinamis, artinya ukuran antrian bisa bertambah selama memori komputer masih tersedia. Kita tidak perlu khawatir tentang Queue Overflow.

Kode Program:

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* next;

};

class Queue {

private:

    Node *front, *rear;

public:

    Queue() {

        front = rear = NULL;

    }

    bool isEmpty() {

        return (front == NULL);

    }

    void enqueue(int x) {

        Node* newNode = new Node();

        newNode->data = x;

        newNode->next = NULL;

        if (rear == NULL) {

            front = rear = newNode;

        } else {

            rear->next = newNode;

            rear = newNode;

        }

        cout << "Elemen " << x << " masuk ke queue\n";

    }

    void dequeue() {

        if (isEmpty()) {

            cout << "Queue kosong\n";

            return;

        }

        Node* temp = front;

        cout << "Elemen " << temp->data << " keluar dari queue\n";

        front = front->next;

        if (front == NULL) {

            rear = NULL;

        }

        delete temp;

    }

    void display() {

        if (isEmpty()) {

            cout << "Queue kosong\n";

            return;

        }

        Node* temp = front;

        cout << "Isi Queue: ";

        while (temp != NULL) {

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

            temp = temp->next;

        }

        cout << endl;

    }

};

int main() {

    Queue q;

    q.enqueue(5);

    q.enqueue(15);

    q.enqueue(25);

    q.display();

    q.dequeue();

    q.display();

    return 0;

}

Output:

Source code:Queue Menggunakan Linked List

Dengan Linked List, setiap elemen baru dialokasikan secara dinamis di memori. front selalu menunjuk ke kepala list (head), dan rear menunjuk ke ekor list (tail). Ini lebih efisien untuk penggunaan memori jangka panjang dibandingkan array statis.