Modul 1 [Queue]

Queue

Terminologi

• front - merupakan node terdepan pada queue.
• rear - merupakan node terbelakang pada queue.
• FIFO - first in first out.

Definisi

Queue adalah struktur data linear yang mengikuti prinsip FIFO. Pada queue, elemen pertama yang dimasukkan adalah elemen pertama yang dapat dikeluarkan. Setiap elemen pada queue selalu ditambahkan dari bagian belakang dan dikeluarkan dari bagian depan. Contoh penerapan dari queue dalam kehidupan sehari-hari adalah proses pengecekan STNK untuk keluar dari gerbang ITS :D.

Aplikasi Queue

Queue biasa digunakan pada BFS (Breadth First Search) Graph Traversal yang nantinya akan dibahas pada modul 4-5 serta penyelesaian problem generate binary number dari 1 hingga n.

Implementasi ADT Queue (Linked List Based)

Kode Lengkap Dapat Dilihat Disini

Implementasi queue dapat dilakukan dengan menggunakan Singly Linked List dengan menggunakan pointer rear untuk menunjukkan node paling belakang dan front untuk menunjukkan node terdepan.

Kompleksitas waktu semua operasi dilakukan secara konstan O(1).

• Representasi Node

  Setiap node yang ada pada queue dapat direpresentasikan oleh sebuah struct QueueNode yang menyimpan data int dan refernsi node selanjutnya menggunakan pointer struct QueueNode ini sendiri.

  typedef struct queueNode_t {
    int data;
    struct queueNode_t *next;
  } QueueNode;

• Struktur Queue

  Keseluruhan queue yang ada dikontrol oleh sebuah struct Queue yang menyimpan referensi node terdepan dan node terbelekang menggunakan pointer struct QueueNode serta data jumlah node yang ada pada queue menggunakan unsigned.

  typedef struct queue_t {
    QueueNode   *_front, *_rear;
    unsigned _size;
  } Queue;

• Fungsi isEmpty()

  Fungsi ini diguakan untuk memeriksa apakah queue kosong atau tidak. Prosesnya dilakukan dengan memeriksa apakah pointer front atau rear bernilai NULL atau tidak.

  bool queue_isEmpty(Queue *queue) {
    return (queue->_front == NULL && queue->_rear == NULL);
  }

• Fungsi queue_push()

  Fungsi ini digunakan untuk menambahkan data pada queue. Operasinya dilakukan melalui tahap sebagai berikut:

  • Buat node baru dengan struct QueueNode.
  • Jika queue kosong, jadikan node baru ini sebagai front dan rear.
  • Jika queue tidak kosong, maka next dari rear adalah node baru, dan jadikan node baru sebagai rear.

  void queue_push(Queue *queue, int value) {
    QueueNode *newNode = (QueueNode*) malloc(sizeof(QueueNode));
    if (newNode) {
      queue->_size++;
      newNode->data = value;
      newNode->next = NULL;
      
      if (queue_isEmpty(queue))                 
        queue->_front = queue->_rear = newNode;
      else {
        queue->_rear->next = newNode;
        queue->_rear = newNode;
      }
    }
  }

• Fungsi queue_pop()

  Fungsi ini digunakan untuk menghapus/mengambil node terdepan dari queue. Operasinya dilakukan dengan tahap sebagai berikut:

  • Tampung front pada variabel sementara temp.
  • Mengganti front dengan referensi next dari front.
  • Menghapus variabel sementara sebelumnya.
  • Jika front kosong, maka rear juga kosong.

  void queue_pop(Queue *queue) {
    if (!queue_isEmpty(queue)) {
      QueueNode *temp = queue->_front;
      queue->_front = queue->_front->next;
      free(temp);
      
      if (queue->_front == NULL)
        queue->_rear = NULL;
      queue->_size--;
    }
  }

• Fungsi queue_front()

  Fungsi ini digunakan untuk mengambil data terdepan dari queue. Operasinya dilakukan dengan tahap sebagai berikut:

  • Apabila queue tidak kosong, maka return data front.
  • Apabila queue kosong, maka return 0.

  int queue_front(Queue *queue) {
    if (!queue_isEmpty(queue)) {
      return (queue->_front->data);
    }
    return 0;
  }