Queue Struktur Data Pascal

QUEUE
Queue atau antrian adalah suatu kumpulan data, dimana penambahan elemen hanya bisa
dilakukan di satu ujung (disebut sisi belakang atau rear) dan penghapusan (pengambilan)
elemen dilakukan melaui ujung yang lain (disebut sisi depan atau front)
Prinsip pada queue adalah FIFO (First In First Out), dengan kata lain:
urutan masuk elemen = urutan keluar elemen
Operasi – operasi Pada Queue
BuatQueue(Queue)
• Tujuan: mendefinisikan queue yang masih kosong
• Input: Queue
• Output: Queue dalam keadaan kosong
QueueKosong(Queue)
• Tujuan: mengecek apakah queue dalam keadaan kosong atau tidak
QueuePenuh(Queue)
• Tujuan: mengecek apakan queue dalam keadaan penuh atau tidak
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
Enqueue(Queue, InfoBaru)
• Tujuan: menambahkan elemen baru yang berisikan InfoBaru pada Queue pada
posisi paling belakang
• Input: Queue dan InfoBaru
• Syarat Awal: Queue tidak penuh
• Output: Queue
• Syarat akhir: Queue bertambah 1 elemen
Dequeue(Queue, InfoDequeue)
• Tujuan: mengeluarkan (mengambil) elemen Queue yang berada pada posisi paling
depan dan disimpan ke dalam InfoDequeue
• Input: Queue
• Syarat Awal: Queue tidak kosong
• Output: Queue dan InfoDequeue
• Syarat Akhir: Queue berkurang 1 elemen
Implementasi Queue dengan Menggunakan Array
Deklarasi
const Nmax = 100;
Type TipeInfo = integer;
TipeArray = array [1..NMax] of TipeInfo;
TipeQueue = record
Elemen: TipeArray;
Belakang: Integer;
end;
Var Queue: TipeQueue;
BuatQueue
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
procedure BuatQueue(var Queue: TipeQueue);
begin
Queue.Belakang := 0;
end;
QueueKosong
function QueueKosong(Queue: TipeQueue): Boolean;
begin
QueueKosong := (Queue.Belakang = 0);
end;
QueuePenuh
function QueuePenuh(Queue: TipeQueue): Boolean;
begin
QueuePenuh := (QueueBelakang = NMax)
end;
Enqueue
procedure Enqueue(var Queue: TipeQueue; IB: TipeInfo);
begin
if (not (QueuePenuh(Queue))) then
begin
Queue.Belakang := Queue.Belakang + 1;
Queue.elemen[Queue.Belakang] := IB;
end;
end;
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
Dequeue
procedure Dequeue(var Queue: TipeQueue; var InfoDeq: TipeInfo);
var i: integer;
begin
if (not (QueueKosong(Queue))) then
begin
InfoDeq := Queue.elemen[1];
for i:=1 to Queue.Belakang – 1 do
Queue.Elemen[i] := Queue.Elemen[i+1];
Queue.Belakang := Queue.Belakang - 1;
end;
end;
Latihan:
1. Buatlah sebuah program yang mengimplementasikan queue dengan array untuk
memasukkan dan menampilkan data berikut:
W R Q Y D T
2. Dari Program nomor 1, coba anda buat procedure untuk mengeluarkan karakter 'D'
Implementasi Queue dengan Menggunakan Array Melingkar
Deklarasi:
const Nmax = 100;
type
TipeInfo = char;
TipeArray = array [1..NMax] of TipeInfo;
TipeQueue = record
Elemen: TipeArray;
depan, belakang: Integer;
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
end;
var Queue: TipeQueue;
Procedure BuatQueue
procedure BuatQueue(var Queue: TipeQueue);
begin
Queue.depan := Nmax;
Queue.belakang := Nmax;
end;
Function QueueKosong
>> Jika depan dan belakang menunjuk ke tempat yang sama
function QueueKosong(Q: TipeQueue): boolean;
begin
QueueKosong := (Q.depan = Q.belakang);
end;
Function QueuePenuh
>> Jika penerus belakang adalah depan
function QueuePenuh(Q: TipeQueue): boolean;
var nextBelakang: Integer;
begin
if (Q.belakang = Nmax) then
nextBelakang := 1
else
nextBelakang := Q.belakang + 1;
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
QueuePenuh := (nextBelakang = Q.depan);
end;
Procedure Enqueue
• Geser Nilai Belakang (nilai depan tetap)
• Masukkan info baru (IB)
procedure Enqueue(var Queue: TipeQueue; IB: TipeInfo);
begin
if not(QueuePenuh(Queue)) then
begin
if Queue.belakang = Nmax then
Queue.belakang := 1
else
Queue.belakang := Queue.belakang + 1;
Queue.elemen[Queue.belakang] := IB;
end
end;
Procedure Dequeue
• Geser nilai depan (belakang tetap)
• Ambil elemen[depan], simpan dalam InfoDeq
procedure Dequeue(var Queue: TipeQueue; var InfoDeq: TipeInfo);
begin
if not(QueueKosong(Queue)) then
begin
if Queue.depan = Nmax then
Queue.depan := 1
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
else
Queue.depan := Queue.depan + 1;
InfoDeq := Queue.elemen[Queue.depan];
end;
end;
Latihan:
1. Buatlah sebuah program yang mengimplementasikan queue dengan array melingkar
untuk memasukkan dan menampilkan data berikut:
W R Q Y D T
2. Dari Program nomor 1, coba anda buat procedure untuk mengeluarkan karakter 'Y'
Implementasi Queue dengan Menggunakan Pointer
Deklarasi
Type TypeInfo = integer;
TypePtr = ^TypeNode;
TypeNode = record
Info: TypeInfo;
Next: TypePtr;
end;
TypeQueue = record
depan: TypePtr;
belakang: TypePtr;
end;
Var Queue: TypeQueue;
Procedure BuatQueue
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
procedure BuatQueue(var Queue: TypeQueue);
begin
new(Queue.depan);
new(Queue.belakang);
end;
Function QueueKosong
function QueueKosong(Queue: TypeQueue): Boolean;
begin
QueueKosong := (Queue.depan = nil);
end;
Procedure EnQueue
Algoritma:
• Buat node baru
• Isi node baru dengan infoBaru
• Next belakang menunjuk node baru
• Belakang menunjuk node baru
procedure Enqueue(Var Queue:TypeQueue; infoBaru: TypeInfo);
var nodeBaru: TypePtr;
begin
new(nodeBaru); nodeBaru^.Info := InfoBaru;
nodeBaru^.next := nil;
if QueueKosong(Queue) then
begin
Queue.depan := nodeBaru;
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
Queue.belakang := nodeBaru;
end
else
begin
Queue.belakang^.next := nodeBaru;
Queue.belakang := nodeBaru;
end;
end;
Procedure DeQueue
Algoritma:
• Ambil elemen/info paling depan
• Temp menunjuk node paling depan
• Depan menunjuk node beriktnya
• Hapus Temp
procedure Dequeue(Var Queue: TypeQueue; var InfoDeq: TypeInfo);
var Temp: TypePtr;
begin
InfoDeq := Queue.depan^.Info;
Temp := Queue.depan;
Queue.depan := Queue.depan^.next;
if Queue.depan = nil then
Queue.belakang := nil;
dispose(Temp);
end;
Praktikum Struktur Data
Laboratorium Komputer Dasar Ilmu Komputer
Universitas Gadjah Mada
Latihan:
1. Buatlah sebuah program yang mengimplementasikan queue dengan pointer untuk
memasukkan dan menampilkan data berikut:
W R Q Y D T
2. Dari Program nomor 1, coba anda buat procedure untuk mengeluarkan karakter '