STRUKTUR DATA
-
Upload
fredericka-mclaughlin -
Category
Documents
-
view
91 -
download
6
description
Transcript of STRUKTUR DATA
STRUKTUR DATAQueue atau Antrian
Pengertian Queue• Queue/antrian adalah ordered list dengan penyisipan di
satu ujung, sedang penghapusan di ujung lain.• Ujung penyisipan disebut rear/tail.• Ujung penghapusan disebut front/head.• Head/front menunjuk ke awal antrian(elemen terdepan),
sedangkan tail/rear menunjuk ke akhir antrian (elemen paling belakang).
• Bersifat FIFO (First In First Out) yaitu Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya.
Simulasi antrian di dunia nyata, antara lain :• Lalu lintas udara, tinggal landas(take-off) dan
pendaratan(landing)• Antrian pembelian tiket di depan loket untuk bis,
kereta api, bioskop• Antrian mobil di depan gerbang jalan tol• Antrian kendaraan di jalan umum.
Penggunaan Queue
Operasi Queue• Create : membuat queue baru yang masih kosong • EnQueue: Memasukkan/menyisipkan data baru pada tail
(queue)• DeQueue: Mengeluarkan/menghapus data
terdepan/pertama dari antrian (di front), jika queue tidak kosong
• Clear: Menghapus seluruh antrian• Empty/IsEmpty: Memeriksa apakah antrian
kosong(mengembalikan nilai true jika queue kosong)• Full/IsFull: Memeriksa apakah antrian penuh
(mengembalikan nilai true jika queue penuh)• getfront: mengambil data pertama (di front), jika queue
tidak kosong.
Operasi Queue dengan Array• Create• Empty• Enqueue• Full • Dequeue• getfront
Queue Linier Array• Terdapat satu buah pintu masuk di suatu ujung
dan satu buah pintu keluar di ujung satunya• Sehingga membutuhkan 2 variabel: Head dan
Tail
Deklarasi Queue
• Operasi-operasi:Create()– Untuk menciptakan dan menginisialisasi
Queue– Dengan cara membuat Head dan Tail = -1
Create()
IsEmpty()– Untuk memeriksa apakah Antrian sudah
penuh atau belum– Dengan cara memeriksa nilai Tail, jika Tail = -1
maka empty– Kita 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
IsFull()– Untuk mengecek apakah Antrian sudah
penuh atau belum– Dengan cara mengecek nilai Tail, jika Tail >=
MAX-1 (karena MAX-1 adalah batas elemen array) berarti sudah penuh
Enqueue()– 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 terlebih dahulu
Dequeue()– Digunakan untuk menghapus elemen
terdepan/pertama (head) dari Antrian– Dengan cara menggeser semua elemen
antrian kedepan dan mengurangi Tail dgn 1 atau bisa menambah head dgn 1
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 elemen-elemen Antrian tidak lagi terbaca
Tampil()– Untuk menampilkan nilai-nilai elemen
Antrian– Menggunakan looping dari head s/d tail
Queue dengan Array#include<iostream.h>#include<conio.h>#include<stdlib.h> #define MAX 10 //ukuran maksimum queue
void enqueue(int queue[], int *tail, int nilai);void dequeue(int queue[], int *head, int *tail, int *nilai);
int main(){
int queue[MAX];int head, tail;int n, nilai;
head = tail = (-1);
do{
do{
cout<<"Masukkan Nilai Elemen : ";
cin>>nilai;enqueue(queue,&tail,nilai);
cout<<endl;cout<<"Tekan 1 untuk
Melanjutkan"<<endl;cin>>n;
} while (n == 1);
cout<<endl;cout<<"Tekan 1 untuk Menghapus
Sebuah Elemen"<<endl;cin>>n;
cout<<endl;cout<<"Tekan 1 untuk Menghapus Sebuah Elemen"<<endl;cin>>n;
while(n == 1){
dequeue(queue,&head,&tail,&nilai);cout<<"Nilai telah
dihapus : "<<nilai<<endl;cout<<endl;cout<<"Tekan 1 untuk
Menghapus Sebuah Elemen : ";cin>>n;
}cout<<endl;cout<<"Tekan 1 untuk
Melanjutkan"<<endl;cin>>n;
} while (n == 1);
getch();return 0;
}
void enqueue(int queue[], int *tail, int nilai){
if(*tail < MAX-1){
*tail = *tail + 1;queue[*tail] = nilai;
}else{
cout<<"Queue Penuh, enqueue Tidak Dapat Dilakukan"<<endl;
exit(0);}
}
void dequeue(int queue[], int *head, int *tail, int *nilai){
if(*head == *tail){
cout<<"Queue Kosong, dequeue Tidak Dapat Dilakukan"<<endl;
exit(0);}else{
*head = *head + 1;*nilai = queue[*head];
}}
Tampilan Program