LINEAR QUEUE

LINEAR QUEUE

QUEUE

(Queue) adalah suatu bentuk khusus dari List Linier dengan operasi penyisipan (Insertion) hanyadiperbolehkan pada salah satu sisi, yang disebut sisi Belakang (Rear) dan operasi penghapusan (Deletion) hanyadiperbolehkan pada sisi lainnya yang disebut sisi Depan(Front) dari List.

 

Prinsip Antrean : FIFO (First In First Out) atau FCFS (First Come First Serve)“Yang Tiba lebih awal Maka akan dilayani TerlebihDahulu”. Jika diartikan secara harafiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehiduypan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang dating terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue. Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :

·         EnQueue Memasukkan data ke dalam antrian

·         DeQueue Mengeluarkan data terdepan dari antrian

·         Clear Menghapus seluruh antrian

·         IsEmpty Memeriksa apakah antrian kosong

·         IsFull Memeriksa apakah antrian penuh

LINEAR QUEUE   Linear queue berarti adalah antrian lurus. Ilustrasi dari linear queue : Pada gambar di atas tampak 4 ekor singa berbaris antri. Ketika singa itu akan ,keluar dari kandang dengan dua sisi pintu, maka singa yang pertama masuk dari pintu belakang (singa A) akan keluar terlebih dahulu melalui pintu depan, sedangkan singa D masuk terakhir maka akan keluar terakhir pula. Front   = Depan Rear     = Belakang Ilustrasi linear queue menggunakan array satu dimensi. Pada saat A keluar maka B bergeser ke tempat A semula. Begitu pun seterusnya C menempati tempat B dan D menempati tempat C. Demikian seterusnya hingga hasilnya menjadi sebagai berikut.   Pergeseran dengan cara di atas membutuhkan waktu cukup lama karena, masing-masing elemen harus berpindah. Cara lain yang dapat ditempuh adalah dengan menggeser loket. Perhatikan urutan gambar ilustrasi berikut. Pada ilustrasi di atas antrian sudah kosong sehingga F > R atau F = R + 1. Lalu ketika semua antrian sudah dilayani maka keadaan perlu dikembalikan ke keadaan semula (di- Reset). Seperti contoh berikut : Sebelum direset : Setelah direset : Representasi Linear Queue dalam array satu dimensi.      PRINSIP / KONSEP PROSES Prinsip yang digunakan pada linear queue adalah FIFO (First In First Out) atau FIFS (First In First Serve). Maksudnya adalah data atau elemen yang pertama masuk akan menjadi elemen yang pertama keluar.   PROSES a.      AWAL (Inisialisasi) b.      INSERT (Isi, Sisip, Masuk, Simpan, Tulis) c.       DELETE ( Hapus, Keluar, Ambil atau Dilayani, Baca) d.      RESET (Kembali ke keadaan awal)   Algoritma dasar untuk proses awal (inisialisasi) dalam bahasa C : Ilustrasi hasil proses awal : F > R atau F = R + 1 berarti Antrian KOSONG Pada keadaan kosong seperti ilustrasi di atas maka proses yang dapat dilakukan hanya INSERT saja. Dalam struktur LINEAR QUEUE,  digunakan istilah : ·         INSERT  untuk : Simpan, atau Masuk, atau Isi atau Tulis. ·         DELETE  untuk : Ambil, atau Keluar, atau Baca, atau Hapus   Ilustrasi proses INSERT dan DELETE : Pada gambar di atas, 1.      Ketika ada perintah INSERT maka akan diisi di elemen nomor 7,        R menunjukkan nomor 7 dan F tetap di nomor 3. 2.      Ketika ada perintah DELETE maka yang akan diambil adalah isi di elemen         nomor 3, sedangkan R tetap menunjuk 6 dan F menunjuk 4. INSERT Algoritma dasar untuk INSERT R maju satu langkah (R=R+1) Isi di tempat yang ditunjuk oleh R à Q[R]=X Lanjutkan menggeser R dan mengisi X dengan b Terus dilanjutkan hingga seperti pada gambar berikut Algoritma dasar untuk INSERT pada antrian Q[ ] Algoritma yang benar adalah : R=R+1; Q[R]=X; Algoritma dasar untuk INSERT R = R + 1; Q[R] = X;   R+=1; Q[R] = X;   R++; Q[R] = X;   Q[++R] = X;     Dalam keadaan seperti ini akan di DELETE Lalu F bergeser maju satu langkah menjadi seperti gambar berikut : Selanjutnya hingga isi antrian tinggal 1 elemen Antrian kosong Antrian penuh Antrian penuh di atas dapat dikosongkan kembali menjadi sebagai berikut : Antrian di-RESET sehingga F= 0 dan R= -1 Algoritma dasar untuk DELETE pada antrian Q[ ] X = Q[F]; F = F + 1; X = Q[F]; F = F + 1;   X = Q[F]; F+=1;   X = Q[F]; F++;   X = Q[F++];       Kondisi antrian void INSERT(void) { if ( R == n-1 )       printf(“Antrian Penuh’);   else       {  R  =  R + 1;         Q[R] =  X;      }       }   Algoritma untuk proses DELETE void DELETE(void) {  if ( F  <  R+1 )      {  X = Q[F] ;         F  =  F + 1;         if ( F == n )            { F = 0;              R = -1; }     }    else    printf( “Antrian  Kosong”); }   Algoritma untuk proses DELETE dengan logika terbalik void DELETE(void) { if ( F == R+1 )    printf(“Antrian Kosong’);  else  { X = Q[R];          F  =  F + 1;          if ( F == n )            { F = 0;              R = 0; }    }       }   Contoh Program Linear Queue #include<stdio.h> #include<conio.h> #define n 10 char Q[n]; int F,R; void Insert(char X); void Delete(void); void Awal(void); void Reset(void); int main() {  int I;    char X, Y;    clrscr();    Awal();    -    scanf(“%i”, &X);    Insert(X);    -    -    Delete();    -    - }   void Awal(void)    { F = 0;      R = -1;  } void Insert( char X)   { if (R < n-1)         { R++;           Q[R] = X;  }      else         printf(“\nAntrian Penuh “);   } void Delete( void)   { char X;     if( F < R+1 )         { X = Q[F];           printf(“%c”, X);           F++;           if(F == n)              Reset( );      else printf(“Antrian Kosong”);   } void Reset(void)   { F = 0;     R = -1;  }