Struktur Data Queue: Pengertian, Jenis, dan Kegunaannya

Dalam ilmu komputer, data adalah informasi dan struktur data adalah cara untuk menyimpan informasi tersebut sehingga hubungan antara nilai dan operasi apa pun yang diterapkan pada data dapat dipertahankan.

Queue merupakan salah satu struktur data dasar yang digunakan dalam aplikasi pemrograman dan cukup penting untuk dipelajari. 

Pada artikel ini, kita akan belajar tentang berbagai jenis struktur data queue, operasi dasar, implementasi, kelebihan serta kekurangannya.

Simak, ya!

Daftar Isi

Pengertian Queue

Queue adalah struktur data linier yang menerapkan prinsip operasi dimana elemen data yang masuk pertama akan keluar lebih dulu. Prinsip ini dikenal dengan istilah FIFO (First In, First Out).

Berbeda dengan struktur data stack yang menyimpan data secara bertumpuk dimana hanya terdapat satu ujung yang terbuka untuk melakukan operasi data, struktur data queue justru disusun secara horizontal dan terbuka di kedua ujungnya. Ujung pertama (head) digunakan untuk menghapus data sedangkan ujung lainnya (tail) digunakan untuk menyisipkan data.

Persamaan antara stack dan queue adalah keduanya dapat diimplementasikan menggunakan struktur data linked list atau array.

Contoh nyata dalam kehidupan sehari-hari yang dapat menggambarkan struktur data queue adalah barisan orang yang menunggu untuk membeli tiket di gedung bioskop.

Orang yang baru datang akan bergabung dengan barisan dari ujung dan orang yang berdiri di depan akan menjadi yang pertama mendapatkan tiket dan meninggalkan barisan. Demikian pula dalam struktur data queue, data yang ditambahkan terlebih dahulu akan meninggalkan antrian terlebih dahulu.

Berikut ini adalah ilustrasi dari queue

Pada gambar di atas, karena elemen 1 ditambahkan ke antrian lebih dulu daripada 2, maka 1 adalah elemen yang pertama dihapus dari antrian. Hal ini mengikuti aturan operasi FIFO.

Dalam istilah pemrograman, menempatkan item dalam struktur data queue disebut enqueue, sedangkan operasi menghapus item dari queue disebut dequeue.

Kita dapat mengimplementasikan queue dalam bahasa pemrograman apa pun seperti C, C++, Java, Python atau C#, dengan spesifikasi yang hampir sama.

Berikut adalah implementasi queue dengan bahasa pemrograman C++

// Queue implementation in C++

#include <iostream>
#define SIZE 5

using namespace std;

class Queue {
   private:
  int items[SIZE], front, rear;

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

  bool isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    return false;
  }

  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  void enQueue(int element) {
    if (isFull()) {
      cout << "Queue is full";
    } else {
      if (front == -1) front = 0;
      rear++;
      items[rear] = element;
      cout << endl
         << "Inserted " << element << endl;
    }
  }

  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "Queue is empty" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* Q has only one element, so we reset the queue after deleting it. */
      else {
        front++;
      }
      cout << endl
         << "Deleted -> " << element << endl;
      return (element);
    }
  }

  void display() {
    /* Function to display elements of Queue */
    int i;
    if (isEmpty()) {
      cout << endl
         << "Empty Queue" << endl;
    } else {
      cout << endl
         << "Front index-> " << front;
      cout << endl
         << "Items -> ";
      for (i = front; i <= rear; i++)
        cout << items[i] << "  ";
      cout << endl
         << "Rear index-> " << rear << endl;
    }
  }
};

int main() {
  Queue q;

  //deQueue is not possible on empty queue
  q.deQueue();

  //enQueue 5 elements
  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // 6th element can't be added to because the queue is full
  q.enQueue(6);

  q.display();

  //deQueue removes element entered first i.e. 1
  q.deQueue();

  //Now we have just 4 elements
  q.display();

  return 0;
}

Struktur data queue umumnya digunakan untuk mengelola thread dalam multithreading dan menerapkan sistem antrian prioritas pada program komputer.

Jenis-jenis Queue

Secara umum ada 4 jenis struktur data queue, meliputi

• Simple Queue
• Circular Queue
• Priority Queue
• Double-Ended Queue (Dequeue)

1. Simple Queue

Simple queue adalah struktur data queue paling dasar di mana penyisipan item dilakukan di simpul belakang (rear atau tail) dan penghapusan terjadi di simpul depan (front atau head).

Sumber: naukri.com

2. Circular Queue

Pada circular queue, simpul terakhir terhubung ke simpul pertama. Queue jenis ini juga dikenal sebagai Ring Buffer karena semua ujungnya terhubung ke ujung yang lain. Penyisipan terjadi di akhir antrian dan penghapusan di depan antrian.

Sumber: naukri.com

3. Priority Queue

Priority Queue adalah strruktur data queue dimana simpul akan memiliki beberapa prioritas yang telah ditentukan. Simpul dengan prioritas terbesar akan menjadi yang pertama dihapus dari antrian. Sedangkan penyisipan item terjadi sesuai urutan kedatangannya. 

