Struktur Data - Queue

Queue adalah struktur data linear yang menggunakan prinsip FIFO (First In First Out). Data yang pertama kali masuk akan keluar pertama kali. Rear (belakang) merupakan sebutan untuk letak elemen yang baru dimasukkan, sementara Front (depan) merupakan sebutan untuk letak elemen yang dihapus.

Contoh sederhana queue dalam kehidupan nyata yaitu antrian tiket di loket bioskop. Pengunjung yang pertama kali mengantre adalah yang pertama dilayani oleh petugas.

1. Operasi Utama dan Algoritma Queue

Operasi utama untuk queue terbagi menjadi dua, yaitu Enqueue (tambah data) dan Dequeue (hapus data).

A. Enqueue (tambah data)

ALGORITHM Enqueue (Q, item)
INPUT     : Q (queue), item (elemen yang akan dimasukkan)
OUTPUT    : Queue Q yang telah ditambahkan elemen baru

BEGIN
    IF rear = MAX - 1 THEN
        OUTPUT "Queue Overflow"
        RETURN
    ENDIF

    IF front = -1 THEN
        front ← 0
        rear ← 0
    ELSE
        rear ← rear + 1
    ENDIF

    Q[rear] ← item

END

Penjelasan variabel:

- Q : Array sebagai tempat penyimpan queue

- MAX : Kapasitas maksimum queue

- Front : Penunjuk elemen depan

- Rear : Penunjuk elemen belakang

- Item : Data yang akan dimasukkan

B. Dequeue (hapus data)

ALGORITHM Dequeue (Q)
INPUT    : Q (queue)
OUTPUT   : Elemen yang dihapus dari queue

BEGIN
    IF front = -1 THEN
        OUTPUT "Queue Underflow"
        RETURN
    ENDIF

    item ← Q[front]

    IF front = rear THEN
        front ← -1
        rear  ← -1
    ELSE
        front ← front + 1
    ENDIF

    RETURN item

END

2. Implementasi dengan Array di C++

Output:

3. Implementasi dengan Linked List di C++

Output: