Antrian (Queue) • Susunan koleksi data dimana proses penambahan data (add) dilakukan dari belakang dan penghapusan data (delete) dilakukan dari depan. • Antrian bersifat FIFO (First In First Out) FIFO Æ Data yang pertama masuk ke dalam antrian menjadi data yang pertama keluar dari antrian. struktur data - antrian
1
Operasi Antrian Macam-macam operasi antrian: • EnQue: menambah data pada antrian (dari belakang, posisi tail,atau ekor) • DeQue: menghapus data pada antrian (dari depan, posisi head, atau kepala) • IsEmpty: menguji apakah antrian dalam keadaan kosong • IsFull: menguji apakah antrian dalam keadaan penuh • Print: menampilkan semua elemen (isi) antrian • Clear: mengosongkan atau menghapus semua elemen (isi) antrian struktur data - antrian
2
Implementasi antrian dengan struct Langkah-langkah... • Definisikan konstanta MAX_QUEUE untuk menyimpan nilai maksimum isi QUEUE • Definisikan queue menggunakan tipe data struct (struct queue) • Elemen struct queue adalah: int head, int tail, dan int data[MAX_QUEUE - 1] (head Æ mencatat posisi data paling depan tail Æ mencatat posisi data paling belakang data Æ mencatat isi antrian) • Definisikan variabel antrian (yang bertipe queue) struktur data - antrian
3
Deklarasi awal • Deklarasi MAX_QUEUE #define MAX_QUEUE 8
• Deklarasi QUEUE dengan tipe data struct typedef { int int int };
struct QUEUE head; tail; data[MAX_QUEUE - 1];
• Deklarasi antrian yang bertipe QUEUE QUEUE antrian; struktur data - antrian
4
Inisialisasi Inisialisasi Antrian • Inisialisasi isi head dan tail = -1 , berarti isi antrian masih kosong atau belum berisi data. (ingat indeks array dalam bahasa C dimulai dari 0) • head Æ variabel yang mencatat (menunjukkan) posisi paling depan antrian. • tail Æ variabel yang mencatat (menunjukkan) posisi paling belakang antrian dan sekaligus juga cacah data di dalam antrian. struktur data - antrian
5
Antrian pertama kali dibuat
Ilustrasi antrian pada awal dibuat, nilai antrian.head=antrian.tail= -1, antrian dalam kondisi kosong. struktur data - antrian
6
Antrian dalam keadaan kosong Ilustrasi antrian dalam keadaan kosong.
struktur data - antrian
7
Antrian dalam keadaan penuh Ilustrasi antrian dalam keadaan penuh.
struktur data - antrian
8
Fungsi IsEmpty dan IsFull Fungsi IsEmpty (memeriksa apakah Antrian masih kosong?) • Memeriksa antrian.tail, jika antrian.tail == -1, berarti antrian masih kosong
Fungsi IsFull (memeriksa apakah Antrian sudah penuh?) •
Memeriksa antrian.tail, jika antrian.tail == [MAX_QUEUE-1], berarti antrian sudah penuh
struktur data - antrian
9
Fungsi EnQueue Fungsi EnQueue • Menambah data pada antrian (dari belakang, posisi tail,atau ekor) Algoritma EnQueue • Apabila antrian belum terisi penuh, lakukan: – Jika antrian.tail == -1 (berarti akan menambah data ke dalam antrian dalam kondisi awal antrian tidak ada data) maka ubah nilai antrian.head=0 – Perbarui nilai antrian.tail, dengan menambah satu (increment) Æ antrian.tail = antrian.tail +1 atau antrian.tail ++ – Isikan data baru ke antrian • Apabila antrian telah terisi penuh, batalkan penambahan data, tampilkan pesan “antrian telah terisi penuh“
struktur data - antrian
10
Ilustrasi fungsi EnQueue
struktur data - antrian
11
Fungsi DeQueue Fungsi DeQueue • Untuk menghapus data pada antrian (dari depan, posisi head, atau kepala). Algoritma DeQueue • Apabila antrian tidak dalam keadaan kosong, lakukan: – Tampilkan data yang akan dihapus – Jika cacah data antrian >1, hapus data tersebut dengan cara melakukan proses “Refresh“. Proses “Refresh“ yaitu pindahkan semua isi antrian.data[ i+1 ] ke dalam antrian.data[ i ] dengan nilai i=0 sampai dengan antrian.tail-1. Perbarui nilai antrian.tail, dengan mengurangi satu (decrement) Æ antrian.tail=antrian.tail-1 atau antrian.tail-– Jika cacah data antrian =1, hapus data tersebut dengan cara mengubah nilai antrian.head = antrian.tail = -1 • Apabila antrian dalam keadaan kosong, batalkan penghapusan data, tampilkan pesan “antrian dalam keadaan kosong“ struktur data - antrian
12
Ilustrasi fungsi DeQueue
struktur data - antrian
13
Fungsi Print Fungsi Print • Untuk menampilkan semua elemen (isi) antrian. • Menggunakan proses perulangan, dimulai dari indeks array antrian.head sampai dengan antrian.tail. • Nilai antrian.head dan antrian.tail tidak diubah (karena hanya menampilkan isi antrian saja)
struktur data - antrian
14
Ilustrasi fungsi Print
struktur data - antrian
15
Fungsi Clear Fungsi Clear • Untuk mengosongkan atau menghapus semua elemen (isi) antrian • Cara1. Menggunakan proses DeQueue yang diulang sebanyak: antrian.tail+1 kali (jika perulangan dimulai dari indeks 1), atau antrian.tail kali (jika perulangan dimulai dari indeks 0) Perhatikan, perulangan bukan sebanyak MAX_QUEUE • atau Cara2. Mengubah nilai antrian.head = antrian.tail dengan -1 struktur data - antrian
16
Latihan Soal • • •
Buatlah fungsi untuk mencari suatu elemen dalam antrian Buatlah fungsi untuk mengedit suatu elemen dalam antrian Buatlah fungsi untuk mencari nilai total, nilai rata-rata, nilai terbesar, dan nilai terkecil, dari elemen antrian
struktur data - antrian
17
Sumber Referensi – James Roberge, Stefan Brandle, dan David Whittington, 2003, C++ Data Structures 2nd Edition, Jones and Bartlett Publishers, Inc., Sudbury, Massachusetts. – Antonius Rachmat Chrismanto – UKDW Yogyakarta. – P. Insap Santosa, 1992, Struktur Data Menggunakan Turbo Pascal 6.0, Penerbit Andi, Yogyakarta. – Berbagai sumber dari Internet. struktur data - antrian
18
