Stack dan Queue pada bahasa pascal
1.
Array
Array atau disebut juga dengan larik adalah sebuah struktur data yang
terdiri atas banyak variable yang mempunyai tipe data sama. Tipe data disebut
elemen atau komponen array. Untuk mengoperasikan array ini digunakan pemilih
elemen array yang disebut index, yang
dapat berupa variable, konstanta ataupun ungkapan. Index diletakkan dalam tanda
kurung dan titik setelah nama array yang di operasikan.
2.
Stack ( Tumpukan )
Stack adalah kumpulan data dengan gambaran
seperti sebuah tumpukkan (misalnya tumpukkan piring, tumpukkan buku). Sifat
khusus yang dimiliki oleh stack ialah penambahan data selalu diletakkan pada
bagian atas dan pengambilan data selalu dilakukan pada data yang terletak di
atas tersebut. Data pada bagian atas stack disebut TOP . Dengan sifat tersebut maka aturan stack dikenal juga istilah LIFO (Last In First Out).
Berdasarkan sifat khusus stack, maka ada 2
operasi terhadap stack, yaitu pengambilan data dilakukan pada top, yang di
sebut sebagai POP dan penambahan
data dilakukan pada top, yang disebut sebagai PUSH.
Dengan menggunakan tipe data array,
stack di definisikan :
Const
NMAX = ....; {ukuran maksimum stack}
NULL = 0; {penunjuk stack kosong}
Type
tipedata
= ....; {tipe data yang disimpan dalam
stack}
Stack
= record
Tabelemen
: array[1 .. NMAX] of tipedata
Top
: NULL ... NMAX; {top dari stack}
End;
Tipe data dapat berupa
tipe data dasar, seperti integer, real, karakter atau string, juga dapat berupa
tipe data bentukan seperti record, set dan array.
Procedure Inisialisasi (var S : stack);
Begin
S.Top := Null;
End;
Procedure Push (var S : stack; data tipedata);
{IS : S adalah stack yang
belum penuh,data terdefinisi}
{FS : data menjadi elemen
top dari stack 8}
Begin
S.Top := S.Top + 1;
S.tebelemen[S.Top] :=
data;
End;
Procedure POP (var S : stack; var data :tipedata);
{IS : S adalah stack yang
tidak kosong}
{FS : elemen top dari
stack 8 dihapus dan disimpan didata}
Begin
Data := S.tabelemen[S.Top];
S.Top := S.Top – 1;
End;
Definisi prosedur PUSH seperti diatas hanya berlaku jika
stack S belum penuh, jika stack S sudah penuh tidak bisa lagi dilakukan
penambahan data. Penambahan data pada posisi dimana stack telah penuh disebut
stack Overflow. Untuk dengan memperhitungkan seleksi apabila stack S
sudah penuh.
Demikian juga untuk prosedur POP, hanya berlaku untuk
stack yang tidak kosong. Pengambilan data dimana stack telah kosong disebut Underflow.
Bila stack telah kosong maka tidak dapat dilakukan operasi POP.
Variasi lain untuk prosedur PUSH dan POP dengan
mempertimbangkan seleksi awal terhadap kondisi stack adalah seperti dibawah
ini:
Procedure Inisialisasi
(var S : stack);
Begin
S.Top := NULL;
End;
Function Empty (S :
stack): Boolean;
{mengirim nilai true jika
S adalah stack kosong}
Begin
Empty := (S.Top=NULL);
End;
Function Full (S :
stack):Boolean;
{mengirim nilai true juka
S sudah penuh)
Begin
Empty := (S.Top=NMAX);
End;
Procedure Push (var S : stack; data tipedata);
{IS : S adalah stack yang belum penuh,data terdefinisi}
{FS : data menjadi elemen top dari stack 8}
Begin
if Not Full (S) then
begin
S.Top := S.Top + 1;
S.tebelemen[S.Top] :=
data;
End;
End;
Procedure POP (var S : stack; var data :tipedata);
{IS : S adalah stack yang tidak kosong}
{FS : elemen top dari stack 8 dihapus dan disimpan didata}
Begin
if Not Empty (S) then
begin
data :=
S.tabelemen[S.Top];
S.Top := S.Top – 1;
End;
End;
Begin
if Not Empty (S) then
begin
data :=
S.tabelemen[S.Top];
S.Top := S.Top – 1;
End
Else
data:=..; {isi suatu
nilai yang kemungkinan bukan data}
end;
3.
Antrian ( Queue )
Antrian adalah kumpulan data dengan penanda pada elemen pertama dan
terakhir. Elemen pertama disebut sebagai Front
dan elemen terakhir disebut Rear.
Penambahan data dilakukan pada akhir elemen, sedangkan penghapusan data
dilakukan pada elemen pertama. Sifat antrian tersebut dikenal denga istilah FIFO (First In Forst Out).
Berdasarkan sifatnya, maka ada 2 operasi terhadap queue, yaitu
penambahan data pada elemen akhir queue, disebut Enqueue dan penghapusan data pada elemen pertama queue, disebut Dequeue.
Procedure Inisialisasi (var Q :
queue);
{IS : -}
{FS : Q didefinisikan sebagai queue kosong}
Begin
Q.front := NULL;
Q.rear := NULL;
End;
Function EmptyQ (Q : queue) :
Boolean;
{Mengirim nilai true jika q adalah queue kosong}
Begin
EmptyQ := ((Q.front=Null) and (Q.rear=Null));
End;
Procedure Enqueue (var Q : queue;
data : tipedata);
{IS : Q adalah queue yang belum penuh, data terdefinisi}
{FS : data menjadi elemen terakhir dari queue Q}
Begin
If EmptyQ
(Q) Then
Begin
Q.front := 1;
Q.rear :=
Q.rear+1;
Q.tabelemen[Q.rear] := data;
End;
End;
Procedure Dequeue (var Q: queue;
var data : tipedata);
{IS : queue Q adalah tidak kosong}
{FS : elemen pertama queue Q dihapus dan disimpan di data, queue Q mungkin
menjadi kosong}
Begin
data :=
Q.tabelemen[Q.front];
Q.front := Q.front + 1;
If(Q.front > Q.rear) Then {queue menjadi kosong}
Begin
Q.front := NULL;
Q.rear := NULL;
End;
End;
Apabila ingin diketahui
bahwa pada saat penambahan data apakah queue sudah penuh atau belum, maka perlu
diperhitungkan jumlah elemen data pada queue. Sebuah queue penuh jika Q.rear =
NMAX. Namun demikian tidak selamanya kondisi Q.rear = NMAX menunjukkan bahwa
queue telah penuh. Kondisi Q.rear = NMAX akan menunjukkan queue telah penuh
bila selama proses pengoperasian queue belum pernah ada data yang keluar
(Dequeue).
Bila telah pernah terjadi
operasi Dequeue maka akan terjadi pergeseran penanda front sebanyak data yang
telah keluar. Hal ini terjadi karena operasi Dequeue dengan array hanya
memindahkan index penanda front ke index yang diatasnya. Dalam hal ini
penghapusan elemen didepan mengakibatkan array pada index awal menjadi kosong
dan tidak terpakai. Jika hal ini terjadi maka perlu dilakukan konsolidasi
(setup ulang index front) dengan memindahkan semua data kebagian awal dari
tabel.
Untuk operasi Dequeue,
apabila dikehendaki pengecekan apakah queue dalam keadaan kosong atau tidak,
maka perlu ada perubahan terhadap prosedur Dequeue dan Enqueue. Dibawah ini
adalah prosedur baru Dequeue dan Enqueue :
Procedure Consolidate (var Q :
queue);
{IS : Q.rear = NMAX dan Q.front <>1}
{FS : Q.front = 1 dan Q.rear = banyaknya data}
Var
i, j : integer;
begin
j := 1;
for
i:=Q.front to Q.rear do
begin
Q.tabelemen[j]:=Q.tabelemen[i];
j:=j+1;
end;
Q.front := 1;
Q.rear := j;
End;
Procedure Enqueue (var Q : queue;
data : tipedata);
{IS : Q adalah queue, data terdefinisi}
{FS : data menjamin elemen terakhir queue Q jika Q belum penuh}
Begin
If EmptyQ(Q) Then
Q.front := 1;
If Q.rear
<> NMAX Then
Begin
Q.rear := Q.rear + 1;
Q.tabelemen[Q.rear] := data;
End
Else {ada kemungkinan Q penuh}
If Q.front <> 1 Then
Begin
Consolidate(Q);
Q.rear := Q.rear+1;
Q.tabelemen[Q.rear] := data;
End; {else terjadi overflow}
End;
Procedure Dequeue (var Q :queue;
var data : tipedata);
{IS : queue Q terdefinisi}
{FS : elemen pertama queue Q dihapus jika tidak kosong dan disimpan di
data, queue Q mungkin menjadi kosong}
Begin
If not Empty(Q) Then
Begin
data:=Q.tabelemen[Q.front];
Q.front:=Q.front+1;
If (Q.front>Q.rear)
Then {queue menjadi kosong}
Begin
Q.front:=NULL;
Q.rear:=NULL;
End;
Else {ada kemungkinan Q penuh}
Data :=...; {isi suatu nilai yang kemungkinan bukan
data}
0 komentar: