1

BAB 5 QUEUE (ANTRIAN)

1. Tujuan Instruksional Umum a. Mahasiswa mampu melakukan perancangan aplikasi menggunakan struktur

Queue (antrian) b. Mahasiswa mampu melakukan analisis pada algoritma Queue yang dibuat c. Mahasiswa mampu mengimplementasikan algoritma Queue pada sebuah

aplikasi secara tepat dan efisien 2. Tujuan Instruksional Khusus

a. Mahasiswa mampu menjelaskan mengenai Queue dan Dequeue b. Mahasiswa mampu membuat dan mendeklarasikan Abstraksi Tipe Data Queue c. Mahasiswa mampu menerapkan operasi push dan pop elemen pada algoritma

Queue Pengertian Queue (Antrian) Struktur data linear adalah kumpulan komponen-komponen yang tersusun membentuk satu garis linear. Bila komponen-komponen ditambahkan (atau dikurangi), maka struktur-struktur tersebut berkembang (atau menyusut). Queue merupakan struktur data linear dimana penambahan komponen dilakukan di satu ujung, sementara pengurangan dilakukan di ujung lain (yang satu lagi).

Queue (Antrian) adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut dengan sisi depan atau front). DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian. Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular Array. Kalau tumpukan menggunakan prinsip LIFO (Last Input First Output), maka pada antrian prinsip yang digunakan adalah FIFO (First Input First Output). Antrian banyak dijumpai dalam kehidupan sehari-hari, misalnya dalam menonton bioskop dimana melakukan antri dalam membeli tiket, mobil-mobil yang antri membeli karcis di pintu jalan tol akan membentuk antrian, para calon mahasiswa yang mendaftarkan diri untuk ikut ujian masuk perguruan tinggi akan membentuk antrian dan contoh-contoh lain yang banyak dijumpai dalam kehidupan sehari-hari. Contoh lain yang lebih relevan dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu (time-sharing computer system) dimana ada sejumlah pemakai yang menggunakan sistem tersebut secara serempak. Karena sistem ini biasanya menggunakan sebuah prosesor dan sebuah memori utama, maka jika prosesor sedang dipakai oleh seorang pemakai, pemakai-pemakai yang lain harus antri sampai gilirannya tiba. Antrian ini mungkin tidak dilayani secara FIFO murni, tetapi didasarkan fase tertentu. Antrian yang mengandung unsur prioritas dinamakan dengan antrian berprioritas (priority queue). QUEUE DENGAN LINIEAR ARRAY

Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya. Sehingga membutuhkan variabel Head dan Tail dengan aturan sebagai berikut:

1. Elemen pertama (HEAD) dan elemen terakhirnya (TAIL),

2

2. Aturan penyisipan dan penghapusan elemennya didefinisikan sebagai berikut: a. Penyisipan selalu dilakukan setelah elemen terakhir b. Penghapusan selalu dilakukan pada elemen pertama

3. Satu elemen dengan yang lain dapat diakses melalui informasi NEXT 4. Struktur data ini banyak dipakai dalam informatika, misalnya untuk

merepresentasi : a. antrian job yang harus ditangani oleh sistem operasi b. antrian dalam dunia nyata.

Abstraksi Tipe Data Queue

Seperti halnya stack (tumpukan) spesifikasi queue (antrian) tersebutb dapat diimplementasikan di level yang lebih rendah baik dengan array ataupun linear linked list. Dalam implementasi array, konsep circular-array dapat diaplikasikan untuk menghindari operasi penggeseran isi array saat dilakukan pop(). Dalam konsep circular array, inkrementasi indeks array yang panjangnya n, selalu di modulo dengan panjang array tsb. sehingga variabel indeks yang semula berharga n-1 jika diinkremen akan "wrap-around" ke 0. Untuk mengetahui posisi ujung-ujung dari item data yang disimpan dalam array, digunakan variabel indeks front (menunjuk ke posisi item yang akan diambil berikutnya) dan rear (posisi elemen array berikutnya yang akan ditempati). Suatu variabel count digunakan untuk mengetahui kasus khusus: apakah queue kosong atau penuh. Jika penuh maka mekanisme memperbesar kapasitas queue dapat diaplikasikan.

Dalam implementasi struktur data linier, maka bagian muka dari queue adalah awal dari list (di-pop dengan delete-first) dan bagian belakang adalah akhir dari list (di-push dengan insert-last). Mengingat operasi insert-last sering dilakukan maka digunakan dua variabel referensi yang digunakan sebagai pointer: front untuk node pertama dari list dan rear utuk node paling akhir. Deklarasi Abatraksi Tipe Data Queue Deklarasi Abstraksi tipe Data Queue #define MAX 8 typedef struct { int data[MAX]; int head; int tail; } Queue; Queue antrian;

Gambar 1. Linier Array Queue

Operasi-operasi pada Queue 1. Membuat Queue Kosong

Untuk menciptakan dan menginisialisasi Queue, dengan cara membuat Head dan Tail sama dengan NULL. Deklarasi Membuat Queue void Create() { antrian.head= NULL; antrian.tail= NULL; }

Gambar 2. Membuat Queue Kosong

3

2. Memeriksa Queue elemen kosong

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 Deklarasi Queue kosong

int IsEmpty() {

if(antrian.tail==NULL) return 1;

else return 0;

}

3. Memeriksa Queue elemen penuh Untuk mengecek apakah Antrian 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. Deklarasi Queue Penuh int IsFull() { if(antrian.tail==MAX-1) return 1; else return 0; }

Gambar 3. Queue Penuh

