Pertemuan 6

PENGERTIAN QUEUE (ANTREAN)

Struktur Data Antrean (Queue) adalah suatu bentuk khusus dari List Linier dengan operasi penyisipan (Insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi Belakang (Rear) dan operasi penghapusan (Deletion) hanya diperbolehkan pada sisi lainnya yang disebut sisi Depan (Front) dari List.Prinsip Antrean : FIFO (First In First Out)

FCFS (First Come First Serve)

“Yang Tiba lebih awal Maka akan dilayani Terlebih Dahulu”

PENGERTIAN QUEUE (ANTREAN)

OPERASI DASAR PADA ANTREAN

Ada 4 operasi dasar yang dapat dilakukan pada Struktur Data Antrean, yaitu :1. CREATE(Antrean)2. ISEMPTY(Antrean)3. INSERT(Elemen,Antrean)4. REMOVE(Antrean)

Pandang misalnya Antrean Q = [ Q1 , Q2 , .., QNOEL ], maka

1. CREATE(Antrean)Adalah suatu operator untuk membentuk dan menunjukan suatu Antrean Hampa Q.Berarti : NOEL(CREATE(Q) = 0

FRONT(CREATE(Q)) = tidak terdefinisi REAR(CREATE(Q)) = tidak terdefinisi

2. ISEMPTY(Antrean)

Adalah operator yang menentukan apakah Antrean Q hampa atau tidak. Operand dari operator ini merupakan Antrean, sedangkan hasilnya merupakan Type data Boolean.ISEMPTY(Q)=True,jika Q hampa, yaitu jika NOEL(Q)=0False, jika Q tidak hampa, yaitu jika NOEL(Q) <> 0Maka ISEMPTY(CREATE(Q)) = True.

3. INSERT(Elemen,Antrean)

Operator yang menginsert (mengisi) elemen E kedalam Antrean Q. Elemen E ditempatkan dibagian depan dari Antrean. Hasil dari Operasi ini adalah Antrean yang lebih panjang.

REAR(INSERT(E,Q)) = EQNOEL Adalah E

ISEMPTY(INSERT(E,Q)) = False

4. REMOVE(Antrean) / DELETE(Antrean)

REMOVE(Q) adalah operator yang meghapus elemen bagian depan dari Antrean Q. Hasilnya merupakan Antrean yang lebih pendek. Pada setiap operasi ini, harga dari NOEL(Q) berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan. Jika NOEL(Q) = 0 , maka REMOVE(Q) memberikan suatu kondisi Error, yaitu Underflow. Jelas bahwa REMOVE(CREATE(Q)) juga memberikan kondisi Error Underflow.Langkah :- Memastikan bahwa antrean ada isinya.- Menggeser Front, maju satu langkah- Mengcopy isi elemen yang ditunjuk Front ke variabel data.

ANTREAN LINEARMenggunakan 2 pointer (indikator) :- Front (F) untuk awal antrean- Rear (R) untuk akhir antrean Untuk pengambilan data menggunakan pointer Front (F), sedangkan pemasukan data menggunakan pointer Rear (R).

Syarat : Front (selalu) <= Rear Deklarasi Array 1 dimensi untuk Queue :

Var Q : Array[1..N] of Type Data;

Beberapa keadaan pada Antrean Linear :

ANTREAN MELINGKAR (CIRCULAR QUEUE)Prinsip : FIFO (First In First Out)

Terlihat dari urutan proses diatas, nilai F dapat lebih kecil atau lebih besar dari R, dimana ini merupakan hal yang tidak dapat terjadi di antrean linear (linear queue) Oleh karena itu agar Antrean dapat digunakan secara Maximal harus diwujudkan dalam bentuk antrean melingkar (Circular Queue).

Latihan Soal Struktur Data (Pertemuan 6)

1. Empat jenis operasi dasar pada Queue adalah a. Create, Isempty, Insert, Remove b. Insert, Remove, Pop, Push c. Isempty, Insert, Remove, Push d. Create, Isempty, Insert, Pop

2. Syarat yang harus dipenuhi pada antrian linier (linier queue) adalah :a. F = R = N c. F > = R b. F = R d. F < = R

2. Syarat yang harus dipenuhi pada antrian linier (linier queue) adalah :a. F = R = N c. F > = R b. F = R d. F < = R

3. Suatu Antrean (Queue) digambarkan dengan Array [1..N] dengan pointer R (Rear), F(Front) dan jumlah elemen = N, keadaan Antrian dianggap “Kosong” jika :a. F=0, R=0 c. F=N, R=0b. F=0, R=N d. F=R=N

3. Suatu Antrean (Queue) digambarkan dengan Array [1..N] dengan pointer R (Rear), F(Front) dan jumlah elemen = N, keadaan Antrian dianggap “Kosong” jika :a. F=0, R=0 c. F=N, R=0b. F=0, R=N d. F=R=N

4. Dalam Antrean circular Kondisi untuk F (Front) dan R (Rear) yang terjadi adalah ……a. Nilai F selalu = R c. Nilai F tidak selalu <= R b. Nilai F selalu <= R d. Nilai F selalu >= R

4. Dalam Antrean circular Kondisi untuk F (Front) dan R (Rear) yang terjadi adalah ……a. Nilai F selalu = R c. Nilai F tidak selalu <= R b. Nilai F selalu <= R d. Nilai F selalu >= R

5. Perhatikan Antrean (Queue) berikut ini:

Front(Q) dari Antrean diatas adalah ……..a. A b. B c. C d. D

DCBA