MODUL PEMROGRAMAN 2
Queue (Antrian) Secara harfiah queue dapat diartikan sebagai antrian. Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yangterakhir masuk akan keluar terakhir. Berikut contoh simulasi proses pada Queue :
Queue dalam kehidupan sehari-hari seperti antrian pada penjualan tiket kereta api, dimana orang yang pertama datang adalah orang yang pertama kali dilayani untuk membeli tiket. Jika ada orang baru yang datang akan membali tiket, maka posisinya berada pada urutan paling belakang dalam antrian tersebut. Orang yang berada pada posisi terakhir dalam antrian adalah yang terakhir Siti yuliyanti
Page 1
MODUL PEMROGRAMAN 2
kali dapat dilayani dan memperoleh tiket kereta api (kalau kurang beruntung, maka akan kehabisan tiket). Contoh lain adalah nasabah yang antri di teller bank, paket data yang menunggu untuk ditransmisikan lewat internet, antrian printer dimana terdapat antrian print job yang menunggu giliran untuk menggunakan printer, dsb. Istilah-istilah yang digunakan dalam queue (antrian) Memasukkan data (insert) disebut juga dengan put, add, atau enqueue. Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue. Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau end (akhir). Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan istilah kepala (head). Circular Queue Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif. Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah merubah posisi front dan rear saja. Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array (atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah? Situasi seperti itu bisa dilihat seperti gambar berikut:
Siti yuliyanti
Page 2
MODUL PEMROGRAMAN 2
Untuk
menghindari
permasalahan
seperti itu (tidak bisa memasukkan data baru) – meskipun queue-nya
belum
penuh,
maka front danrear-nya berputar (kembali) ke bagian
awal
dinamakan
array.
Kejadian
dengan circular
seperti
ini
queue (atau
kadang-kadang disebut juga dengan istilah ring buffer). Kejadian seperti ini seperti terlihat pada gambar disamping : Perhatikan bahwa setelah rear berputar (kembali) ke bagian awal array, posisinya sekarang di bawah front, kebalikan dari posisi aslinya (front berada di bawah rear). Coba hapus beberapa data sehingga pada suatu saat front juga akan berputar (balik) ke bagian awal array, sehingga front dan rear akan ke susunan aslinya (front di bawah rear).
head
X
tail
Dalam Queue, dikenal istilah head yaitu : data paling awal atau pertama diinput, dan tail : data yang paling akhir diinput atau terakhir dimasukan. Berikut contoh source code queue : #include <stdio.h> #include
main() { int queue[5]; int depan = -1; int belakang = -1; int pilihan, data, i; do{ printf("\n--MENU--\n"); printf("1. ENQUEUE\n2. DEQUEUE\n3. VIEW\n4. EXIT\n\n\n"); printf("Pilihan = "); scanf("%d", &pilihan);
Siti yuliyanti
Page 3
MODUL PEMROGRAMAN 2
switch (pilihan) { case 1:
//enqueue
//apakah queue belum penuh? if (belakang < 4 ) {
printf("Data Masuk = "); scanf("%d", &data); queue[belakang+1] = data; belakang++; if (belakang == 0) depan = 0;
} else printf("Queue penuh!\n");break;
case 2: //dequeue //apakah queue belum kosong? if (depan <= belakang) {
printf("Data keluar = %d\n", queue[depan]); depan++;
} else printf("Queue kosong!\n");break; case 3: printf("\nISI QUEUE : "); for(i=depan; i<=belakang; i++) printf("%d ", queue[i]); printf("\n\n");break; } }while (pilihan != 4); }
LATIHAN BuatlahpProgram shift yaitu, menjadikan sebuah bilangan desimal inputan menjadi bilangan biner, lalu setelah menjadi biner, akan dilakukan dequeue lalu di enqueue sebanyak shift.
Siti yuliyanti
Page 4
MODUL PEMROGRAMAN 2
contoh : bilangan desimal : 25 di shift : 3 maka hasilnya adalah : 7 Kenapa kok bisa 7 ?????? nah, caranya seperti ini……!!! dari bilangan desimal 25 dikonversikan menjadi biner menjadi 11001 setelah dikonversikan, maka program di shift sebanyak 3x 11001 —> shift pertama, angka 1 yang terakhir di dequeue lalu di enqueue sehingga menjadi11100 11100 —> shift kedua, angka 0 yang terakhir di dequeue lalu di enqueue sehingga menjadi01110 01110 —> shift ketiga, angka 0 yang terakhir di dequeue lalu di enqueue sehingga menjadi 00111 setelah selesai menjadi bilangan biner 00111 akan dikonversikan menjadi desimal 1 —> 20 x 1 = 1 1 —> 21 x 1 = 2 1 —> 22 x 1 = 4 0 —> 23 x 0 = 0 0 —> 24 x 0 = 0 ———————– + 7
Siti yuliyanti
Page 5
