Struktur Data - Queues

Queue adalah struktur data yang berbentuk "antrian". Misalnya seperti antrian anjing pada gambar di atas, anjing yang paling depan akan lebih dulu "buang air" pada pohon tersebut. Jadi, yang paling depan akan keluar terlebih dahulu, atau biasa disebut FIFO(First In, First Out).

Terdapat dua fungsi utama pada queue, yaitu Enqueue & Dequeue. Enqueue menaruh elemen pada bagian belakang queue, sedangkan Dequeue mengeluarkan elemen pada bagian depan queue.

Cara mendefinisikan queue yang menyimpan string

typedef struct
{
    // menandakan dimana letak bagian depan queue
    int head;

    // string pada queue sebanyak CAPACITY=4
    char* string[CAPACITY];

    // menandakan berapa banyak string pada queue
    int size;
} queue;

// deklarasi variabel dengan tipe data queue sebagai variabel global
queue q;

Kita perlu membuat tanda bagian depan queue menggunakan variabel head, mengapa tidak string[0] saja? Jika seperti itu, berarti kita perlu menggeser elemen-elemen di belakangnya setiap kita men-dequeue dan itu hanya membuang-buang waktu.

CAPACITY adalah sebuah konstanta yang didefinisikan dengan menggunakan #define.

Ini adalah fungsi Enqueue dengan nilai kembalian berupa boolean

bool enqueue(char str[])
{
    // cek jika jumlah string pada queue sama dengan CAPACITY
    if (q.size == CAPACITY)
    {
        // enqueue gagal jika queue penuh
        return false;
    }
    // taruh string pada bagian depan queue
    q.string[(q.size + q.head) % CAPACITY] = str;

    // jumlah string pada queue bertambah jika enqueue berhasil
    q.size++;

    // enqueue berhasil
    return true;
}

Untuk Enqueue sebuah elemen pada queue, pastikan terlebih dahulu bahwa queue tidak penuh dengan membandingkan size dan CAPACITY.  Jika size == CAPACITY, maka queue penuh. Jika tidak, maka taruh elemen pada bagian depan queue, yang berarti pada indeks[(size + head) % CAPACITY].

Ini adalah fungsi Dequeue dengan nilai kembalian berupa char*

char* dequeue()
{
    // cek jika terdapat string pada queue
    if (q.size > 0)
    {
        // jika ada, simpan elemen bagian depan queue ke variabel first
        char* first = q.string[q.head];

        // elemen dibelakang first menjadi elemen bagian depan
        q.head = (q.head + 1) % CAPACITY;

        // kurangi jumlah string pada queue
        q.size--;

        // nilai kembalian berupa elemen bagian depan queue
        return first;
    }
    return NULL;
}

Untuk Dequeue sebuah elemen dari queue, pastikan bahwa ada sebuah elemen pada queue (size > 0). Jika size > 0, maka elemen bagian depan akan ter-dequeue.  Lalu kurangi variabel size sebesar 1 dan jadikan elemen yang berada di belakang elemen terdepan tadi sebagai elemen bagian depan dengan menambah variabel head sebesar 1.

Program queue.c

#include <stdio.h>
#include <stdbool.h> // agar dapat menggunakan tipe data boolean

// mendefinisikan kapasitas queue hanya memuat 4 string
#define CAPACITY 4

typedef struct
{
    // menandakan dimana letak bagian depan queue
    int head;

    // string pada queue sebanyak CAPACITY=4
    char* string[CAPACITY];

    // menandakan berapa banyak string pada queue
    int size;
} queue;

// deklarasi variabel dengan tipe data queue sebagai variabel global
queue q;

bool enqueue(char str[])
{
    // cek jika jumlah string pada queue sama dengan CAPACITY
    if (q.size == CAPACITY)
    {
        // enqueue gagal jika queue penuh
        return false;
    }
    // taruh string pada bagian depan queue
    q.string[(q.size + q.head) % CAPACITY] = str;

    // jumlah string pada queue bertambah jika enqueue berhasil
    q.size++;

    // enqueue berhasil
    return true;
}

char* dequeue()
{
    // cek jika terdapat string pada queue
    if (q.size > 0)
    {
        // jika ada, simpan elemen bagian depan queue ke variabel first
        char* first = q.string[q.head];

        // elemen dibelakang first menjadi elemen bagian depan
        q.head = (q.head + 1) % CAPACITY;

        // kurangi jumlah string pada queue
        q.size--;

        // nilai kembalian berupa elemen bagian depan queue
        return first;
    }
    return NULL;
}

int main()
{
    // inisialisasi size dan head sebesar 0
    q.size = 0;
    q.head = 0;
    char* data;
    int pilihan;
    while (true)
    {
        printf("1. Enqueue\n2. Dequeue\n3. Display Size and Head\n4. Quit\nJawab: ");
        scanf("%d", &pilihan);
        switch (pilihan)
        {
            case 1:
               printf("Insert string: ");
               scanf("%s", &data);
               printf("The enqueue %s successful\n", (enqueue(data)) ? "was" : "was not");
               break;
            case 2: dequeue(); break;
            case 3: printf("Size = %d\nHead = %d\n", q.size, q.head); break;
            default: return 0; break;
        }
    }
    return 0;
}

----------------------------------------------------------------------------------------------
Referensi: https://study.cs50.net/queues