4. Menambah elemen Queue (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. Gambar 4 memperlihatkan penambahan elemen queue. Deklarasi Enqueue

void Enqueue(int data) {

if(IsEmpty()==1) {

antrian.head=antrian.tail=0; antrian.data[antrian.tail]=data; printf("%d masuk!",antrian.data[antrian.tail]);

} else if(IsFull()==0) { antrian.tail++; antrian.data[antrian.tail]=data; printf("%d masuk!",antrian.data[antrian.tail]); }

}

4

Gambar 4. Enqueue Data

5. Menghapus elemen Queue (Dequeue)

Digunakan untuk menghapus elemen terdepan/pertama dari antrian dengan cara mengurangi counter Tail dan menggeser semua elemen antrian kedepan. Penggeseran dilakukan dengan menggunakan looping. Gambar 5 memperlihatkan penghapusan elemen queue. Deklarasi Dequeue

int Dequeue() {

int i; int e = antrian.data[antrian.head]; for(i=antrian.head;i<=antrian.tail-1;i++) {

antrian.data[i] = antrian.data[i+1]; } antrian.tail--; return e;

}

Gambar 5. Dequeue Data

6. Membersihkan indeks Queue

Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head sama dengan NULL. Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai NULL sehingga elemen-elemen Antrian tidak lagi terbaca. Deklarasi Clear Queue

void Clear()

5

{ antrian.head=antrian.tail=NULL; printf("data clear");

}

7. Menampilkan elemen Queue

Untuk menampilkan nilai-nilai elemen antrian dengan menggunakan looping dari head sampai dengan tail. Deklarasi menampilkan elemen Queue

void Tampil() {

if(IsEmpty()==0) {

for(int i=antrian.head;i<=antrian.tail;i++) {

printf("%d ",antrian.data[i]); }

} else

printf("data kosong!\n"); }

8. PUSH elemen Queue

Salah satu algoritma untuk proses memasukkan data (PUSH) adalah sebagai berikut: 1. Masukkan inputan data 2. Jika variabel i = MAX (nilai maksimum array), maka kerjakan langkah 3. Jika i

≠ MAX, maka kerjakan langkah 4. 3. Tampilkan “Queue sudah penuh”. 4. Selama i < MAX, maka i = i + 1 dan data [i] = data

Deklarasi PUSH elemen Queue

If(i == MAX) Printf(“\nQueue sudah penuh\n\n”); Else { printf(“Masukkan data : “); scanf(“%d”, &data[i]); i = i + 1;

}

9. POP elemen Queue

Salah satu algoritma untuk proses mengeluarkan data (POP) adalah sebagai berikut: 1. Jika i = 0, maka tampilkan “Queue kosong” lalu kerjakan langkah 4. Jika i ≠ 0,

maka lakukan langkah 2. 2. Mulai hapus ← data[0] dan data[i-1] ← data[i] 3. i ← i – 1 4. data[0] ← NULL

Deklarasi POP elemen Queue If(i == 0) Printf(“Queue kosong”); Else

{ hapus = data[0]; for(int j = 0; j < = i; j ++)

{

6

data[j] = antrian.data[j+1]; data[i]=NULL; i--; }

}

Manfaat Queue

a. digunakan sistem operasi untuk mengatur eksekusi task dalam suatu sistem untuk mencapai perlakuan yang "adil" (seringkali queue disebut waiting line)

b. untuk mailbox dalam komunikasi antar proses c. untuk buffer dalam mekanisme printspooler, komunikasi data d. untuk simulasi dan modeling (misalnya simulasi sistem pengendali lalu lintas

udara) dalam memprediksi performansi Contoh Soal

Buatlah program dalam bentuk menu untuk mengimplementasikan antrian. Menu tersebut berisi memasukkan data, menghapus data, menampilkan data, dan keluar #include<stdio.h> #include<conio.h> void main() { int i=0, data[8], x, hapus; char pil; do { printf("1. Tambah Antrian\n"); printf("2. Hapus Antrian\n"); printf("3. Lihat Antrian\n"); printf("4. Keluar\n"); printf("Silahkan masukkan pilihan anda... "); pil=getche(); if(pil!='1' && pil !='2' && pil !='3' && pil!='4' ) printf("\n\nAnda salah mengetikkan inputan...\n"); else { if(pil=='1') //PUSH { if(cek==20) printf("\nQueue Penuh\n\n"); else { printf("\nMasukkan data: );scanf("%i",&x); data[i]=x; i++; } } else { if(pil=='2') //POP { if(i==0) printf("\nQueue kosong\n\n"); else { hapus=data[0]; for(int j=0;j<i;j++) data[j]=data[j+1]; data[i-1]=NULL; i--; printf("\nNilai = %i terhapus.",hapus); }

7

getch(); } else { if(pil=='3') //CEK DATA { if(i==0) printf("\nQueue Kosong.\n\n"); else { printf("\n"); for(int z=0;z<cek;z++) { printf(" | "); printf("%i",data[z]); printf(" | "); } } getch(); } } } } }while(pil!='4'); }

Soal Carilah nilai total, rata-rata, terbesar dan terkecil dari elemen queue dengan menggunakan fungsi di atas

Daftar Pustaka

1. _____. Struktur Data dengan Bahasa C. Team PPTI Universitas Kristen satya Wacana

2. Andri Kristanto. 2003. Struktur Data dengan C++. Yogyakarta: Graha Ilmu 3. Antonius Rachmat C. Handout Struktur Data. Prodi Teknik Informatika

Universitas Kristen Duta Wacana 4. Santoso, P. I. 1992. Struktur data Turbo Pascal 6.0. Yogyakarta: Penerbit Andi

Offset 5. Setiawan, S. dan Wibowo, A.M. Handout Struktur Data dan Algoritma.

Fakultas Ilmu Komputer Universitas Indonesia 6. Titi. Handout Struktur data. Teknik Informatika Institut Teknologi Bandung