Queue

 

Pengertian Queue

Queue (antrian) adalah struktur data dimana proses pengambilan dan penambahan element dilakukan pada ujung yang berbeda. cara kerja Queue adalah  mengikuti konsep FIFO (First In First Out) dimana elemen yang pertama masuk akan menjadi elemen yang pertama kali keluar

Queue dan Stack 

Karakteristik yang membedakan queue (antrian) dari stack adalah cara menyimpan dan mengambil data dengan struktur first in first out (FIFO) Hal ini berarti elemen pertama yang ditempat-kan pada queue adalah yang pertama dipindahkan.

Operasi operasi pada Queue

  1. Enqueue : Yaitu proses penambahan element pada queue element nya ini biasanya di tempatkan pada ujung (Tail)
  2. Dequeue : yaitu proses pengambilan elemen pada queue. Cara kerja nya adalah dengan emindahkan elemen dari kepala (head) sebuah queue.
Untuk penambahan di dalam Queue sendiri dilakukan pada bagian belakang. Sedangkan pengambilan dilakukan pada bagian depan (element yang pertama masuk)
 
 
Karakteristik Queue

 Queue sendiri, ini mempunyai berbagai macam karakteristik diantaranya :

  1. Elemen antrian (item-item data yang terdapat di elemen antrian)
  2. Front (Element terdepan antrian)
  3. Tail (Element terakhir
  4. Count (Jumlah element pada antrian)
  5. Status antrian
Front dan rear
  • Front : pointer bantu yang digunakan untuk menunjuk element yang paling depan.
  • Rear : pointer bantu yang digunakan untuk menunjuk element yang paling belakang

Status Antrian

  1. Penuh
  • Bila elemen pada antrian mencapai kapasitas maksimum antrian.
  • Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian.
  • Penambahan elemen menyebabkan kondisi kesalahan Overflow.
      2. Kosong 
  • Bila tidak ada elemen pada antrian
  • Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari antrian.
  • Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

Gambaran Proses Queue Antrian

 
 Deklarasi

Deklarasi struktur data mengacu pada objek permasalahan yang akan diselesaikan dengan suatu program/aplikasi. Dalam hal ini terfokus pada tata cara mewadahi data-data yang merupakan representasi permasalahan contoh dari proses nya adalah sebagai berikut :

  1. Proses yang harus dilakukan pertama kali adalah deklarasi/menyiapkan tempat.
  2. Langkah yang harus dilakukan adalah :
  • Deklarasi class 
  • Deklarasi struktur data (menggunakan array atau linked list)
  • Deklarasi pointer front dan rear
  • Deklarasi variabel size untuk menyimpan besar array.
  • Deklarasi variabel jumlah untuk mengetahui banyak item yang disimpan pada queue.
Deklarasi Queue
 
#define MAX 8
typedeft struct {
    int data[MAX];
    int head;
    int teal;
} queue;
Queue Antrian;

Inisialisasi

    Inisialisasi merupakan suatu proses pemberian nilai Awal 
Contoh  pada array :
  1. Pembentukan obyek array beserta ukurannya.
     antrian= new int[10];
     (pembentukan obyek array yang memiliki 10 element, dan alamat obyek akan disimpan pada  variabel bernama antrian)
  2. Pemberian nilai awal pada variabel front=0 dan belakang=-1.
        front = 0;
        rear=-1;
Contoh pada Linked List :
    Proses inisialisasi dilakukan dengan memberikan nilai awal pada variabel head, tail front dan rear        dengan nilai null.
    head = tail = front=rear= null; 
 

Fungsi Create 

Digunakan untuk membentuk dan menunjukan awal terbentuknya suatu Antrean / Queue
Pengecekan fungsi Kosong (Isempty)
  1. Isempty ini merupakan operasi yang digunakan untuk mengecek kondisi queue dalam keadaan kosong.
  2. Pada array : menggunakan pengecekan pada variabel jumlah_item. Jika nilainya = 0 berarti queue dalam kondisi kosong.
  3. Pada linked list : dapat menggunakan pengecekan front atau rear jika nilainya null berarti queue kosong
  4. Operasi ini harus dapat mengembalikan nilai true jika queue kosong dan false jika sebaliknya
Cek penuh (Isfull)
  1. Operasi yang hanya dapat diterapkan pada queue yang menggunakan array.
  2. Operasi ini digunakan untuk mengecek kondisi queue dalam keadaan penuh.
  3. Caranya : melihat nilai pada variabel jumlah item. Jika nilainya = size-1 (dimana size adalah ukuran array) maka dapat diindikasikan queue dalam kondisi penuh.
  4. Operasi ini harus dapat mengembalikan nilai true jika queue penuh dan false jika sebaliknya 

 Fungsi Enqueue
  1. Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu dilakukan pada     elemen paling belakang
  2.  Penambahan elemen selalu menggerakan variabel Tail dengan cara menambahkan Tail terlebih dahulu
  
 Fungsi Dequeue
  1. Digunakan untuk menghapus elemen terdepan (head)     dari Antrian
  2.  Dengan cara : menggeser semua elemen antrian     kedepan dan mengurangi Tail dgn 1. Penggeseran     dilakukan dengan menggunakan looping
Fungsi Clear
  1. Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
  2. Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula

 Jenis Jenis Queue
  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).

  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.

  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.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. 

Antrian Berprioritas

  1. Struktur data queue umumnya digunakan untuk mengelola thread dalam multithreading dan menerapkan sistem antrian prioritas pada program komputer.
  2. Dalam antrian yang telah dibahas sebelum, semua elemen yang masuk dalam antrian dianggap mempunyai prioritas yang sama, sehingga elemen yang masuk lebih dahulu akan diproses lebih dahulu.
  3. Dalam praktek, elemen-elemen yang akan masuk dalam suatu antrian ada yang dikatakan mempunyai prioritas yang lebih tinggi dibanding yang lain.
  4. Antrian yang demikian ini disebut dengan antrian berprioritas (priority queue).

 Fungsi Queue

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

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

Kelebihan Queue

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

Kekurangan Queue

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