Pengertian Queue Dalam C++

Queue jika diartikan secara harfiah, queue berarti antrian, Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Pada Stack atau tumpukan menggunakan prinsip “Masuk terakhir keluar pertama”atau LIFO (Last In First Out), Maka pada Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out). Data-data di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

Queue (antrian) adalah salah satu list linier dari struktur data yang beroperasi dengan cara First In First Out (FIFO) yaitu elemen pertama yang masuk merupakan elemen yang pertama keluar. Contohnya, ialah dalam sebuah antrian pembelian tiket bagi yang pertama masuk maka dia pulalah yang pertama keluar/selesai. Untuk penyisipan (INSERT) hanya dapat dilakukan pada satu sisi yaitu sisi belakang (REAR), sedangkan untuk penghapusan (REMOVE) pada sisi depan (FRONT) dari list.      

Queue/antrian adalah ordered list dengan penyisipan di satu ujung, sedang penghapusan di ujung lain. Ujung penyisipan biasa disebut rear/tail, sedang ujung penghapusan disebut front/head. Fenomena yang muncul adalah elemen yang lebih dulu disisipkan akan juga lebih dulu diambil.

Queue merupakan kasus khusus ordered list. Dengan karakteristik terbatas itu maka kita dapat melakukan optimasi representasi ADT Queue untuk memperoleh kerja paling optimal.

Baca Juga: Rekomendasi Aplikasi Perekam Layar Laptop Terbaik 2021

Misalnya Queue Q= (a1,a2,a3…,an), maka:

1.      Elemen a1 adalah elemen paling depan

2.      Elemen ai adalah diatas elemen ai-1, di mana 1<i<n.

3.      Elemen an adalah elemen paling belakang.

Head (Front) menunjuk ke awal antrian Q (elemen terdepan), sedangkan tail (rear)menunjuk akhir antrian Q (elemen paling belakang). Disiplin FIFO pada Queue berimplikasi jika elemen A, B, C, D, E dimasukkan ke Queue, maka penghapusan/ pengambilan elemen akan terjadi dengan urutan A, B, C, D, E.

Sebagai gambaran, cara kerja queue dapat disamakan pada sebuah antrean di suatu loket dimana berlaku prinsip ‘Siapa yang duluan antre dia yang akan pertama kali dilayani‘, sehingga dapat dikatakan prinsip kerja queue sama dengan prinsip sebuah antrean.

Karakteristik Queue

Karakteristik penting antrian sebagai berikut:

1.      Elemen antrian yaitu item-item data yang terdapat di elemen antrian.

2.      Head/Front (elemen terdepan dari antrian).

3.      Tail/Tear (elemen terakhir dari antrian).

4.      Jumlah elemen pada antrian (count).

Ada beberapa kondisi yang bisa kita temukan dalam queue. Kondisi antrian yang menjadi perhatian adalah:

1.      Penuh

Bila elemen di 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 di antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

   Operasi – Operasi dalam Queue dan Deklarasinya Dalam Program

Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru, di dalam Bahasa C, biasa disebut struct. Sebuah struktur data dari sebuah queue setidaknya harus mengandung tiga variabel, yakni:
Baca Juga: Mulai Aktivitas Tanpa Batas Dengan Berkonten Ria Bersama IndiHome

1.      Variabel head yang akan berguna sebagai penanda bagian depan antrian,

2.      Variabel tail yang akan berguna sebagai penanda bagian belakang antrian.

3.      Array data dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut.

Berikut adalah syntax untuk mendeklarasikan struktur data dari sebuah queue:

typedef struct {

int HEAD, TAIL;

int data[max];

   }Queue;  

Queue antrian;

Dimana, nilai MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan dalam queue. Setelah struktur data dari queue didefinisikan dengan syntax di atas, maka setelah itu dapat dibuat variabel-variabel baru yang mengacu pada tipe data Queue di atas, misalkan membuat sebuah variabel bernama antrian yang bertipe Queue: Queueantrian; 8.

Berikut adalah ilustrasi dari sebuah queue kosong dengan ukuran nilai MAX = 8:

Pada dasarnya, operasi-operasi dasar pada queue mirip dengan operasi-operasi dasar pada stack. Perbedaannya hanya pada prosedur push dan pop saja. Pada queue, prosedur yang berfungsi untuk memasukkan data/ nilai ke dalam antrian adalah enqueue, sedangkan prosedur untuk mengeluarkan data/ nilai dari antrian adalah dequeue. Berikut adalah operasi – operasi dasar dalam Queue:

