Queue (Antrian)

Posted by ByLa in Mar 31, 2011, under educations

BAB I

PENDAHULUAN

1.1. Latar Belakang Masalah

Queue/antrian adalah ordered list dengan penyisipan di satu ujung, sedang penghapusan di ujung lain. Ujung penyisipan biasa disebut rear/tail, sedang ujung penghapusa disebut front/head. Fenomena yang muncul adalah elemen yang lebih dulu disisipkan akan juga lebih dulu diambil. Queue berdisiplin FIFO (First In, First Out). Queue merupakan kasus khusus ordered list. Dengan karakteristik terbatas itu maka kita dapat melakukan optimasi representasi ADT Queue untuk memperoleh kerja paling optimal.

Karakteristik Queue memang terbatas, tetapi Queue merupakan kakas dasar penyelesaian masalah-masalah besar, seperti simulasi fenomena antrian di dunia nyata, serta fenomena antrian di pengolahan data. Beberapa fenomena dunia nyata berupa antrian diantaranya : antrian pembelian tiket di depan oket untuk bis, kereta api, bioskop; antrian mobil di depan gerbang jalan tol; antrian kendaraan di jalanan umum; dll.

Representasi Queue dapat dilakukan dengan dua cara, yaitu:

  1. Representasi Sekuen
  • Representasi Sekuen linear
  • Representasi Sekuen Melingkar
  1. Representasi Dinamis

Pembahasan Representasi sekuen menggunakan array pada setiap pengoprasiannya, sedangkan Representasi dinamis  biasanya menempati memori berupa Record keduanya dideklarasikan menggunakan bahasa pemograman pascal.

1.2.Judul Makalah

Laporan makalah ini berjudul “Queue (Antrian)”, laporan ini diharapkan dapat menjadi literatur bagi proses belajar mengajar dalam perkuliahan, terutama mata kuliah Struktur Data khususnya bagi mahasiswa/i secara cepat dan mudah dalam memahami konsep antrian yang sesungguhnya.

BAB II

PEMBAHASAN

2.1. DESKRIPSI QUEUE

Queue/antrian adalah ordered list dengan penyisipan di satu ujung, sedang penghapusan di ujung lain. Ujung penyisipan biasa disebut rear/tail, sedang ujung penghapusa disebut front/head. Fenomena yang muncul adalah elemen yang lebih dulu disisipkan akan juga lebih dulu diambil. Queue berdisiplin FIFO (First In, First Out). Queue merupakan kasus khusus ordered list. Dengan karakteristik terbatas itu maka kita dapat melakukan optimasi representasi ADT Queue untuk memperoleh kerja paling optimal.

Misalnya Queue Q= (a1,a2,a3…,an), maka

  1. Elemen a1 adalah elemen paling depan
  2. Elemen ai adalah diatas elemen ai-1, di mana 1<i<n.
  3. Elemen an adalah elemen paling belakang

Head (atau front) menunjuk ke awal antrian Q (atau elemen terdepan), sedangkan tail ( rear) menunjuk akhir antrian Q (atau elemen paling belakang).

Disiplin FIFO pada Queue berimplikasi jika elemen A, B, C, D, E dimasukkan ke Queue, maka penghapusan/pengambilan elemen akan terjadi dengan urutan A, B, C, D, E.

2.2 Karakteristik Queue

Karakteristik penting antrian sebagai berikut :

  1. Elemen antrian yaitu item-item data yang terdapat di elemen antrian.
  2. Head/front (elemen terdepan dari antrian ).
  3. Tail/rear (elemen terakhir dari antrian ).
  4. Jumlah elemen pada antrian (count).
    1. Status/kondisi antrian.

Kondisi antrian yang menjadi perhatian adalah :

Penuh

Bila elemen di antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen menyebabkan kondisi kesalahan Overflow.

Kosong

Bila tidak ada elemen di antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

2.3 Operasi-Operasi Pokok di Queue

Operasi-operasi pokok antrian sebagai berikut :

  1. createQueue (Q), atau constructor menciptakan antrian kosong Q.
  2. addQueue (Q, X) memasukkan elemen X sebagai elemen akhir di Q.
  3. removeQueue (Q, X)atau mengambil elemen depan di antrian Q ke elemenX.

Operasi-operasi pengaksesan tambahan yang dapat dilakukan adalah :

  1. headQueue (Q), atau Front (Q, X) mengirim elemen terdepan tanpa menghapus.
  2. tailQueue (Q), mengirim elemen tanpa menghapusnya.

Operasi-0perasi Query tambahan yang dapat dilakukan adalah :

  1. isEmptyQueue (Q), mengirim apakah antrian Q adalah kosong.
  2. isFullQueue (Q), mengirim apakah antrian Q adalah penuh bila kapasitas antrian Q didefinisikan.
  3. isOverflowQueue (Q), mengirim apakah antrian Q telah mengalami overflow.
  4. isUnderflowQueue (Q), mengirim apakah antrian Q mengalami underflow.

