Queue

Pengertian Queue (Antrian)

Struktur  data  linear  adalah  kumpulan  komponen-komponen  yang  tersusun membentuk satu garis linear. Bila komponen-komponenditambahkan (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 lewatujung yang lain (disebut dengan sisi depan atau front). DEQUEUEadalah mengeluarkan satu elemen dari suatu Antrian. Antrian dapat dibuat dengan menggunakan: Liniear Arraydan 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.  Aturan penyisipan dan penghapusan elemennya didefinisikan sebagai berikut:

• Penyisipan selalu dilakukan setelah elemen terakhir
• 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 :

• Antrian job yang harus ditangani oleh sistem operasi
• 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  countdigunakan 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-popdengan delete-first) dan bagian belakang adalah akhir dari list (dipush dengan  insert-last). Mengingat  operasi insert-last sering  dilakukan  maka digunakan dua variabel referensi  yang digunakan sebagai pointer:  frontuntuk node pertama dari list dan rearutuk node paling akhir.

Operasi-operasi pada Queue
1.  Membuat Queue Kosong
Untuk  menciptakan  dan  menginisialisasi  Queue,  dengan  cara  membuat  Head  dan Tail sama dengan 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  berubahubah. Pergerakan pada Antrian terjadi dengan penambahan elemen antrian kebelakang, yaitu menggunakan nilai Tail

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.

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.

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.

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

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

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

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 lakukanlah langkah 2.
2. Mulai hapus ←data[0] dan data[i-1] ←data[i]
3. i ←i – 1
4. data[0] ←NULL 

Manfaat Queue

• Digunakan sistem operasi untuk mengatur eksekusi taskdalam suatu sistem untuk mencapai perlakuan yang "adil" (seringkali queuedisebutwaiting line)
• Untuk mailboxdalam komunikasi antar proses
• Untuk bufferdalam mekanisme printspooler, komunikasi data
• Untuk simulasi dan modeling (misalnya simulasi sistem pengendali lalu lintas udara) dalam memprediksi performansi

Suatu Keinginan Dapat Terwujud

Bukanlah Karena Adanya Waktu Untuk Mewujudkannnya

Tetapi Karena Ada Keinginan Yang Sangat Kuat Untuk Mewujudkannya