“tumpukan
(stack)”
§ Secara
sederhana di artikan dengan :
o
Sebagai tumpukan dari benda
o
Sekumpulan data yang diolah-olah
diletakkan di atas data yang lain
o
Koleksi dari objek-objek homogen
Dengan
melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (last
in first out) ,yaitu elemen yangterakhir masuk akan pertama kali diambil /
dilayani
”Ilustrasi stack”
Salah satu yang dapat dikemukakan
disini adalah tumpukan piring / barang lain. Pada saat kita hendak menumpuk
piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring
pertama pada tempatbya, selanjutnya meletakan piring kedua di atas piring
pertama dan demikian seterusnya. Pada saat kita hendak mengambil satu piring
dari tumpukan tersebut, tentu yang di ambil adalah piring teratas (yang
terakhir kali di taruh ) bukan yang bawah ( yang pertama kali diletakkan) .
“ Operasi Pada
Stack”
2
operasi dasar yang bisa dilaksanakan pada sebuah stack, yaitu :
o
Operasi
Push
(Menyisipkan Data) memasukkan data kedalam stack .
o
Operasi
Pop
( Menghapus Data) menghapus elemen-elemen yang terletak pada posisi paling atas dari sebuah stack.
“Dibawah Ini Contoh
Pemakaian Operasi Push Dan Pop Dan Isi Stack Untuk Setiap Selesai Eksekusi Satu
Operasi”
operasi yang dilakukan
|
isi stack
|
keterangan
|
Kondisi awal
|
Kosong
|
-
|
push (‘A’, S )
|
A
|
-
|
Push (‘B’, S )
|
AB
|
-
|
Push (‘C’, S )
|
ABC
|
-
|
Pop (
data, S )
|
AB
|
Mengambil data terisi ‘c’
|
Push (‘D’, S)
|
ABD
|
Mengambil data terisi ‘c’
|
Pop (
data, S )
|
AB
|
Data terisi ‘D’
|
Pop (
data, S )
|
A
|
Data terisi ‘B’
|
“Implementasi Stack
Dalam Bahasa Pemrograman “
Implementasi
dalam bahasa pascal dapat dilakukan dengan memanfaatkan struktur data record
dan array . array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan
selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang
ada di dalam array yang sekaligus menunjukkan TOS .
“Pada Implementasi
Dibawah Ini : “
§ Konstanta
maxelm menyatakan bahwa elemen maximum yang dapat di tampung oleh stack
§ Typeelemen
adalah tipe data yang akan disimpan di dalam stack (bisa
integar,word,real,boolean,char,string atau lainnya)
§ Banyak
adalah field yang menyatakan banyaknya elemen dalam stack saat itu , yang
sekaligus menyatakan TOS (Top Of The
Stack)
“ Deklarasi Tipe
Untuk Tumpukan (Stack) “
Type tumpukan = record
Banyak : 0 . . . . maxelm ;
Elemen : array [1 . . . . maxelm] of typeelemen;
End ;
“ Cont.”
§ Selain
prosedur untuk POP dan PUSH , kita dapat pula menambahkan sejumlah fungsi untuk
membantu penanganan kesalahan di antaranya adalah fungsi PENUHS (untuk mengecek
apakah stack penuh) fungsi kosongs (untuk mencetak apakah stack kosong) dan
fungsi sizes (untuk mengatur banyaknya elemen di dalam stack ) masing-masingg
sub program di atas dapat disajikan pseudocodenya sebagai berikut :
Ø Pseudocode
o
Procedure inisialisasi ( var S : tumpukan );
Begin
S banyaknya
– 0
End ;
o
Function Penuhs (S : tumpukan) ;
boolean ;
Begin
Jika S banyak =
maxelm maka PENUH S-true
Else PENUHS - False
End ;
Ø pseudocode
cont.
o Function KOSONGS(S : tumpukan):boolean;
begin
If S.banyak = 0 then KOSONGS -- true
else KOSONGS -- false
end;
o Procedure PUSH(data : tipelemen; var S :
tumpukan);
begin
If not KOSONGS(S) then
begin
S.banyak -- S.banyak
+ 1
S.elemen[S.banyak]-- data
end
else
Tampilan pesan kesalahan “Stack Penuh”
end;
o Procedure POP(var S : tumpukan; var data :
typeelemen);
begin
if not KOSONGS(S) then
begin
data -- S.elemen[S.banyak]
S.banyak -- S.banyak
-1
end
else
Tampilan pesan kesalahan “Stack Kosong”
End:
“Penjelasan Operasi Pada Stack”
1.
Buat stack (stack)-create
Membuat
sebuah stack baru yang masih kosong .
Spesifikasi
:
© Tujuan
: mendefinisikan stack yang
kosong
© Input : stack
© Syarat
awal : tidak ada
© Output
stack : - (kosong)
© Syarat
akhir : stack dalam keadaan kosong
2.
Stack kosong (stack)-empaty
Fungsi
untuk menentukan apakah stack dalam keadaan kosong/tidak.
Spesifikasi
:
© Tujuan
: mengecek apakah stack dalam
keadaan kosong
© Input : stack
© Syarat
awal : tidak ada
© Output
stack : boolean
© Syarat
akhir : stack kosong bernilai true jika
stack dalam keadaan kosong
3.
Stack penuh (stack)-full
Fungsi
untuk memeriksa apakah stack yang ada sudah penuh.
Spesifikasi
:
© Tujuan
: mengecek apakah stack dalam
keadaan penuh
© Input : stack
© Syarat
awal : tidak ada
© Output : boolean
© Syarat
akhir : stack penuh bernilai true jika
stack dalam keadaan penuh
4.
Push (stack , info baru)
Menambahkan
sebuah elemen ke dalam stack
Spesifikasi
:
© Tujuan
: menambahkan elemen ,info
baru pada stack pada posisi paling
atas
© Input : stack dan info baru
© Syarat
bawah : stack tidak pernah
© Output : stack
© Syarat
akhir : stack bertambah satu elemen
“Queue (antrian)”
§ Implementasi
dalam bahasa pascal dapat dilakukan dengan memanfaatkan struktur data record
dan array . array dipergunakan untuk menyimpan elemen-elemen yang di masukkan .
selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang
ada di dalam array.
§ Definisi
Queue adlah suatu linear lish dimana
operasi DELETE terjadi pada sisi depan (FRONT) dan
operasi INSERT terjadi pada sisi belakang ( REAR).
Jika diberikan suatu Queue Q dengan
elemen-elemennya yang terdiri atas Q1, Q2, . . . .,
QT maka queue Q dituliskan :
Q
= [ Q1, Q2, ...., QT ]
o FRONT (Q) = Q1
o REAR (Q) = QT
§ Selanjutnya
untuk menyatakan jumlah elemen dalam suatu . Queue Q digunakan notasi NOEL (Q)
. catatan : suatu pengoperasian berlaku banyak untuk satu elemen
§ Pada
queue prinsip yang digunakan adalah “ masuk pertama keluar pertama” atau FIFO (
first in first out)
Data-data
di dalam antrian dapat bertipe integer, real, record.
OPERASI-OPERASI
PADA QUEUE (Q)
§ Terdapat empat operasi dasar yang
didefinisikan pada queue, yaitu :
ü CREATE
ü ISEMPTY
ü INSERT
ü REMOVE
PENJELASAN
:
§ CREATE
Bentuk
umum :
CREATE (Queue)
Suatu operasi CREATE (Q) akan menghasilkan
suatu queue kosong dengan nama Q, dan didefinisikan bahwa :
NOEL
(CREATE (Q)) =
0
FRONT
(CREATE (Q)) =
tidak terdefinisi
REAR (CREATE
(Q)) =
tidak terdefinisi
§ ISEMPTY
Bentuk umumnya adalah : INEMPTY (queue)
Jika Q adalah Queue, maka ISEMPTY(Q)
adalah suatu operasi yang digunakan untuk memeriksa apakah Queue Q adalah queue
kosong. Jika hasil dari operasi ini akan berjenis data boolean
(true/false),dengan bentuk sebagai berikut :
ISEMPTY(Q) =
True, jika Q adalah queue kosong
=
False, jika Q bukan queue kosong
§ INSERT
Bentuk Umumnya : INSERT (Elemen, Queue)
INSERT(E,Q), dimana E = elemen dan Q =
queue, adalah suatu operasi yang digunakan untuk memasukkan elemen E ke dalam
queue Q.
Didefinisikan, bahwa elemen E akan menjadi
elemen yang berada pada posisi REAR dan queue Q. Akibat dari operasi ini adalah
:
v REAR(insert(E,Q)) = E
v NOEL(Q) bertambah satu dan QNOEL adalah
E
Jika Q adalah queue kosong , maka :
ISEMPTY(INSERT(E,Q))
= False
Dalam bentuk statemen Pascal, biasanya
dituliskan :
IF
ISEMPTY(Q) Then front (insert(E,Q)) = E
Else
front(insert(E,Q = front(Q);
§ REMOVE
Bentuk umum : REMOVE(elemen, queue)
REMOVE(Q) berarti mengeluarkan elemen Q
yang berada pada posisi FRONT. Akibat dari operasi ini, elemen Q akan berkurang
satu dan elemen kedua (elemen yang berada disebelahnya) akan menjadi elemen
yang berada pada posisi FRONT dari queue Q ini.
Selanjutnya, jika Q adalah queue kosong,
maka REMOVE(Q) akanmenghasilkan suatu Error.
IF
NOEL(Q) = 0 Then Remove(Q) = erroe_condition
Remove(create(Q))
= error_condition
DEKLARASI
QUEUE DALAM PASCAL
§ Dalam bahasa pemrograman biasanya tidak
ada fasilitas queue (built in queue). Untuk itu setiap programmer harus
mendefinisikan sendiri dengan bantuan fasilitas yang ada. Pada umumnya
fasilitas yang digunakan untuk mendeklarasikan queue adalah Array, Bentuk
deklarasinya dalam bahasa sebagai berikut :
TYPE
StrukQueue = Record
Q
: Array[1...100] of integer;
Front,
Rear : Integer;
End;
VAR
Q : StrukQueue;
§
No comments:
Post a Comment