PRAKTIKUM 7Queue

2.1 Tujuan

Setelah melakukan praktikum ini siswa diharapkan mengerti :

1. Cara lain untuk merepresentasikan sekumpulan data menggunakan queue

2. Anggota/elemen struktur dari sebuah queue dengan array atau linked list

3. Cara penggunaan queue dengan array ataupun dengan linked list

4. Penelusuran simpul/pembacaan queue : FIFO (First In First Out)

2.2 Dasar Teori

Misal Max Elemen = 6

belakang

keluar masuk ①

belakang

keluar masuk ②

belakang

keluar masuk ③

1. Sesudah enqueuring 5,3 (belakang=2)2. Sesudah enqueuring 8,9,2 (belakang=5)3. Sesudah dequeuring 5,3 (belakang=3)

Depan belakang

keluar masuk ①

Depan = belakangkeluar masuk ②

belakang depankeluar masuk ③

1. Sesudah enqueuring 5,3 (depan=1,belakang=2)2. Sesudah enqueuing 8,9,2,1 (depan=belakang=6)3. Sesudah dequeuing 5,3 dan enqueuing 4(depan=6,belakang=1

35

29835

298

35

129835

12984

Definisi struktur Queue dengan array

#define MAXISI 10 //maksimum data isi

#define MAX 10 //maksimum data stack

//Definisi struktur stack

Struct antrian {

Int isi[MAXISI];

Int depan; //Posisi elemen I

Int belakang; //Posisi elemen terakhir

};

Struct antrian que[MAX]; //deklarasi var antrian

//Dengan array mungkin terjadi overflow, antrian telah penuh //sementara masih akan menambahkan elemen baru

Kondisi awal :

Belakang=0;

Depan=1; //Antrian kosong jika : Belakang<Depan

//Banyaknya elemen yang ada dalam antrian : Belakang-Depan + 1

Operasi enqueuing :

Void enque(struct antrian que,int penuh, int x)

{ if(que.belakang==MAX) que.belakang=1;

Else que.belakang=que.belakang+1;

If(que.depan==que.belakang)penuh=1;

Else que.isi[que.belakang]=x;

} }

Operasi Dequeuing :

Int deque(struct antrian que)

{

If(que.depan==que.belakang) return 0;

Else {

Temp=que.isi[que.depan];

If(depan==MAX) que.depan=1;

Else que.depan=que.depan+1;

Return(temp);

} }

//Definisi struktur queue dengan Linked list

Struct antrian

{

Int isi; struct antrian *next;

};

Struct antrian *data; //deklarasi var antrian

//Harus mempunyai 2 buah pointer untuk mencatat elemen //plg depan(kepala) dan elemen plg akhir (ekor)

Operasi enqueueing

Void enque(struct antrian *kepala, struct antrian *ekor, struct antrian *baru,int x)

{

If(ekor==NULL)

{ kepala = (struct antrian*)malloc(sizeof(struct antrian));

Kepala->isi=x; kepala->next=kepala;

Ekor=kepala;

}

Else { baru=(struct antrian*)malloc(sizeof(struct antrian));

Baru->isi=x; baru->next=kepala;

Ekor=baru; }

}

Operasi Dequeuing :

Void deque(struct antrian *kepala, struct antrian *hapus, int x) {

If(kepala==NULL)

{ kepala->next=kepala;

}

Else { hapus=kepala->next;

Kepala->next=hapus->next;

Free(hapus); }

}

1.1. Latihan Program1. Mendeklarasikan, memasukkan data, dan menampilkan pada stack menggunakan

array(=penelusuran LIFO)

Hasil Run :

2. Aplikasi queue simulasi tempat parker mwnggunakan single linked list . Persoalan :

(a) Tempat parkir mobil dibuat 1 baris, mobil bisa masuk lewat belakang dan keluar lewat depan

(b) Jika mobil yang berada paling depan yang akan dikeluarkan -> mobil bisa segera dikeluarkan

(c) Jika mobil yang akan dikeluarkan berada ditengah -> semua mobil didepannya harus dikeluarkan sementara dulu, setelah mobil yang dimaksud keluar ->maka mobil yang dikeluarkan sementara tadi akan masuk lagi dengan urutan tetap (push pop stack)

Hasil Run :Tampilan awal pilihan 1 memasukkan data plat nomer :

Tampilan pilihan 3 setelah memasukkan data plat nomer :

Tampilan pilihan 2 mengeluarkan mobil dari antrian :

Tampilan pilihan 4 :

3. Aplikasi program queue berprioritas dengan single linked list Pembahasan antrian di depan dinaggap semua elemen yang masuk

mempunyai prioritas yang sama, sementara dalam praktek yang digunakan adalah antrian berprioritas

Ketentuan antrian berprioritas :a. Elemen yang mempunyai prioritas lebih tinggi akan diproses lebih dulub. Dua elemen yang mempunyai prioritas yang sama akan dikerjakan sesuai

dengan urutan pada saat kedua elemen ini masuk dalam antrianc. Penerapan dengan single linked list, ketentuannya :o Setiap simpul terdiri dari 3 anggota, yaitu : informasi,angka prioritas,

dan bagian penyambung ke simpul lain .o Simpul X mendahului (terletak disebelah kiri) simpul Y, jika prioritas

X > prioritas Y atau bisa juga karena simpul X datang lebih dulu disbanding simpul Y .

Hasil Run :

1.2. Tugas Pemrograman

1. Untuk latihan program no 1,2 dan 3 buatlah bagan proses dari queue , untuk

setiap operasi enqueuing (insert) dan dequeuing (remove) pada representasi array

dan linked list. Jangan lupa memasukkan juga perubahan nilai index array dan

perubahan nilai pointernya .

2. Buatlah program simulasi penjadwalan cpu dengan queue berprioritas , parameter

yang dimasukkan :

Waktu kedatangan (arrival time)

Waktu proses

Nilai prioritas

Dapatkan total waktu yang dibutuhkan sampai selesai seluruh proses .