Queue (Antrian) PDF

 Antrian (Queue) dpt diartikan kumpulan data dengan penambahan data(elemen) hanya melalui satu sisi saja, yaitu belakang (tail) dan penghapusan data (elemen) hanya melalui sisi depan (head)  Hal ini membuat antrian bersifat FIFO (First In First Out), yaitu data masuk pertaman akan kel...

 Antrian (Queue) dpt diartikan kumpulan data dengan penambahan data(elemen) hanya melalui satu sisi saja, yaitu belakang (tail) dan penghapusan data (elemen) hanya melalui sisi depan (head)  Hal ini membuat antrian bersifat FIFO (First In First Out), yaitu data masuk pertaman akan keluar pertama dan yang terakhir akan keluar terakhir. A B C D E F  Elemen pertama kali masuk disebut elemen depan (front/head of queue), yg terakhir disebut elemen belakang (rear/tail of queue).  Antrian dapat dibuat baik dengan array maupun dengan struct.  Pada pembuatan antrian dengan array, antrian yang disajikan bersifat statis, karena jumlah maksimal array sudah ditentukan sejak deklarasi awal.  Contoh :  Penjualan karcis kereta, bioskop  Penjadualan pencetakan (spooling system)  Penjadualan pemakaian CPU  Pemakaian I/O pada sistem komputer  Penyimpan barang di Apotek 1. Membuat queue atau inisialisasi 2. Mengecek apakah queue penuh atau full 3. Mengecek apakah queue kosong atau empty 4. Memasukkan elemen ke dalam queue atau InQueue (insert Queue) 5. Menghapus elemen atau DeQueue (Delete Queue)  Implementasi Queue dengan Linear Array atau disebut model fisik (physical Model) yaitu bagian depan queue selalu menempati posisi pertama array Kosong 1 Elemen 4 Elemen Belakang Belakang D Belakang 0 1 4 C B Depan Depan Depan 0 A 1 A 1 Depan = 0 Belakang = 0 A B C D Depan = 1 Depan = 1 Belakang = 2 Belakang = 4 Depan = 1 Depan = 1 Belakang = 1 Belakang = 3  A B C D Ambil 1 elemen Geser antrian Depan = 1 Belakang = 3  B C D Ambil 1 elemen Geser antrian Depan = 1 Belakang = 2  C D Ambil 1 elemen Geser antrian Depan = 1 Belakang = 1  D Ambil 1 elemen Depan = 0 Belakang = 0 Kamus Data : Q : array [1..4] of Char Depan : Integer Belakang : Integer Q Belakang 0 Depan 0 //deklarasi queue menggunakan array # define MAX 50 # define true 1 # define false 0 Struct queue { int data[MAX]; int head; int tail; }; Struct queue antri;  Salahsatu algoritma untuk proses memasukkan data (PUSH) adalah sebagai berikut: 1. Masukkan inputan (x) 2. Jika variabel cek = max (Nilai maksimal array), kerjakan langkah 3 Jika tidak, kerjakan langkah 4. 3. Cetak “ANTRIAN PENUH” lalu selesai. 4. Selama cek kurang dari max, maka c  c +1 dan data [c]  x. Salah satu algoritma untuk proses mengeluarkan data (POP) adalah sebagai berikut: 1. Jika cek = 0, cetak “ANTRIAN KOSONG” kemudian selesai. Jika tidak, lakukan langkah 3. 2. mulai x=0, selama x kurang dari cek, lakukan langkah 3 dan 4. 3. data[x]  data [x+1]. 4. data[cek-1]  NULL. 5. cek  cek – 1 1. Fungsi init Digunakan utk menciptakan queue yg baru atau kosong, yaitu cara memberi nilai awal (head) dan nilai akhir(tail) dengan nol (0) void init (void) { antri.awal=0; antri.akhir=0; } 2.Fungsi Full  Untuk mengecek apakah queue sdh penuh atau blm.  jika nilai akhir (tail) = nilai max, maka fungsi akan mengembalikan nilai 1  jika tidak sama dengan maksimum, maka fungsi akan mengembalikan nilai 0 if full (void) { If (antri.akhir==MAX) return (true); Else return (false) } 3. Funsi Empty  Untuk mencek apakah queue masih kosong atau sudah berisi data  Dgn cara mencek nilai akhir (tail) bernilai nol atau tidak  Jika nilai akhir (tail) = 0, maka fungsi akan mengembalikan nilai 1  Jika tidak 0, maka funsi akan mengembalikan nila If Empty (void) { If (antri.akhir==0) return(true) Else return(false); } 4. Fungsi InQueue  Untuk memasukkan elemen ke dalam queue  Jika queue masih koson, maka nilai awal(head) dan nilai akhir(tail) diubah menjadi 1  Jika tidak kosong dan antrian belum penuh, maka nilai akhir (tail) akan ditambah 1(increment) Void inQueue (char elemen) { if (Empty()==true) { antri.awal=1; antri.akhir=1; antri.info[antri.awal]=elemen; } Else { If(full()!=true) { antri.akhir++ Antri.info[antri.akhir]=elemen; } Else printf(“Queue Overflow,,,\n”); } } 5. Fungsi DeQueue  Untuk mengambil elemen dari queue, dgn cara memindah suatu elemen satu langkah ke posisi depannnya, sehingga elemen yang paling depan tertimpa Char deQueue (void) { char isi; int i; if (empty()!=true) { isi=antri.info[antri.awal]; for (i=antri.awal;i= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh int IsFull ( ) { if(tail = = MAX-1) return 1; else return 0;} 4. Inqueue  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 //dengan array void Enqueue ( int data) { if(IsEmpty()= =1) { head=tail=0; data[tail]=data; printf(“%d masuk!”, data[tail])}; else if(IsFull() = = 0) { tail++; data[tail]=data; printf(“%d masuk!”, data[tail]);} }  Dequeue()  Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian  Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1  Penggeseran dilakukan dengan menggunakan looping int Dequeue( ){ int i; int e = data[head]; for (i=head;i