1.      Prosedur Create

Sama pada stack, prosedur ini berfungsi untuk mengosongkan queue dengan cara meletakkan HEAD dan TAIL pada indeks array ke-(-1).

Berikut deklarasi prosedur create pada queue:

void create()

{

   antrian.HEAD = -1;

   antrian.TAIL = -1;

}

2.      Fungsi IsEmpty

Sama seperti fungsinya pada stack, fungsi ini berfungsi untuk melakukan pengecekan terhadap queue, apakah queue tersebut kosong atau tidak. Jika queue tersebut kosong (artinya, HEAD dan TAIL berada pada posisi -1, atau bisa juga ketika HEAD > TAIL), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika queue tersebut tidak kosong/ berisi (artinya, HEAD dan TAIL tidak berada pada posisi -1), maka fungsi akan mengembalikan nilai 0 (false).

Berikut deklarasi fungsi IsEmpty:

int IsEmpty(){

   if(antrian.HEAD=antrian.TAIL==-1)

return 1;

   else

return 0;

}

3.      Fungsi IsFull

Fungsi ini berfungsi untuk melakukan pengecekan terhadap queue, apakah queuetersebut penuh atau tidak. Jika queue tersebut penuh (artinya, TAIL berada pada posisi MAX), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika queue tersebut tidak penuh (artinya, TAIL tidak berada pada posisi MAX), maka fungsi akan mengembalikan nilai 0 (false).

Berikut deklarasi fungsi IsFull dalam Bahasa C:

int IsFull(){

   if (antrian.TAIL == max-1)

return 1;

   else

return 0;

}

4.       Prosedur EnQueue

Prosedur ini digunakan untuk memasukkan sebuah data / nilai ke dalam queue. Sebelum sebuah data / nilai dimasukkan ke dalam queue, maka prosedur ini terlebih dahulu melakukan pengecekan terhadap posisi HEAD dan TAIL. Jika posisi HEAD dan TAIL masih berada pada indeks ke-(-1) (artinya queue masih kosong), maka prosedur ini akan menempatkan HEAD dan TAIL pada indeks ke-0 terlebih dahulu, baru setelah itu memasukkan data / nilai ke dalam array data queue. Namun, jika posisi HEAD dan TAIL tidak berada pada posisi ke-(-1), maka posisi TAIL yang akan dinaikkan satu level. Jadi, pada proses enqueue, TAIL-lah yang berjalan seiring masuknya data baru ke dalam antrian, sedangkan HEAD akan tetap pada posisi ke-0.

Berikut deklarasi prosedur EnQueue:

void enqueue()

{

   if (IsEmpty()){

     antrian.HEAD=antrian.TAIL=0;

     cout<<”Masukkan data : “;

     cin>>antrian.data[antrian.TAIL];

   }

   else

   if(IsFull()){

     cout<<”ANTRIAN SUDAH PENUH!”;

   }

}

5.      Prosedur DeQueue

Prosedur ini digunakan untuk mengeluarkan atau membuang sebuah data/ nilai yang paling awal masuk (yang berada pada posisi HEAD, yakni yang paling depan dari antrian) ke dalam queue. Pekerjaan yang dilakukan oleh prosedur ini adalah menaikkan nilai HEAD satu level. Jadi, setiap satu kali data dikeluarkan, maka posisi HEAD naik bertambah satu level. Misalkan HEAD berada pada indeks ke-0, maka ketika akan mengeluarkan/ menghapus data pada posisi paling depan (pada posisi HEAD), prosedur ini akan menaikkan posisi HEAD ke indeks array ke-1. Atau dengan cara menggeser semua elemen antrian kedepan dan mengurangi TAIL dengan 1 penggeseran dilakukan dengan menggunakan looping.

Berikut deklarasi prosedur DeQueue:

int Dequeue(){

   int i;

   int e = antrian.data[antrian.HEAD];

   for(i=antrian.HEAD;i<=antrian.Tail-1;i++){

          antrian.data[i]=antrian.data[i+1];

   }

   Antrian.TAIL--;

   Return e;

}

6.       Prosedur Clear

Untuk menghapus elemen-elemen queue dengan cara membuat Tail dan Head= -1. Penghapusan elemen-elemen queue sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen queue tidak lagi terbaca. Berikut deklarasi prosedur clear:

