Queue (Antrean) Pertemuan 9

PERTEMUAN 9

QUEUE (ANTREAN)

A.      Pengertian QUEUE (ANTREAN)

Struktur Data Antrean (QUEUE) adalah suatu bentuk khusus dari list linier dengan operasi pemasukan data hanya diperbolehkan pada salah satu sisi,yang disebut sisi belakang/ekor (Tail) dan operasi pengahapusan hanya diperbolehkan pada sisi lainnya yang disebut sisi Depan/Kepala (Head) dari LinkedList.

Prinsip Antrean : FIFO (First In First Out)

                                : FCFS (First Come First Serve)

“yang tiba lebih awal maka akan dilayani terlebih dahulu”

B.      Deklarasi Queue

#define MAX 8

Typedef Struct {

                Int data [MAX];

                Int head;

                Int tail;

                } Queue;

Queue antrian;

    0         1        2         3          4        5          6         7        Max=8

         Head = -1

         Tail = -1

C.      Operasi Queue

·         CREATE

Untuk menciptakan dan menginisialisasi Queue dengan cara membuat Head dan Tail =-1

·         ISEMPTY

Untuk memeriksa apakah queue kosong

·         ISFULL

Untuk memeriksa apakah queue sudah penuh

·         ENQUEUE

Untuk menambahkan item pada posisi paling belakang

·         DEQUEUE

Untuk menghapus item dari posisi paling depan

·         CLEAR

Untuk mengosongkan Queue

D.      Fungsi Create

Digunakan untuk membentuk dan menunjukkan awal terbentuknya suatu Antrean/Queue

E.       Fungsi IsEmpty

·         Untuk memeriksa apakah Antrian penuh atau kosong

·         Dengan cara memeriksa nilai Tail,jika Tail=-1 maka Antrian kosong(Empty)

·         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

F.       Fungsi IsFull

Untuk mengecek apakah Antrian sudah penuh atau Belum ,dengan Cara;

·         Mengecek Nilai Tail

·         JIka tail=MAX-1 berarti antrian sudah penuh (MAX-1 adalah batas elemen Array dalam program C++)

Int isfull()

{

   If (antrian.tail==Max-1)

                Return 1;

   Else

                Return 0;

}

5

10

35

20

15

30

40

25

    0         1        2         3          4        5          6         7        Max=8

 Head=0

Tail=7

Antrian penuh karena Head=0 Tail=Max -1

G.     Fungsi Enqueue

·         Untuk menambahkan elemen pada antrian,penambahan elemen selalu dilakukan pada elemen paling belakang

·         Penambahan elemen selalu menggerakkan variable tail dengan cara menambahkan Tail terlebih dahulu

·          

4

45

1

8

    0         1        2         3          4        5          6         7        Max=8

Head=0

Tail=3

Enqueue (8)

H.      Fungsi Dequeue

·         Digunakan untuk menghapus elemen terdepan(head) dari antrian

·         Dengan cara ; menggeser semua elemen antrian kedepan dan mengurangi tail dengan 1.penggeseran dilakukan dengan menggunakan looping

I.        Fungsi Clear

·         Untuk menghapus elemen-elemen Antrian sebenarnya tidak menghapus arraynya ,namun hanya mengeset index pengaksesan-nya ke nilai-1 sehingga elemen-elemen Antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula

·         Untuk menghapus elemen-elemen Antrian dengan cara membuat tail dan Head= -1

PERTEMUAN 9 QUEUE (ANTREAN)

LATIHAN 1 STRUKTUR DATA
Berikan gambaran/ilustrasi dari kasus antrian berikut;a. Diketahui suatu Antrian/queue dengan max =6

5

20

3

9

                0                  1                       2                   3                   4                   5               MAX=6

b. Lakukan Enqueue 4 elemen ke dalam antrian,      dimanakah posisi Head dan Tail ?

5

20

3

9

                0                  1                      2                    3                   4                    5               MAX=6                          HEAD=0                                   TAIL=3                                                                                    ENQUEUE=8
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]);  }}

c.Kemudian lakukan Dequeue 2 elemen dari antrian.Maka dimana posisi Head dan Tail ?

 

5

20

3

9

                0                  1                      2                    3                   4                    5               MAX=6

              
                          HEAD=0                                   TAIL=3                                                                                    DEQUEUE()
int Dequeue(){            int i;            int e = antrian.data[antrian.head];            for(i=antrian.head;i<=antrian.tail-1; i++) {            }            Antrian.tail--;            Return e;}

1

8

                0                  1                      2                    3                    4                   5               MAX=6                          HEAD=0        TAIL=1                                                                                                          MAJU SEMUA TAIL --

d. Dari keadaan diatas, bagaimanakah kondisi IsFull dan     IsEmpty nya ?
    IsFull

4

45

1

8

10

7

                0                  1                      2                    3                   4                   5                     MAX=6                                       head=0              antrean penuh karena                                                                head=0                                                   tail=5                                                tail= max -1int IsFull(){    If(antrian.tail== Max-1)            Return 1;   else            return 0;}
 

IsEmpty           0                       1                    2                     3                  4                   5                MAX=6Head= -1                      antrean kosongTail= -1                                    karena tail= -1
int IsEmpty(){    If(antrian.tail== -1)            Return 1;   else            return 0;}