STACK (TUMPUKAN)
Secara sederhana 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