queue
DESCRIPTION
QueueTRANSCRIPT
QueueSherly Christina, S.Kom., M.Kom
Definisi
• Secara harfiah berarti antrian. • sering kita temui dalam kehidupan sehari-hari,• misalnya pada saat mengantri di loket untuk
membeli tiket.
Representasi Antrian
Istilah-Istilah
• ENQUEUE : apabila seseorang masuk kedalam antrian atau terjadi penambahan data pada antrian.
• Dalam suatu antrian yang datang terlebih dahulu akan dilayani lebih dahulu (First In First Out)
• DEQUEUE:bila seseorang keluar dari antrian atau terjadi penghapusan data dari antrian
Operasi Pada Antrian (Memasukan elemen/Enqueue)• Memasukan elemen ke dalam antrian▫ Kondisi Awal: ada sebuah antrian▫ Buat Elemen baru yang akan dimasukkan
Operasi Pada Antrian (Memasukan elemen/Enqueue)• Elemen baru dimasukkan ke dalam queue
Operasi Pada Antrian (Memasukan elemen/Enqueue)• Penunjuk Last diubah menunjuk ke elemen baru
sebagai elemen paling terakhir
Operasi Pada Antrian (Mengeluarkan elemen/Dequeue)▫ Kondisi Awal: ada sebuah antrian
Operasi Pada Antrian (Mengeluarkan elemen/Dequeue)• Penunjuk First diubah menunjuk ke elemen
dibelakang elemen paling depang
Operasi Pada Antrian (Mengeluarkan elemen/Dequeue)• Elemen paling depan dikeluarkan dari antrian
Metode membuat antrian
1. Array ▫ Linier Array▫ Circular Array
2. linked list
Metode membuat antrian
1. Array Statis▫ Linier Array▫ Circular Array
2. Linked List Dinamis
Implementasi QUEUE dengan Linear ARRAY• Linier Array : suatu array yang dibuat seakan-
akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar.
• Antrian dapat mengalami kondisi penuh• Tempat pada array dapat tidak diisi elemen• Penanganan enqueue dan dequeue dengan
menggeser elemen
Definisi QUEUE dengan Linear ARRAY (Pascal)Const
MaxQueue = 6;Type
TypeQueue = byte;Var
Queue : Array [1..MaxQueue] of TypeQueue;Head, Tail : byte;
1. Create Queue Linear Array• Procedure Create:
menciptakan QUEUE yang baru dan kosong
• Cara: memberikan nilai awal (Head First) dan nilai akhir (Tail Last) dengan nol (0).
• Nol Queue (antrian) masih kosong.
Procedure Create;Begin
Head := 0; Tail := 0;End;
2.EmptyQueue Linear Array• Function Empty : mengecek
apakah Queue masih kosong atau sudah berisi data.
• Cara: mengecek apakah tail bernilai nol atau tidak, jika ya maka kosong.
Function Empy : Boolean;Begin
If (Tail = 0) thenEmpty := True
ElseEmpty := False;
End;
3.FullQueue Linear Array• Function Full : mengecek
apakah Queue sudah penuh atau masih bisa menampung data
• Cara: cek apakah tail sudah sama dengan jumlah maksimal queue, jika ya maka penuh.
Function Full : Boolean;Begin
If (Tail = MaxQueue) thenFull := True
ElseFull := False
End;
4.EnQueueQueue Linear Array• Procedure EnQueue:
memasukan 1 elemen ke dalam QUEUE.
Procedure EnQueue(Elemen : Byte);
BeginIf (Empty) thenBegin
Head := 1; Tail := 1;Queue[Head] := Elemen;
End Else
If (Not Empty) thenBegin
Inc (Tail);Queue(Tail) := Elemen;
End;End;
5. DequeuQueue Linear Array
• Procedure DeQueue berguna untuk mengambil 1 elemen dari QUEUE, operasi ini sering disebut juga SERVE.
• Cara: memindahkan semua elemen satu langkah ke posisi di depannya, sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak di belakangnya
Procedure DeQueue;Var
i : Byte;begin
if (Not Empty) thenBegin
For (i := Head) To (Tail-1) DoQueue[i] := Queue[i + 1];Dec(Tail);
End;End;
5. Clear Queue Linear Array• Procedure Clear: menghapus
semua elemen dalam QUEUE• Cara : mengeluarkan semua
elemen tersebut satu per satu sampai kosong dengan memanfaatkan procedure DeQueue
Procedure Clear;BeginWhile (Not Empty) Then
DeQueue;End;
Queue pada Circular Array• Circular array: suatu array yang dibuat seakan-akan merupakan sebuah lingkaran
• Dengan titik awal (Head) dan titik akhir (Tail) saling bersebelahan jika array tersebut masih kosong.
• Operasi pada circular array tidak berbeda jauh dengan operasi pada linear array.
QUEUE dengan DOUBLE LINKED LIST• Metode linked list yang digunakan
adalah double linked list. • Pada representasi dinamis,
penambahan elemen tetap dilakukan pada akhir queue.
• Pengambilan/penghapusan elemen tetap dilakukan pada awal queue
• Berikut penggalan type, konstanta dan variable yang akan digunakan dalam penjelasan operasi-operasi queue dengan linked list.
TypePoint = ^Simpul;Simpul = Record
Isi : TipeData;Next : Point;
End;Queue = Record
Head : Point;Tail : Point;
End;VarQ : Queue;N : 0..MaxQueue; { Jumlah Antrian}
1. CreateQUEUE DOUBLE LINKED LIST• untuk menciptakan QUEUE
yang baru dan kosong.• Cara:
mengarahkan pointer headdan tail kepada NIL.
Procedure Create;Begin
Q.Head := NIL; Q.Tail := Q.Head;
End;
2.EmptyQUEUE DOUBLE LINKED LIST • untuk mengecek apakah
QUEUE masih kosong atau sudah berisi data.
• Hal ini dilakukan dengan mengecek Head masih menunjuk pada nil atau tidak, jika ya maka kosong.
Function Empty:Boolean;Begin
If (Q.Head = NIL) thenEmpty := True
ElseEmpty := False;
End;
3.FullQUEUE DOUBLE LINKED LIST • untuk mengecek apakah
QUEUE sudah penuh atau masih bisa menampung data.
• Cara: dengan mengecek apakah N (Jumlah Queue) sudah sama dengan Max_Queue atau belum, jika ya maka penuh.
Function Full : Boolean;Begin
If (N = Max_Queue) thenFull := True
ElseFull := False;
End;
4.EnQueueQUEUE DOUBLE LINKED LIST• Untuk memasukan 1
elemen ke dalam QUEUE.
• Cara : (head dan tailmula-mula menunjuk ke NIL).
Procedure EnQueue (Elemen : TipeData);
VarNow : Point;
BeginIf (Not Full) thenBegin
New(Now);Now.^Isi := elemen;Now.^Next := NIL;
If (Empty) thenBegin
Q.Head := Now;Q.Tail := Now;N := 1;
4.EnQueueQUEUE DOUBLE LINKED LIST
End elseBegin
Q.Tail.^Next := Now;Q.Tail := Now;Inc(N);
End;End;
End;
5.DeQueueQUEUE DOUBLE LINKED LIST• untuk mengambil 1 elemen dari
QUEUE. • Cara: menghapus satu simpul
yang terletak paling depan (depan).
Procedure DeQueue;Var
Now : Point;Begin
If (Not Empty) thenBegin
Now := Q.Head;Q.Head := Q.Head^.Next;Dispose(Now);Dec(N);
End;End;