SOAL
1)
Jelaskan
perbedaan antara queue dengan stack.
2)
Buatlah
contoh program dari Queue.
3)
Sebutkan
contoh Queue yang Anda terapkan dalam kehidupan sehari – hari.
4)
Jelaskan
konsep dari operasi – operasi Queue.
Apa
saja kondisi yang harus diperhatikan dalam operasi – operasi Queue.
Jawab :
PERBEDAAN STACK DAN QUEUE
QUEUE
Secara harfiah queue dapat diartikan sebagai antrean. Queue merupakan
kumpulan data dengan penambahan data hanya dapat dilakukan melalui satu sisi,
yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head).
Queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan
keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.
Elemen yang pertama kali masuk kedalam queue disebut elemen depan
(front/head of queue), sedangkan elemen yang terakhir kali masukk queue disebut
elemen belakang (rear/tail of queue).
Aturan penambahan dan penghapusan elemen pada queue, yaitu pada
penambahan elemen selalu di lakukan melalui salah satu ujung, menempati posisi
di belakang elemen-elemen yang sudah masuks ebelumnya atau menjadi elemen
paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda,
yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan.
STACK
Stack adalah sebuah abstract data type (ADT) yang berisi koleksi data
item yang hanya dapat diakses pada akhir bagian stack tersebut, biasa disebut
top. Hal ini berarti bahwa didalam sebuah stack, kita dapat memasukkan (insert)
dan menghapus (delete) item hanya dari posisi top tersebut. Item terakhir yang
kita masukkan kedalam sebuah stack adalah item yang paling pertama harus kita
keluarkan. Itulah mengapa stack disebut sebagai Last-In-First-Out (LIFO) data
structure. Kalimat sederhana yang dapat menjelaskan konsep tersebut adalah
kalimat “Masuk belakangan keluar duluan”.
Didalam kehidupan sehari-hari, terdapat beberapa contoh penerapan
algoritma dari data structure ini, seperti dalam membuat suatu tumpukan piring,
tumpukan buku, tumpukan koin, tusuk sate, atau bahkan cara memakai gelang.
Salah satu contoh, dalam membuat suatu tumpukan piring kita pasti menempatkan
piring pertama berada pada posisi paling bawah, dan piring terakhir
berada pada posisi paling atas. Nah, ketika kita hendak mencuci atau mengambil
piring tersebut, maka kita akan mengambil piring pada tumpukkan atas terlebih
dahulu dan seterusnya hingga mencapai piring paling bawah. Hal tersebut juga
serupa pada tumpukan buku, koin, tusuk sate dan cara memakai gelang. Saya rasa
ilustrasi tersebut cukup menjelaskan konsep LIFO dari stack.
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.
Sedangkan Pada queue,
operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu
dilakukan melalui salah satu ujung, 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.
CONTOH PROGRAM
PROGRAM QUEUE;
uses wincrt;
const max=25;
type
queue=record
jenis:array [1..max] of string;
plat:array
[1..max] of real;
depan,
belakang:0..max;
end;
var produk :
queue;
tempjenis : string;
tempplat : real;
pil :1..4;
tanya : char;
function penuh
(s:queue) : boolean;
begin
if
s.belakang=max then penuh := true
else penuh :=
false;
end;
function
kosong (s:queue):boolean;
begin
if
s.belakang=0 then kosong:=true
else kosong:=false;
end;
procedure push
(var s:queue; tempjenis:string; tempplat:real);
begin
if penuh(s)
then writeln ('maaf, antrian sudah penuh.hapus beberapa data kemudian ulangi
lagi')
else begin
s.belakang:=s.belakang+1;
s.jenis[s.belakang]:=tempjenis;
s.plat[s.belakang]:=tempplat;
writeln('jumlah data antrian sekarang
',s.belakang,' buah');
end;
end;
{procedure
pop}
procedure pop
(var s:queue);
var i:byte;
Begin
if kosong(S)
then
writeln('antrian
kosong')
else begin
for i:=1 to
s.belakang-1 do
Begin
s.jenis
[i]:=s.jenis[i+1];
s.plat
[i]:=s.plat[i+1];
end;
s.belakang:=s.belakang-1;
writeln('data yang ada di antrian sekarang
ada',s.belakang,' buah');
end;
end;
{procedure
cetak}
procedure
cetak (s:queue);
var i:byte;
begin
if kosong (s)
then writeln('tidak ada data')
else begin
writeln('+==================================+');
writeln('| No
| Tujuan |
harga |');
writeln('+----
----------------- -----------+');
for i:=1 to
s.belakang do
writeln('|',i:3,'
|',s.jenis[i]:16,' | ':2,s.plat[i]:9:2,' |':2);
writeln('+==================================+');
end;
end;
begin
repeat
clrscr;
writeln(' PROGRAM QUEUE TIKET KERETA API');
writeln('==================================');
writeln;
writeln('1.
Masukkan Antrian Tiket');
writeln('2.
Lihat Data Antrian');
writeln('3.
Ambil Data Antrian');
writeln('4.
Exit');
writeln;
writeln('PILIHAN
[1/2/3/4]');
writeln;
write('masukan
pilihan anda : ');readln(pil);
writeln;
case pil of
1:begin
repeat
writeln
('Masukkan Data Transaksi');
write
('Tujuan : ');readln(tempjenis);
write
('Harga : Rp. ');readln(tempplat);
push
(produk,tempjenis,tempplat);
writeln;
write('Tambah
Data Lagi? [Y/N] => ');readln(tanya);
until upcase
(tanya)<>'Y';
end;
2: begin
cetak
(produk);
write('press
enter to continue ');readkey;
end; 3: begin
repeat
CONTOH QUEUE DALAM KEHIDUPAN SEHARI-HARI
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. Walaupun berbeda
implementasi, Konsep struktur data queue adalah First In First Out(FIFO).
Queue
setidaknya harus memiliki operasi-operasi sebagai berikut:
EnQueue :
Masukkan data ke dalam antrian
DeQueue :
Mengeluarkan data terdepan dari antrian
Clear :
Menghapus seluruh antrian
IsEmpty :
Memeriksa apakah antrian kosong
IsFull :
Memeriksa apakah antrian penuh
Dalam
pembelian tiket kereta api:
Enqueue :
Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.
Dequeue :
Setelah membeli tiket, langsung menuju tempat penungguan kereta, dengan
sebelumnya petugas memeriksa cek tiket tersebut.
Clear :
Pembeli tiket tersebut telah terhapus dari antrian karena sudah melewati
pembayaran administrasi tersebut.
IsEmpty :
Petugas tiket Kereta melihat tidak ada lagi yang ingin membeli tiket kereta.
IsFull :
Petugas Tiket Kereta melihat masih ada pembeli tiket kereta.
KONSEP QUEUE
- Create()
Untuk
menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail = -1
- IsEmpty()
Untuk
memeriksa apakah antrian masih kosong atau sudah terisi dengan cara memeriksa
nilai tail, jika tail = -1 maka empty Pergerakan pada Antrian terjadi dengan
penambahan data antrian kebelakang,
yaitu menggunakan nilai tail.
2.
IsFull()
untuk mengecek apakah Antrian sudah
penuh atau belum
Dengan cara mengecek nilai tail, jika tail >= MAX-1 (karena MAX-1 adalah
batas data array pada C) berarti sudah penuh
- Enqueue
Untuk menambahkan data ke dalam
antrian, penambahan data selalu ditambahkan di data paling belakang
Penambahan data selalu menggerakan variabel tail dengan cara increment counter
tail.
- Dequeue()
Digunakan untuk menghapus data
terdepan dari Antrian
Dengan cara mengurangi counter tail dan menggeser semua data antrian kedepan.
Penggeseran dilakukan dengan menggunakan looping
- Clear()
Untuk menghapus semua data Antrian
dengan cara membuat tail dan head = -1 . Penghapusan data-data antrian
sebenarnya tidak menghapus arraynya, namun hanya mengeser indeks pengaksesannya
ke nilai -1 sehingga data-data Antrian tidak lagi terbaca.
- Tampil()
Untuk menampilkan nilai-nilai data
Antrian menggunakan looping dari head s/d tail
KONDISI YANG HARUS DI PERHATIKAN 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.
