Queue

Queue

 Pengertian Queue

Queue atau 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).

Kalau tumpukan dikenal dengan menggunakan prinsip LIFO (Last In First Out), maka pada antrian prinsip yang digunakan adalah FIFO (First In First Out). Hal ini berarti elemen pertama yang ditempatkan pada queue adalah yang pertama dipindahkan.

Contoh yang paling populer untuk membayangkan sebuah queue adalah antrian pada kasir sebuah bank.  Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setelah pelanggan dilayani, antrian yang berada di depan akan maju. Pada saat menempatkan elemen pada ujung (tail) dari queue disebut dengan  enqueue, pada saat memindahkan elemen dari kepala (head) sebuah queue disebut dengan  dequeue.

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; }

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; }

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]);

}

}

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;

}

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()

{

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