Queue (Antrean)

            Kali ini saya akan berbagi informasi yang terkait dengan antrean (queue). Struktur data antrean atau queue adalah suatu bentuk khusus dari linier list, dengan operasi penyisipan hanya diperbolehkan pada salah satu sisi, yang disebut REAR, dan operasi penghapusan hanya diperbolehkan pada sisi depan (FRONT) dari list.

            Notasi NOEL(Q) digunakan untuk menyatakan jumlah elemen di dalam antrean Q. NOEL(Q) mempunyai harga integer. Operator penyisipan disebut INSERT dan operator penghapusan disebut REMOVE. Untuk lebih jelasnya, silahkan dicoba contoh program antrean berikut ini. (Program ini menggunakan bahasa pascal),

program queue;

uses crt;

const max = 10;

type antri = array [1..max] of char;

var

   antrian : antri;

   q : antri;

   d : char;

   isi : antri;

   m, depan, belakang,jumlah,pilih : integer;

   elemen : char;

procedure kotak;

var

i: integer;

begin

     gotoxy(20,15);

     for i:= 1 to m * 4 + 1 do

         write('-');

     gotoxy(20,16);

     write('|  ');

     for i:= 1 to m - 1 do

         write(' |  ');

     writeln(' |');

     gotoxy(20,17);

     for i:= 1 to m * 4 + 1 do

         write('-');

     gotoxy(8,16);writeln('Keluar <---');

     gotoxy(22 + m * 4 + 1,16);

     writeln('<--- Masuk');

end;

procedure letakkan(x: char; r:integer);

begin

     gotoxy(18+4*r,16);

     write(x);

end;

procedure tambah(var antrian: antri;x:char);

begin

     if (((depan = 1) and (belakang = m)) or (depan = belakang+1)) then

     begin

          gotoxy (40,9);

          write ('OVERFLOW ERROR');

          readln;

          exit;

     end;

     if depan = 0 then

     begin

          depan := 1;

     end;

     if belakang = m then

     belakang := 1

     else belakang := belakang + 1;

     jumlah := jumlah + 1;

     antrian[belakang]:=x;

     letakkan(x,belakang);

     gotoxy (20,19);

     write('Front=', antrian[depan], ',' , depan );

     write('  Rear=',elemen, ',' , belakang);

     write('  Jumlah=',jumlah);

end;

procedure tampil(q: antri);

var i,awal : integer;

begin

     clrscr;

     writeln('Queue');

     if depan = m then awal :=1

     else awal := depan +1;

     for i:=awal to belakang do

     writeln(i:3,' ':5,isi[i],' ');

     readln;

end;

function hapus(var antrian: antri):char;

var hapusdata : char;

begin

     hapusdata := ' ';

     if depan = 0 then

     begin

     writeln('UNDERFLOW ERROR');

     exit;

     end;

     letakkan(hapusdata,depan);

     hapus:=antrian[depan];

     if depan = belakang then

     depan := 0

     else if depan = m then

     depan := 1

     else depan := depan +1;

     jumlah := jumlah-1;

     gotoxy (20,19);

     write('Front=',antrian[depan],',', depan);

     if depan=0 then

     write('  Rear= 0,0')

     else

     write('  Rear=',elemen,',',belakang);

     writeln('  Jumlah=',jumlah);

end;

{program utama}

begin

     clrscr;

     write('Berapa banyak inputan yang diinginkan (max 10) : ');

     readln(m);

     clrscr;

     kotak;

     depan:=0;

     belakang:=0;

     repeat

           for pilih:=5 to 9 do

           begin

                gotoxy(40,pilih);write(' ':39);

           end;

           gotoxy(1,1);

           writeln;

           writeln(' Pilihan ');

           writeln('===================');

           writeln(' 1. Tambah Data');

           writeln(' 2. Hapus Data ');

           writeln(' 3. Selesai dan Keluar');

           writeln;writeln;

           writeln(' Pilihan Anda:');

           repeat

                 gotoxy(22,9);writeln(' ');

                 gotoxy(22,9);readln(pilih);

           until (pilih>=1) and(pilih<=3);

           case pilih of

           1 : begin

             gotoxy(40,4);

             writeln ('--------------');

             gotoxy(40,5);

             writeln ('Masukkan Data');

             gotoxy(40,6);

             writeln ('--------------');

             gotoxy(40,8);

             write('Input Karakter:');

             readln(elemen);

             tambah(antrian,elemen);

             end;

           2 : hapus(antrian)

             end;

             until pilih = 3

end.

Tampilan output program akan seperti ini :

·         Operasi dasar pada antrean

o   CREATE(nama antrean) : Operator untuk membuat/menunjuk antrean hampa.

o   ISEMPTY(nama antrean) : Operator yang menentukan apakah antrean Q hampa atau tidak.

o   INSERT (elemen, antrean) : Operator untuk penyisipan.

o   REMOVE(nama antrean) : Operator untuk penghapusan.

Antrean mempunyai sifat FIFO(first in-first out), maksudnya data/elemen yang masuk pertama kali ke dalam antrean, maka data/elemen itulah yang akan terhapus pertama kali, ketika dilakukan operasi REMOVE.

Sumber :

      Suryadi, D.2005."Pengantar Struktur Data". Depok : Gunadarma.