Queue
By Emanuel Lienardi - 6:57 AM
Queue dll
Antrean atau queue adalah operasi
penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut
sisi belakang (REAR), dan operasi penghapusan (deletion) hanya diperbolehkan
pada sisi lainnya, yang disebut sisi depan (FRONT), dari list. pada antrian prinsip yang digunakan adalah FIFO
(Fist In Fist Out) yang aartinya Elemen yang pertama masuk ke antrian akan
keluar pertama kalinya . Sebagai contoh
, antrean (X1, X2, X3,...,XN). Kita notasikan bagian depan dari antrean X
sebagai FRONT(X) dan bagian belakang sebagai REAR(X). Jadi untuk antrean X =
[X1, X2, X3 …, XN] :
FRONT(X) = X1 dan REAR(X) = XN
Kita menggunakan notasi NOEL(X) untuk menyatakan jumlah elemen di dalam
antrean X. NOEL(X) mempunyai harga integer. Untuk antrean X = [X1,X2,X3…, XN],
maka NOEL(X) = N.
Prinsip antreannya ada dua, yaitu FIFO (First In First Out), dan satunya lagi
FCFS (First Come First Serve).
Berikut contoh pendeklarasiannya
Operasi pada queue :
1. Create () adalah untuk menciptakan atau
menganalisis queue dengan cara membuat head dan tail = -1
2. IsEmpty () adalah untuk memeriksa apakah
antrean sudah penuh atau belum, dengan cara memeriksa nilai Tail. Jika tail =
-1, maka empty. Kita tidak perlu memeriksa head, karena head adalah tanda untuk
kepala antrian (elemen pertama dalam antrian).
3. IsFull () adalah untuk mengecek apakah
antrean sudah penuh atau belum dengan cara mengecek nilai Tail. Jika tail >=
MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh.
4. Enqueue () digunakan untuk menambahkan
elemen ke dalam antrean penambahan akan dilakukan pada elemen paling belakang. Penambahan
elemen selalu menggerakkan variabel Tail dengan cara increment counter Tail
terlebih dahulu.
5. Dequeue berfungsi untuk menghapus elemen
di depan atau pertama (head) dari antrean dengan menggeser semua elemen antrean
ke depan dan mengurangi Tail dengan 1 penggeseran dilakukan dengan menggunakan
looping.
6. Clear () digunakan untuk penghapusan pada
elemen – elemen antrean dengan membuat tail dan head = -1. Penghapusan elemen –
elemen antrean sebenarnya tidak menghapus array nya, namun hanya men-set indeks
pengaksesannya ke nilai -1 sehingga elemen – elemen antrean tidak lagi terbaca.
7. Tampil () digunakan untuk menampilkan
nilai dari elemen antrean menggunakan looping dari head sampai tail.
Contoh
Programnya :
1.
#include <iostream>
2.
#include <conio.h>
3.
#ifdef __cplusplus__
4.
#include <cstdlib>
5.
#else
6.
#include <stdlib.h>
7.
#endif
8.
9.
#define max 6
//Mendeklarasikan max data pada queue
10.
11.
int value[max];
12.
int awal = -1, akhir = -1, i;
13.
14.
//membuat fungsi IsEmpty
15.
bool IsEmpty(){
16.
if (awal == -1 && akhir == -1)
17.
return true;
18.
else
19.
return false;
20.
}
21.
22.
//membuat fungsi IsFull
23.
bool IsFull(){
24.
if (akhir == max - 1)
25.
return true;
26.
else
27.
return false;
28.
}
29.
30.
//membuat enqueue, untuk
memasukkan data kedalam queue / antrian
31.
void Enqueue(){
32.
if (IsFull())
33.
{
34.
cout << "Queue sudah terlalu banyak, silahkan sabar menunggu ";
35.
}
36.
else {
37.
if (IsEmpty()){
38.
awal = akhir = 0;
39.
cout << "inputkan value : "; cin >> value[akhir];
40.
}
41.
else {
42.
akhir++;
43.
cout << "inputkan value : "; cin >> value[akhir];
44.
}
45.
}
46.
}
47.
48.
//Membuat fungsi Dequeue
49.
void Dequeue(){
50.
if (IsEmpty()){
51.
cout << "Queue tidak ada data! ";
52.
getch();
53.
}
54.
else {
55.
cout << "Value yang diambil : " << value[awal];
56.
for (i = awal; i <= akhir - 1; i++)
57.
value[i] = value[i + 1];
58.
akhir--;
59.
if (akhir == -1)
60.
awal = -1;
61.
getch();
62.
}
63.
}
64.
65.
//Membuat Prosedur clear
66.
void Clear(){
67.
awal = akhir = -1;
68.
cout << "Queue sudah
dikosongkan ! "; getch();
69.
}
70.
71.
//Membuat Prosedur View
72.
void View(){
73.
if (IsEmpty()){
74.
cout << "Queue tidak ada data ! ";
75.
getch();
76.
}
77.
else {
78.
for (i = awal; i <= akhir; i++)
79.
cout << "Value pada indeks
ke- " << i << " = " << value[i] << endl;
80.
getch();
81.
}
82.
}
83.
84.
int main(){
85.
int jawab;
86.
do{
87.
if (system("CLS")) system("clear");
88.
cout << "=========================================" << endl;
89.
cout << " PROGRAM
QUEUE
" << endl;
90.
cout << "=========================================" << endl;
91.
cout << "1. Enqueue " << endl;
92.
cout << "2. Dequeue " << endl;
93.
cout << "3. Clear " << endl;
94.
cout << "4. View " << endl;
95.
cout << "5. keluar " << endl;
96.
cout << "inputkan pilihan kamu : ";
97.
cin >> jawab;
98.
switch (jawab){
99.
case 1:
100.
Enqueue(); break;
101.
case 2:
102.
Dequeue(); break;
103.
case 3:
104.
Clear(); break;
105.
case 4:
106.
View(); break;
107.
}
108.
} while (jawab != 5);
109.
}
Tampilan program
akhir :
Collision
Collision adalah apabila nilai atau key-nya sama dan bertubrukan, cara menanggulanginya dapat dengan menggunakan Linear Probing atau Chaining.
Linear Probing adalah apabila ada key hash yang sama maka akan ditempatkan di tempat index kosong yang terdekat.
Chaining adalah apabila ada key hash yang sama maka akan ditempatkan disampingnya sehingga membentuk rantai atau Linked list.
0 comments