Sumber: naukri.com

Aplikasi priority queue antara lain algoritma jalur terpendek Dijkstra, algoritma prim, dan teknik kompresi data seperti kode Huffman.

4. Double-Ended Queue (Dequeue)

Dalam double-ended queue (dequeue), operasi penyisipan dan penghapusan dapat terjadi di ujung depan dan belakang dari queue.

Sumber: programiz.com

Karakteristik Queue

Queue memiliki berbagai karakteristik sebagai berikut:

• Queue adalah struktur FIFO (First In First Out).
• Untuk menghapus elemen terakhir dari Queue, semua elemen yang dimasukkan sebelum elemen tersebut harus dihilangkan atau dihapus.
• Queue adalah daftar berurutan dari elemen-elemen dengan tipe data yang serupa.

Operasi-operasi Dasar pada Queue

Queue adalah struktur data abstrak (ADT) yang memungkinkan operasi berikut:

• Enqueue: Menambahkan elemen ke akhir antrian
• Dequeue: Menghapus elemen dari depan antrian
• IsEmpty: Memeriksa apakah antrian kosong
• IsFull: Memeriksa apakah antrian sudah penuh
• Peek: Mendapatkan nilai bagian depan antrian tanpa menghapusnya
• Initialize: Membuat antrian baru tanpa elemen data (kosong)

Namun, secara umum antrian memiliki 2 operasi utama, yaitu enqueue dan dequeue.

Operasi Enqueue

Di bawah ini adalah langkah-langkah untuk enqueue (memasukkan) data ke dalam antrian

• Periksa apakah antrian sudah penuh atau tidak.
• Jika antrian penuh – cetak kesalahan overflow dan keluar dari program.
• Jika antrian tidak penuh – naikkan pointer belakang untuk menunjuk ke ruang kosong berikutnya.
• Tambahkan elemen pada posisi yang ditunjuk oleh pointer belakang.
• Kembalikan status bahwa penambahan telah berhasil

Pseucode untuk operasi enqueue

procedure enqueue (data)
 

if queue is full

return overflow

endif

rear ← rear + 1

queue[rear] ← data

return true

end procedure

Operasi Dequeue

Di bawah ini adalah langkah-langkah untuk melakukan operasi dequeue

• Periksa apakah antrian sudah penuh atau tidak.
• Jika antrian kosong – cetak kesalahan underflow dan keluar dari program.
• Jika antrian tidak kosong – akses elemen data yang ditunjuk oleh pointer depan.
• Geser pointer depan untuk menunjuk ke elemen data berikutnya yang tersedia.
• Kembalikan status bahwa operasi penghapusan telah berhasil

Pseucode untuk operasi dequeue

procedure dequeue
 

if queue is empty

return underflow

end if

data = queue[front]

front ← front + 1

return true

end procedure

Fungsi dan Kegunaan Queue

Berikut ini adalah beberapa fungsi queue yang paling umum dalam struktur data:

• Queue banyak digunakan untuk menangani lalu lintas (traffic) situs web.
• Membantu untuk mempertahankan playlist yang ada pada aplikasi media player
• Queue digunakan dalam sistem operasi untuk menangani interupsi.
• Membantu dalam melayani permintaan pada satu sumber daya bersama, seperti printer, penjadwalan tugas CPU, dll.
• Digunakan dalam transfer data asinkronus misal pipeline, IO file, dan socket.

Kelebihan Queue

Kelebihan queue di antarnya:

• Data dalam jumlah besar dapat dikelola secara efisien.
• Operasi seperti penyisipan dan penghapusan dapat dilakukan dengan mudah karena mengikuti aturan masuk pertama keluar pertama.
• Queue berguna ketika layanan tertentu digunakan oleh banyak konsumen.
• Queue cepat untuk komunikasi antar-proses data.
• Queue dapat digunakan dalam implementasi struktur data lainnya.

Kekurangan Queue

Kelemahan struktur data queue adalah sebagai berikut:

• Operasi seperti penyisipan dan penghapusan elemen dari tengah cenderung banyak memakan waktu.
• Dalam queue konvensional, elemen baru hanya dapat dimasukkan ketika elemen yang ada dihapus dari antrian.
• Mencari elemen data pada struktur queue membutuhkan time complexity O(N).
• Ukuran maksimum antrian harus ditentukan sebelumnya.

Penutup

Demikianlah penjelasan lengkap mengenai struktur data queue. Semoga bermanfaat.

Apabila Anda suka dengan artikel seperti ini, Anda bisa mengunjungi rubrik Data Structure atau membaca artikel lainnya mengenai "Struktur Data Stack".

Salam!

Referensi:

• https://www.programiz.com/dsa/queue
• https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-queue
• https://www.geeksforgeeks.org/what-is-data-structure-types-classifications-and-applications/#queue

Trivusi Ikatlah ilmu dengan menulis. Menebar manfaat dengan berbagi :)

Berbagi :