void clear(){

   antrian.HEAD = -1;

   antrian.TAIL = -1

        cout<<"Antrian sudah dikosongkan! ";

     }

7.      Prosedur Tampil

Untuk menampilkan nilai-nilai elemen queue menggunakan looping dari HEAD sampai dengan TAIL. Berikut deklarasi prosedur tampil:

            void Tampil(){

   if(IsEmpty()){

          cout<<"Antrian kosong! ";

        }

        else {

          for(i=antrian.HEAD;i<=antrian.TAIL;i++)

         cout<<"Data pada antrian ke "<<i<<" = "<<antian.data[i]<<endl;

        }

     }

    Macam – Macam Queue dan Representasinya

1.    Queue dengan Linear Array

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Berikut ini diberikan deklarasi kelas QueueLinear sebagai implementasi dari Queue menggunakan linear array. Dalam prakteknya, kita dapat menggantinya sesuai dengan kebutuhan kita. Data dikses dengan field data, sedangkan indeks item pertama dan terakhir disimpan dalam variabel Head dan Tail. Konstruktor akan menginisialisasi nilai Head dan Tail dengan -1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX_QUEUE yang ditunjuk oleh data. Destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian.

    hapus elemen              1         2       ……..      ke – n                      sisip elemen

head                                tail

Di bawah ini diperlihatkan suatu queue yang akan menempati N elemen array memori, serta cara pengurangan (delete) dan penambahan (added) elemen pada queue tersebut. 

A

B

C

D

.....

Head   : 1

Tail      : 4

                        1          2          3          4        5         6          7        .....       N

REMOVE(Q)

B

C

D

.....

Head   : 2

Tail      : 4

                        1          2          3          4          5          6       7       .....       N

INSERT(INSERT(E),F)

B

C

D

E

F

.....

Head   : 2

Tail      : 6

                        1          2          3          4          5          6       7       .....        N

REMOVE(Q)

C

D

E

F

.....

Head   : 3

Tail      : 6

                        1          2          3          4          5          6          7          .....       N

Dapat dilihat bahwa setiap terjadi penghapusan elemen pada queue nilai (index) dari Head bertambah satu (1) ; dapat ditulis HEAD = HEAD+1. Begitu pula bila terjadi penambahan elemen pada queue nilai (index) Tail bertambah satu (1); dapat ditulis TAIL = TAIL + 1.

Akan terjadi ketidakefisienan bila penambahan elemen sudah pada posisi index N (Tail = N) maka tidak dapat lagi dilakukan penambahan elemen, sedangkan dilokasi memori yang lain (nilai di bawah N) masih terdapat memori array yang kosong. Untuk mengatasi hal tersebut maka kita bayangkan bahwa memori dari queue tersebut berbentuk melingkar dimana kedua ujungnya saling bertemu atau disebut juga dengan Circular Queue.

Contoh Program :

2.    Queue dengan Circular Array

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Jika menggunakan array untuk queue seperti di atas, maka ketika ada proses pengambilan (dequeue) ada proses pergeseran data. Proses pergeseran data ini pasti memerlukan waktu apalagi jika elemen queue-nya banyak. Oleh karena itu solusi agar proses pergeseran dihilangkan adalah dengan metode circular array. Kelebihan jenis ini adalah alokasi penyimpanan data yang optimal dan dinamis. Hal ini disebabkan penambahan maupun pengurangan data/ item antrian yang baru selalu menempati pos kosong yang disediakan sistem.

Queue dengan circular array dapat dibayangkan sebagai berikut:

5

6

7

9

Front   =1       

Tail      =4

      1              2              3              4              5

Aturan-aturan dalam queue yang menggunakan circular array adalah:

1.      Proses penghapusan dilakukan dengan cara nilai depan (front) ditambah 1: front=front+1.

2.      Proses penambahan elemen sama dengan linear array yaitu nilai belakang ditambah 1: tail=tail + 1.

3.      Jika front = maks dan ada elemen yang akan dihapus, maka nilai front = 1.

4.      Jika tail = maks dan front tidak 1 maka jika ada elemen yang akan ditambahkan, nilai tail = 1

5.      Jika hanya tinggal 1 elemen di queue (front = tail), dan akan dihapus maka front diisi 0 dan tail diisi dengan 0 (queue kosong).

Front dan Tail akan bergerak maju, jika:

1.      Untuk penambahan.

2.      Tail sudah mencapai elemen terakhir array akan memakai elemen pertama array yang telah dihapus.