Operasi-operasi terhadap seluruh antrian Q antara lain adalah :

  1. sizeQueue (Q), mengetahui jumlah elemen di antrian Q.
  2. isEqualQueue (Q1, Q2), mengirim apakah antrian Q1 dan Q2 sama isinya.

Jumlah operasi pokok Queue tidak banyak. Dengan demikian, sangat sederhana untuk menyatakan apa pun mengenai implementasinya.

2.4. Pengunaan Queue

Meski Queue sangat sederhana, namun Queue merupakan kakas dasar penyelesaian masalah-masalah besar. penggunaan Queue yang utama adalah untuk simulasi fenomena antrian di dunia nyata, serta fenomena antrian di pengolahan data.

Penggunaan :

  1. Simulasi antrian di dunia nyata, antara lain :
  • Lalu lintas pesawat udara tinggal landas (take-off) dan pendaratan (landing).
  • Antrian pembelian tiket di depan oket untuk bis, kereta api, bioskop.
  • Antrian mobil di depan gerbang jalan tol.
  • Antrian kendaraan di jalanan umum.
  • 2. System produksi
  • Barisan bahan atau komponen yang akan diproses suatu mesin.
  • Barisan bahan atau komponen yang akan diproses suatu manusia
  1. 3. System komputer
  • Pemrosesan banyak job (tugas) pada system multiprogramming.
  1. 4. System jaringan komputer
  • Pemrosesan banyak paket yang dating dari banyak koneksi pada suatu host, bridge, gateway dll.

2.5. Representasi Queue

Representasi Queue dapat dilakukan dengan dua cara, yaitu :

  1. Representasi sekuen
  • Representasi sekuen linear
  • Representasi sekuen melingkar merupakan implementasi statik yang lebih baik disbanding sekuen linear.
  1. 2. Representasi Dinamis (linked list).

2.6. Representasi Sekuen

Representasi queue secara sekuen lebih sulit disbanding stack. Untuk array satu dimensi QElemen [1:n], memerlukan variable front dan rear. Representasi sekuen linear tidak pernah digunakan karena representasi sekuen melingkar lebih baik dan juga sederhana. Pembahasan representasi sekuen linear berikut hanya digunakan untuk pembanding.

2.6.1.  Representasi Sekuen Linear

Kondisi berikut akan berlaku :

Front = rear jika dan hanya jika tidak terdapat elemen.

Kondisi awal adalah front = rear = o.

Front dan tail selalu bergerak maju/naik sehingga

  1. Bila tail telah mencapai elemen terakhir array, antrian dianggap penuh walau sebenarnya mungkin elemen-elemen awal antrian telah dihapus (dikosongkan).
  2. Bila front dan tail mencapai nilai yang sama berarti antrian dalam keadaan kosong maka front dan tail dapat diinisialisasikan kembali ke kondisi semula.

Kelemahan  Representasi Linear

Kapasitas penuh yang disediakan dapat terpakai seluruhnya yaitu bila telah terjadi penghapusan elmen-elemen antrian awal.

2.6.2.  Representasi Melingkar

Representasi queue lebih efisien dengan menganggap array QElemen [1;n] sebagai cirkular, mendeklarasikan array QElemen sebagai  QElemen [0:n-1]. Ketika rear = n-1, elemen dimasukkan ke QElemen [0] bila lokasi itu telah dikosongkan.

Konvensi

Front selalu menunjuk satu posisi setelah elemen pertama di queue searah jarum jam.

  1. Variable front = rear, jika dan hanya jika queue kosong.
  2. Awalnya front = rear = 1.

Asumsi sirkular adalah dengan mengubah algritma AddQ dan DeleteQ. Untuk penambah elemen, algoritma perlu memindahkan rear satu posisi searah jarum jam, yaitu:

if tail = n-1 then tail := 0 else tail := tail * 1

Efek sirkular  dengan rear := (rear+1) mod n. operator modulo yang menghitung sisa bagi. Serupa itu, perlu pemindahan front satu posisi searah jarum jam tiap terjadi penghapusan. Penghapusan dapat dilakukkan dengan front := (front +1) mod n. algoritma dapat dilakukan dengan waktu tetap atau 0 (1).

Front dan Tail Selalu Bergerak Maju/Naik

  1. Untuk penambahan

Bila tail telah mencapai elemen terakhir array, akan memakai elemen pertama array yang telah tidak digunakan (dihapus/dikeluarkan).

  1. Untuk penghapusan

Bila front telah mencapai elemen terakhir array, maka akan menuju elemen pertama bila antrian masih berisi elemen.

2.7. Representasi Linked List

