QUEUE (ANTREAN)

QUEUE (Antrian) adalah list linier yang :  dikenali elemen pertama (HEAD) dan elemen terakhirnya (TAIL),

aturan penyisipan dan penghapusan elemennya didefinisikan sebagai berikut:

     - Penyisipan selalu dilakukan setelah elemen terakhir

     - Penghapusan selalu dilakukan pada elemen pertama

satu elemen dengan yang lain dapat diakses melalui informasi NEXT Struktur data ini banyak dipakai dalam informatika, misalnya

untuk merepresentasi :

     - antrian job yang harus ditangani oleh sistem operasi

     - antrian dalam dunia nyata.

Maka secara lojik, sebuah QUEUE dapat digambarkan sebagai list linier yang setiap elemennya adalah type ElmtQ : < Info : InfoType, Next :address> dengan InfoType adalah sebuah type terdefinisi yang menentukan informasi yang disimpan pada setiap elemen queue, dan address adalah "alamat" dari elemen. Selain itu alamat elemen pertama (HEAD) dan elemen terakhir(TAIL) dicatat . Maka jika Q adalah Queue dan P adalah adaress, penulisan untuk Queue adalah :

Queue(Antrian).

DEFINISI FUNGSIONAL QUEUE:

Diberikan Q adalah QUEUE dengan elemen ElmtQ maka definisi fungsional antrian adalah:

IsEmpty: Q → boolean { Test terhadap Q: true jika  Q kosong, false jika Q tidak kosong}

IsFull : Q → boolean { Test terhadap Q: true jika memori Q sudah penuh, false jika memori Q tidak penuh}

NBElmt(Q) : Q → integer { Mengirimkan banyaknya elemen Q }

CreateEmpty : → Q {Membuat sebuah antrian kosong }

Add :ElmtQ x Q → Q { Menambahkankan sebuah elemen setelah elemen ekor QUEUE }

Del : Q →Q x ElmtQ { Menghapus kepala QUEUE, } { mungkin Queue menjadi kosong}

Implementasi QUEUE dengan tabel :

Memori tempat penyimpan elemen adalah sebuah tabel dengan indeks 1.. IdxMax. IdxMax dapat juga “dipetakan” ke kapasitas Queue. Representasi field Next: Jika i adalah “address” sebuah elemen, maka suksesor i adalah Next dari elemen Queue.

Perhatikan ilustrasi berikut :

Deklarasi

constant NMax : integer = 100

constant Nil      : integer = 0

type infotype    = integer

type Queue      = <TabQ: array[1..NMax] of infotype;

Head,Tail: integer>

Function EmptyQ(Q:Queue) → boolean

{True jika Q antrian kosong}

Procedure CreateEmpty(output Q:Queue)

{I.Q. – F.Q. Terdefinisi antrian kosong Q}

function IsFullQ(Q:Queue) → boolean {True Q penuh}

algoritma

→ (Q.Head = 1) and (Q.Tail=NMax)

Procedure AddQ (input/output Q:Queue; input X:infotype)

{I.Q. Q antrian, terdefinisi, mungkin kosong}

{F.Q. X elemen terakhir Q jika antrian tidak penuh}

Kamus:

i:integer

Function ISFull()

Algoritma

    if IsFull(Q) then

        output(‘Antrian penuh’)

else

        if Empty(Q) then

Q.Head ← 1

Q.Tail ← 1

        else

if Q.Tail<NMax then

      Q.Tail ← Q.Tail + 1

           else

{***}

{***}

for i←Q.Head to Q.Tail do

Q.TabQ[i-Q.Head+1] ← Q.TabQ[i]

Q.Tail ← Q.Tail-Q.Head+2

Q.Head ← 1

{end if}

{end if}

           Q.TabQ[Q.Tail] ← X {menyisipkan X}

{end if}