3.      Untuk pngahapusan.

6.      Front telah mencapai elemen terakhir array, maka akan menuju elemen pertama jika antrian masih berisi elemen.

3.    Queue dengan Linked-List

Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list. Operasi-operasi Queue dengan Double Linked List:

1.      IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.

2.      IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.

3.      EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).

4.      DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

   Penerapan Aplikasi Queue

Meski Queue sangat sederhana, namun Queue merupakan kakas dasar penyelesaian masalah-masalah besar. Penggunaan Queue yang utama adalah untuk simulasi fenomena antrian di dunia nyata, serta fenomena antrian di pengolahan data.

   Penerapan Queue dalam Kehidupan Sehari – hari

1.      Pada Pembelian Tiket

Dalam kehidupan sehari-hari kita bisa dapati melalui penerapan pembelian tiket kereta api, tiket pesawat, tiket kapal laut, pembayaran tiket tol, pembayaran listrik, pembayaran air, dan lain sebagainya. Saat mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang datang terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue. Walaupun berbeda implementasi, tapi pada prinsipnya sama saja. Aplikasi dalam pembelian tiket kereta api:

a. Enqueue  : Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.

b. Dequeue : Setelah membeli tiket, langsung menuju tempat penungguan kereta, dengan sebelumnya petugas memeriksa cek tiket tersebut.

c. Clear : Pembeli tiket tersebut telah terhapus dari antrian karena sudah melewati pembayaran administrasi tersebut.

d. IsEmpty : Petugas tiket Kereta melihat tidak ada lagi yang ingin membeli tiket kereta.

e. IsFull  : Petugas Tiket Kereta melihat masih ada pembeli tiket kereta.

2.      Antrian Mobil di Pintu Tol

Ketika sebuah mobil datang, dari belakang akan menuju kedepan dari antrian. Setelah mobil mendapatkan karcis tol, antrian yang berada didepan akan maju. Pada saat menempatkan data pada ujung (tail) dari queue disebut dengan enqueue. Pada saat memindahkan data dari kepala (head) sebuah queue disebut dengan dequeue.

    Penerapan Aplikasi Queue dalam Aplikasi Komputer

1.      Pada Aplikasi Download Manager IDM

Queue juga dipakai sebagai salah satu fitur dari Internet Download Manager atau yang biasa disebut dengan IDM. Fitur ini sangat membantu bagi para pecinta download. Fitur ini akan membantu pengguna untuk mendownload file yang anda pilih satu-persatu, jadi sebanyak apapun anda mendownload, tetapi akan tetap dibuat antrian atau istilahnya queueing. Sistem yang diterapkan dalam fitur ini adalah pada saat download file, maka IDMakan mendownload satu per satu, hingga download file selesai maka baru akan secara otomatis mendownload file berikutnya.

   Printer Sharing

Pada suatu jaringan terdapat beberapa aplikasi yang dapat membantu kita untuk mempermudah pekerjaan kita untuk melakukan cetak hanya dengan menggunakan 1 printer yang dapat dipakai oleh banyak orang yaitu dengan cara printer sharing. Aplikasi ini menggunakan cara kerja queue atau juga disebut dengan antrian, untuk mencetak suatu document yang hanya menggunakan 1 printer yang dapat diakses oleh orang banyak, penggunaan queue diperlukan untuk mengatur sistem jaringan agar tidak terjadi error, dengan cara siapa yang terlebih dahulu mencetak suatu dokumen, dia akan dilayani terlebih dahulu untuk mencetak dokumen dan jika ada seseorang yang ingin mencetak dokumen dia akan dimasukan kedalam antirian dan menunggu untuk dapat mencetak sebuah document.

   Penerapan Aplikasi Queue dalam Sistem Produksi

Dalam sistem produksi terdapat banyak sekali aplikasi antrian, misalnya pada mesin pengisi (filling) botol minuman otomatis di pabrik. Mesin ini digunakan agar mempermudah pekerjaan, meminimalisir waktu, dan masih banyak lagi manfaat lainnya. Cara kerja dari mesin filling otomatis ini yaitu :

1.      Beberapa botol disiapkan pada tempatnya.

2.      Kemudian mesin akan mengisi air kedalam botol sesuai dengan posisinya.

3.      Botol yang diletakkan paling depan akan diisi oleh mesin paling awal, setelah botol paling depan terisi baru akan berjalan ke botol yang dibelakangnya, dan seterusnya.

Berbagi :