Deklarasi queue menggunakan singly linked list sebagai berikut:

BAHASA PASCAL

Type

TData = . . . ;

TKey = . . . ;

PNode = ^Node ;

Node = record

Key : Tkey ;

Data : TData ;

Next : PNode ;

end ;

Queue = record

count : integer ;

front,            {sama dengan first}

tail : PNode ;    {sama dengan last}

end ;

Kita menyimpan count untuk menyimpan jumlah elemen di queue karena menghitung jumlah elemen di linked list adalah dengan menelusuri seluruh elemen. Penelusuran banyak memakan waktu. Kalau tidak ada keperluan mengetahui jumlah elemen di queue, maka count dapat dihilangkan.

Operasi- operasi di Queue

  1. CreateQ (Q) menciptakan Q dengan queue kosong.
  2. AddQ (Q, x) menambah elemen x ke rear queue.
  3. RemoveQ (Q, x) menghilangkan elemen pada front dari queue Q.
  4. FrontQ (Q) mengirim elemen front dari queue Q.
  5. IsEmptyQ (Q) yang mengembalikan true if Q kosong else false.
  6. SizeQ (Q) mengirimkan jumlah elemen pada queue;

Operasi- operasi tersebut diimplementasikan sebagai berikut:

2.8.  Dequeue

Representasi dequeue;

  1. Repsentasi Sekuen
  2. Repsentasi Linked List

Operasi- operasi pada dequeue antara lain:

  1. InitDQ, menciptakan dequeue kosong.
  2. InsertDQ, menyisipkan ekemen ke dequeue terdiri dari:
  • Menyisipkan ke ujung kiri
  • Menyisipkan ke ujung kanan
  1. RemoveDQ, mengambil elemen dari  dequeue terdiri dari:
  • Menghilangkan elemen di ujung kiri
  • Menghilangkan elemen di ujung kanan
  1. LeftDQ, mengrim elemen di ujung kiri.
  2. RightDQ, mengrim elemen di ujung kanan.
  3. IsEmptyDQ, mengirim true jika dequeue kosong.
  4. SizeDQ, mengir im jumlah elemen di dequeue.

2.9.  Representasi Sekuen Dequue

Deklarasi dalam pascal adalah:

BAHASA PASCAL

Const

N  = . . . ;

Type

Terror  =  (NoError , Overflow, Underflow, NotAvailable) ;

Tdata  = . . . ;

Deque = record

DQElemen  :  array[0 . . (N – 1)] of TData ;

Count ,

Left ,

Right  :  integer ;

ErrorCode  :  Terror ;

End;

2.10.   Representasi Linked List Dequeue

Deque

  • AddLeftDQ dilakukan dengan InsertFirst
  • RemoveLeftDQ dilakukan dengan DeleteFirst
  • AddRightDQ dilakukan dengan InsertLast
  • RemoveRightDQ dilakukan dengan DeleteLast

9 Responses

  • 徵信社

    I think youve got something great here. But what if you shed a couple links to a site that backs up what youre saying? Or maybe you could give us something to look at, I could revisit & read more sometime soon.3

  • JerryWriteman

    Great information as for me. Thank you a lot for providing this information.

    Jerry Writeman
    jamming cell phone

  • koawkeoawko

    Queue (Antrian) | Nabilla Canun Pretty nice post. I just stumbled upon your weblog and wished to say that I have really enjoyed surfing around your blog posts. After all I will be subscribing to your rss feed and I hope you write again very soon!

  • kasor

    Queue (Antrian) | Nabilla Canun Very nice post. I just stumbled upon your blog and wished to say that I’ve really enjoyed browsing your blog posts. In any case I’ll be subscribing to your feed and I hope you write again soon!

  • untue

    Excellent post at Queue (Antrian) | Nabilla Canun. I was checking constantly this blog and I’m impressed! Very helpful information specifically the last part :) I care for such info much. I was seeking this certain information for a very long time. Thank you and best of luck.

  • kasor

    Queue (Antrian) | Nabilla Canun Pretty nice post. I just stumbled upon your blog and wished to say that I’ve really enjoyed surfing around your blog posts. In any case I will be subscribing to your feed and I hope you write again very soon!

  • Manual Desselle

    on . May 16th, 2011 at . 2:24 pm

  • fkawau

    This is the straight Queue (Antrian) | Nabilla Canun journal for anyone who wants to assay out out some this issue. You respond so overmuch its most effortful to converse with you (not that I really would want…HaHa). You definitely put a new revolve on a topic thats been shorthand around for eld. Precise sundries, only great!

  • gjawua

    Queue (Antrian) | Nabilla Canun I was recommended this web site by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my trouble. You’re incredible! Thanks! your article about Queue (Antrian) | Nabilla CanunBest Regards Cassetta

Leave a Reply