PERTEMUAN 3
Secara sederhana STACK diartikan dengan :
· Sebagai tumpukan dari benda
· Sekumpulan data yang seolah-olah diletakkan di atas data yang lain
· Koleksi dari objek-objek
Dengan
melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan
LIFO (First In Firs Out) yaitu elemen yang terakhir masuk akan pertama
kali diambil atau dilayani.
ILUSTRASI
STACK
Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau
barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah
yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selanjutnya
meletakkan piring kedua di atas piring pertama dan demikian seterusnya. Pada
saat kita akan mengambil satu piring maka yang diambil piring yang paling atas.
ILUSTRASI
STACK-CONT
OPERASI PADA
STACK
2 operasi dasar yang dapat dilaksanakan pada sebuah stack, yaitu :
ü Operasi Push (menyisipkan data) memasukkan
data ke dalam stack.
ü Opersi Pop (menghapus data) menghapus
elemen yang terletak pada posisi paling atas dari sebuah stack.
Contoh
pemakaian operasi pust 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
|
Data Berisi ‘C’
|
|
PUSH
(‘D’,S)
|
ABD
|
-
|
|
POP
(Data,S)
|
AB
|
Data Berisi ‘D’
|
|
POP
(Data,S)
|
A
|
Data Berisi ‘B’
|
IMPLEMENTASI
STACK DALAM BAHASA PEMOGRAMAN
· Implementasi dalam bahasa Pascal dapat dilakukan denagnmemanfaatkan
struktur data record dan array. Arraydipergunakan untuk menyimpan
elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk
mencatat banyaknya elemen yang ada di dalam array yang sekaligus menggunakan
IOS.
Pada
Implementasi di bawah Ini :
· Konstanta maxelm menyatakan banyaknya elemen maksimum yang
dapat ditampung oleh stack.
· Typeelemen adalah tipe
data yang akan disimpan di dalam stack (bisa integer, word, real, boolean,
char, string, atau lainnya). Banyak field yang menyatakan 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
diantaranya adalah fungsi PENUHS (untuk mengecek apakah stack
penuh) fungsi KOSONGS (untuk mengecek apakah stack kosong)
fungsi SIZES (untuk mengetahui banyaknya elemen di dalam
stack). Masing-masing sub program di atas dapat disajikan pseudocode-nya
sebagai berikut :
Ø PSEUDOCODE
o Procedure Inisialisasi(var S : tumpukan);
begin
S. banyak-0
end;
o Function PENUHS(S : tumpukan): boolean;
begin
Jika S.banyak = maxelm maka PENUHS - 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
v 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 aktif : stack dalam keadaan
kosong
v Stack kosong (stack) – empty
Fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak.
#Spesifikasi
§ Tujuan :
mengecek apakah stack dalam keadaan kosong
§ Input :
stack
§ Syarat awlal : tidak ada
§ Output : boolean
§ Syarat akhir : stack kosong bernilai true jika stack dalam keadaan
kosong.
v Stack penuh (stack) – full
Fungsi untuk memeriksa apakah stack yang ada sudah penuh.
#Spesifikasi
§ Tujuan :
mengecek apakah stack dalam keadaan penuh
§ Input :
stack
§ Syarat awlal : tidak ada
§ Output : boolean
§ Syarat akhir : stack kosong bernilai true jika stack dalam keadaan
penuh.
v 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 awlal : stack tidak penuh
§ Output : stack
§ Syarat akhir : stack bertambah satu elemen.
QUEUE (ANTRIAN)
DEFINISI
o 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 ]
· FRONT (Q) = Q1
· REAR (Q) = QT
o Selanjutnya untuk menyatakan jumlah elemen dalam suatu queue Q digunakan
notasi NOEL (Q).
o Catatan : Satu pengoperasian berlaku hanya untuk
satu elemen.
CONT.
o Pada queue prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama”
atau FIFO (Firs In Firs Out).
o Data-data di dalam antrian dapat bertipe integer, real, record
ILUSTRASI QUEUE
OPERASI-OPERASI PADA QUEUE (Q)
o Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu :
1. 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
2. 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
3. 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 :
- REAR(insert(E,Q))
= E
- 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);
4. 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;
Tidak ada komentar:
Posting Komentar