Queue
1. Pengertian queue
Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan. Analoginya sama dengan antrian di sebuah loket pembelian tiket kereta, orang yang datang lebih dahulu, maka akan dilayani terlebih dahulu, dan akan selesai lebih dulu dari orang-orang yang datang setelahnya.
Queue adalah suatu kumpulan data yang mana penambahan data atau elemen hanya dapat dilakukan pada sisi belakang, sedangkan penghapusan atau pengeluaran elemen dilakukan pada sisi depan. Antrian queue dapat diartikan sebagai suatu kumpulan data yang seolah olah terlihat seperti ada data yang diletakkan di sebelah data yang lain.
Antrian dapat dibuat baik dengan array maupun dengan struct. Pada pembuatan antrian dengan array, antrian yang disajikan bersifat statis. Ini disebabkan oleh jumlah maksimal array yang sudah ditentukan sejak deklarasi awal. Seperti pada gambar di bawah ini.
2. Deklarasi queue
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 dua tiga variabel, yakni variabel HEAD yang akan berguna sebagai penanda bagian depan antrian, variabel TAIL yang akan berguna sebagai penanda bagian belakang antrian dan ARRAY DATA dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut. Berikut adalah syntax untuk mendeklarasikan struktur data dari sebuah queue menggunakan Bahasa C :
typedef struct
{
int HEAD, TAIL;
int data[max+1];
}Queue;
Dimana, nilai MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan dalam queue. Setelah strukutr 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 :
Queue antrian;
Dalam tulisan ini, sebuah queue didefinisikan dengan array berukuran MAX + 1, maksudnya adalah agar elemen array ke-0 tidak digunakan untuk menyimpan data, melainkan hanya sebagai tempat „singgah‟ sementara untuk variabel HEAD dan TAIL. Sehingga, jika HEAD dan TAIL berada pada elemen array ke-0, berarti queue tersebut dalam kondisi kosong (tidak ada data yang disimpan).
Berikut gambaran dari queue dengan array, beserta operasi dalam programnya.
Dalam queue, terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya. Sehingga membutuhkan variabel Head dan Tail.
Operasi Create()
• Untuk menciptakan dan menginisialisasi Queue
• Dengan cara membuat Head dan Tail = -1
Operasi IsEmpty()
• Untuk memeriksa apakah Antrian sudah penuh atau belum
• Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty bernilai benar
• Tidak memeriksa Head, karena Head adalah tanda untuk kepala
antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
• Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian
kebelakang, yaitu menggunakan nilai Tail
Operasi IsFull()
• Untuk mengecek apakah Antrian sudah penuh atau belum, jika antrian [enuh maka bernilai benar
• Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1
adalah batas elemen array pada C) berarti sudah penuh
Operasi Enqueue(data)
• Untuk menambahkan elemen ke dalam Antrian, penambahan elemen
selalu ditambahkan di elemen paling belakang
• Penambahan elemen selalu menggerakan variabel Tail dengan cara
increment counter Tail
Operasi Dequeue()
• Digunakan untuk menghapus elemen terdepan atau pertama, dari Antrian
• Dengan cara mengurangi counter Tail dan menggeser semua elemen
antrian kedepan.
• Penggeseran dilakukan dengan menggunakan looping
Operasi Clear()
• Untuk menghapus elemen-elemen antrian dengan cara membuat Tail dan
Head = -1
• Penghapusan elemen-elemen antrian sebenarnya tidak menghapus
arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1
sehingga elemenelemen antrian tidak lagi terbaca
Operasi Print()
• Untuk menampilkan nilai-nilai elemen Antrian
• Menggunakan looping dari head hingga tail
Perbedaan antara stack dan queue terdapat pada aturan penambahan dan
penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen
dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas tersebut akan dihapus paling awal, sifat demikian dikenal dengan LIFO. Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung antrian, menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan. Sifat yang demikian dikenal dengan FIFO (first in first out).
#include
<iostream.h>
#include
<stdio.h>
#include
<conio.h>
#define MAX 10
28
typedef struct
{
int data[MAX];
int head;
int tail;
} Queue;
Queue antrian;
void Create()
{
antrian.head=antrian.tail=-1;
}
int IsEmpty()
{
if(antrian.tail==-1)
return 1;
else
return 0;
}
int IsFull()
{
if(antrian.tail==MAX-1)
return 1;
else return 0;
}
void Enqueue(int
data)
{
if(IsEmpty()==1)
{
antrian.head=antrian.tail=0;
antrian.data[antrian.tail]=data;
cout<<"Data
"<<antrian.data[antrian.tail]<<"
Masuk!!";
}
else
if(IsFull()==0)
{
antrian.tail++;
antrian.data[antrian.tail]=data;
cout<<"Data
"<<antrian.data[antrian.tail]<<"
Masuk!!";
}
else if
(IsFull() == 1)
{
cout<<"Ruangan
Penuh!!"<<endl;
cout<<data<<"
Ga Bisa Masuk!!";
}
}
29
void Dequeue()
{
int i;
int e =
antrian.data[antrian.head];
if (antrian.tail
== -1)
{
cout<<"Ga
Ada Antrian... Data Kosong"<<endl;
}
else
{
for(i=antrian.head;i<=antrian.tail-1;i++)
{
antrian.data[i]
= antrian.data[i+1];
}
antrian.tail--;
cout<<"Data
yang Keluar lebih dulu = "<<e<<endl;
}
}
void Clear()
{
antrian.head=antrian.tail=-1;
cout<<"Duh
Lega, Ruangan Jadi Ga Sumpek...."<<endl;
cout<<"Data
Clear...";
}
void Tampil()
{
if(IsEmpty()==0)
{
cout<<"Data
Dalam Antrian"<<endl;
cout<<"==========================="<<endl;
cout<<endl;
for(int
i=antrian.head;i<=antrian.tail;i++)
{
cout<<"|
"<<antrian.data[i]<<" |";
}
}
else
cout<<"Ga Ada Antrian... Data Kosong";
}
void main()
{
int pil;
int data;
Create();
do
{
clrscr();
cout<<"Implementasi
Antrian dengan Struct"<<endl;
cout<<"=================================="<<endl;
cout<<endl;
30
cout<<"1.
Enqueue(Push)"<<endl;
cout<<"2.
Dequeue(PoP)"<<endl;
cout<<"3.
Print"<<endl;
cout<<"4.
Clear"<<endl;
cout<<"5.
Exit"<<endl;
cout<<"Pilihan
Anda= "; cin>>pil;
switch(pil)
{
case 1:
{
cout<<endl;
cout<<"Data
= "; cin>>data;
Enqueue(data);
break;
}
case 2:
{
cout<<endl;
Dequeue();
break;
}
case 3:
{
cout<<endl;
Tampil();
break;
}
case 4:
{
cout<<endl;
Clear();
break;
}
}
getch();
} while(pil!=5);
}
3. Perbedaan Stack dan Queue
Stack memakai sistem LIFO atau last in first out (yang pertama masuk akan keluar terakhir, begitu pula yang terakhir masuk akan keluar pertama kali) apabila kita mengahapus data untuk keluar, maka data yang terakhirlah yang akan terhapus atau keluar terlebih dahulu.
Sementara queue memakai siste FIFO atau first in first out (yang pertama masuk akan keluar pertama, begitu pula yang masuk terakhir akan keluar terakhir) yang apabila kita menghapus atau mengeluarkan data, maka data yang pertamalah yang akan terhapus atau keluar terdahulu dan data yang terakhir akan terhapus atau keluar terakhir.
Perbedaan juga terletak pada operasi yang digunakan pada keduanya.
Operasi pada stack :
- Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
- Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
- Clear : digunakan untuk mengosongkan Stack.
- Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
- MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
- IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
- Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.
Operasi pada Queue :
- Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
- Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
- EnQueue : berfungsi memasukkan data kedalam antrian.
- DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
- Clear : Menghapus seluruh Antrian
- IsEmpty : memeriksa apakah antrian kosong
- IsFull : memeriksa apakah antrian penuh
4. 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).
5. Penerapan Queue
Dalam kehidupan sehari-hari.
- 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 antrean adalah enqueue. Dalam suatu antrean, yang datang terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrean adalah dequeue. Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :
a.EnQueue : Memasukkan data ke dalam antrean
b.DeQueue : Mengeluarkan data terdepan dari antrean
c. Clear : Menghapus seluruh antrean
d. IsEmpty : Memeriksa apakah antrean kosong
e. IsFull : Memeriksa apakah antrean penuh
Penerapannya dalam aplikasi 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 antrean 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.
Dalam aplikasi komputer
- 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 dipilih satu-persatu, jadi sebanyak apapun mendownload, tetapi akan tetap dibuat antrean atau istilahnya queueing. Sistem yang diterapkan dalam fitur ini digunakan pada saat download file, maka IDM akan mendownload satu per satu, hingga download file selesai maka baru akan secara otomatis mendownload file berikutnya.
- Pada 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 antrean, 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 antrian dan menunggu untuk dapat mencetak sebuah document.
Dalam sistem produksi
Dalam sistem produksi terdapat banyak sekali aplikasi antrean, 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.
Prinsip queue atau antrean digunakan dalam mesin ini, karena FIFO (First In First Out). Jadi botol yang paling awal sampai pada pengisi air, maka botol itu juga yang akan pertama keluar setelah diisi.
6. Queue berprioritas
Dalam antrean yang telah dibahas di atas, semua elemen yang masuk dalam antrean dianggap mempunyai prioritas yang sama, sehingga elemen yang masuk lebih dahulu akan diproses lebih dahulu. Dalam praktek, elemen-elemen yang akan masuk dalam suatu antrean ada yang dikatakan mempunyai prioritas yang lebih tinggi dibanding yang lain. Antrean yang demikian ini disebut dengan antrean berprioritas (priority queue). Dalam antrean berprioritas, setiap elemenn yang akan msuk dalam antrean sudah ditentukan lebih dahulu prioritasnya.
7. Kelebihan dan kekurangan queue
- Kelebihan
Data yang pertama masuk maka akan pertama dilayani.
- Kelemahan
Data yang terakhir masuk, bila waktu pelayanan habis kemungkinan bisa tidak dilayani.
Referensi :
http://allaboutalgoritma.blogspot.com/2009/07/queue.html
http://algoritmamu.blogspot.com/2017/01/stack-dan-queue.html
https://www.academia.edu/32592023/LAPORAN_PRAKTIKUM_5_ALGORITMA_STRUKTUR_DATA-QUEUE
https://www.cappluse.com/2018/02/dasar-analisis-algoritma-queue-atau.html
0 komentar:
Posting Komentar