stack
1.1
LINEAR LIST
Linear List adalah suatu
struktur data yang merupakan himpunan terurut. Misal didefinisikan suatu linear list A yang terdiri atas T buah
elemen sebagai berikut :
A
= [a1, a2, ..........,
aT]
Jika T = 0, maka A dikatakan sebagai “Null List”.
Suatu elemen dari sembarang posisi pada linear list A dapat dihilangkan.
Sebaliknya, suatu elemen baru dapat dimasukkan ke dalam list dan dapat
menempati sembarang posisi pada list tersebut. Jadi suatu linear list dapat
berkurang atau bertambah setiap saat.
1.2
DEFINISI STACK
Stack adalah suatu
bentuk khusus dari linear list di mana operasi penyisipan dan penghapusan atas
elemen-elemennya hanya dapat dilakukan pada satu sisi saja yang disebut sebagai
“TOP”.
Misal diberikan Stack S sebagai berikut :
Untuk menunjukkan jumlah
elemen suatu stack digunakan notasi NOEL.
Dari stack di atas, maka NOEL(S) = T.
Selanjutnya, jika diberikan sebuah stack S = [A,B,C,D], maka stack S ini dapat
digambarkan sebagai berikut :
1.3
OPERASI DASAR PADA STACK
Ada empat operasi dasar yang
didefinisikan pada stack, yaitu :
1. &nbrp;
CREATE(stack)
2.
ISEMPTY(stack)
3.
PUSH(elemen,stack)
4.
POP(stack)
1.3.1
CREATE
Operator ini berfungsi untuk membuat sebuah stack kosong
dan didefinisikan bahwa :
NOEL(CREATE(S))
= 0 dan TOP(CREATE(S)) = null
1.3.2
ISEMPTY
Operator ini berfungsi untuk menentukan apakah suatu
stack adalah stack kosong. Operasinya akan bernilai boolean, dengan definisi
sebagai berikut :
ISEMPTY(S) = true, jika S adalah stack
kosong
 :
= false, jika S bukan stack kosong
atau
ISEMPTY(S) = true, jika NOEL(S) = 0
= false, jika NOEL(S) 0
Catatan : ISEMPTY(CREATE(S))
= true.
1.3.3
PUSH
Operator ini berfungsi untuk menambahkan
satu elemen ke dalam stack. Notasi yang digunakan adalah :
PUSH(E,S)
Artinya : menambahkan elemen E ke dalam stack S.
Elemen yang baru masuk ini akan menempati posisi
TOP.
Jadi
: TOP(PUSH(E,S)) = E.
Akibat dari operasi ini jumlah elemen dalam stack akan
bertambah, artinya NOEL(S) menjadi lebih besar atau stack menjadi tidak kosong
(ISEMPTY(PUSH(E,S)) = false).
1.3.4
POP
Operator ini berfungsi untuk
mengeluarkan satu elemen dari dalam stack. Notasinya :
POP(S)
Elemen yang keluar dari dalam stack adalah
elemen yang berada pada posisi TOP. Akibat dari operasi ini jumlah elemen stack
akan berkurang atau NOEL(S) berkurang dan elemen pada posisi TOP akan berubah.
Operator POP ini tidak dapat digunakan pada stack kosong, artinya :
POP(CREATE(S)) = error condition
Catatan
: TOP(PUSH(E,S))
= E
1.4
DEKLARASI STACK PADA BAHASA PEMROGRAMAN
Dalam bahasa pemrograman,
untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal
yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen.
Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100
elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus
dideklarasikan pula variabel lain yaitu TOP_PTR yang merupakan indeks dari
array. Variabel TOP_PTR ini digunakan untuk menyatakan elemen yang berada pada
posisi TOP dalam stack tersebut. Selanjutnya gabungan kedua variabel ini diberi
nama STACK_STRUCT. Kemudian didefinisikan bahwa :
NOEL(S) = TOP_PTR
ISEMPTY(S) = TRUE, jika TOP_PTR = 0 dan
FALSE, jika TOP_PTR > 0.
Maka bentuk deklarasinya dalam PASCAL
adalah :
TYPE Stack_Struct = Record
Stack : array[1..100] of integer;
TopPtr : integer;
End;
VAR S : Stack_Struct;
Selanjutnya, untuk keperluan operasi PUSH dan POP harus dibuat suatu
prosedur tersendiri, yaitu :
PROCEDURE PUSH(Eon : integer);
Begin
If (S.TopPtr < NoelMax) Then Begin
S.TopPtr
:= S.TopPtr + 1;
S.Stack
[S.TopPtr] := Eon
End
Else
Overflow_Condition
End;
PROCEDURE POP(Eoff : integer);
Begin
If (S.TopPtr > 0) Then Begin
Eoff :=
S.Stack[S.TopPtr];
S.TopPtr
:= S.TopPtr - 1
End
Else
Underflow_Condition
End;
Catatan :
Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH terhadap
stack dalam keadaan penuh. Underflow
adalah keadaan di mana kita melakukan operasi POP terhadap stack kosong. Eon adalah elemen yang akan dimasukkan
ke dalam stack dan Eoff adalah
elemen yang akan dikeluarkan dari dalam stack.
1.5
PENGGUNAAN/ APLIKASI STACK
Logika stack digunakan untuk menyelesaikan berbagai
macam masalah. Antara lain digunakan pada compiler,
operating system dan dalam
program-program aplikasi. Berikut ini tiga buah contoh aplikasi stack, yaitu :
1.5.1
MATCHING
PARENTHESES
Proses ini dilakukan compiler untuk memeriksa
kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan
stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan
adalah :
- Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan.
- Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push ke dalam stack.
- Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.
·
Jika stack kosong terjadi kesalahan. berarti : ada simbol ")",
tetapi
tidak ada simbol "(" yang seharusnya mendahului.
·
Jika
stack tidak kosong artinya ada pasangannya dan langsung
di-POP keluar stack.
Misalkan NEXT CHAR adalah suatu karakter
terakhir dalam suatu string. Berikut ini bentuk flowchart (logika proses) yang
digunakan pada proses matching ini :
1.5.2
NOTASI POSTFIX
Bentuk aplikasi stack yang lain adalah mengubah suatu
ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini
digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa
tingkat tinggi (high level language). Stack digunakan oleh compiler untuk
mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam
bentuk/notasi postfix.
Contoh :
Misal diberikan ekspresi aritmatik : A + B
;
Maka bentuknya dalam notasi postfix
menjadi : AB+
Urutan (prioritas) dari operator adalah :
1. Perpangkatan (^)
2. Perkalian (*) atau Pembagian (/)
3. Penjumlahan (+) atau Pengurangan (-)
Aturan yang digunakan dalam proses
transformasi tersebut adalah :
1. Ekspresi aritmatik yang diberikan di-
"Scan" dari kiri ke kanan.
2. Bila simbol yang di-scan adalah
"(", maka simbol tersebut di push ke dalam stack.
- Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "(" yang pertama ditemukan dalam stack.
- Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack.
a. Jika derajatnya setara atau lebih rendah
dari simbol yang berada pada posisi top, maka top stack di-pop keluar sebagai
output dan simbol yang baru di-push ke dalam stack.
b. Jika derajatnya lebih tinggi dari simbol
yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut
di-push ke dalam stack.
- Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output.
- Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.
Contoh :
Misal diberikan sebuah ekspresi aritmatik dengan
bentuk sbb:
(
(A + B) * C / D + E ^ F ) / G ;
Selanjutnya akan dicari bentuk ekspresi diatas
dalam notasi postfix.
Proses yang dilakukan dapat digambarkan dalam tabel
berikut :
Urutan
Proses
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
Simbol
Yang di
Scan
|
(
|
(
|
A
|
+
|
B
|
)
|
*
|
C
|
/
|
D
|
+
|
E
|
^
|
F
|
)
|
/
|
G
|
;
|
Top
|
(
|
(
|
(
|
+
|
+
|
(
|
*
|
*
|
/
|
/
|
+
|
+
|
^
|
^
|
/
|
/
|
||
(
|
(
|
(
|
(
|
(
|
(
|
(
|
(
|
(
|
(
|
+
|
+
|
|||||||
(
|
(
|
(
|
(
|
|||||||||||||||
Output
|
A
|
B
|
+
|
C
|
*
|
D
|
/
|
E
|
F
|
^+
|
G
|
/
|
Jadi ekspresi aritmatik : ( ( A + B ) * C / D + E^F ) / G ;
dalam notasi postfix menjadi :
AB+D*C/EF^+G/
1.5.3
PROSES REKURSIF
Stack juga dapat
digunakan untuk menelurusuri suatu program atau procedure yang rekursif. Berikut ini sebuh contoh yang
menyelesaikannya menggunakan proses rekursif.
Persoalan
:
Agar
diperoleh uang sebanyak 1.000.000 rupiah pada 25 tahun yang akan datang, berapakah banyak uang yang harus
didepositokan saat ini? dianggap bahwa tingkat bunga tidak berubah selama 25 tahun
yaitu sebesar 8% per/tahun.
Penyelesaian :
Untuk menyelesaikan masalah ini akan digunakan
logika stack yaitu :
-
pada tahun ke-25 jumlah uang = Rp. 1.000.000,-
-
pada tahun ke-24 jumlah uang = Rp. 1.000.000 / (1 + 0.8)
-
pada tahun ke-23 jumlah uang
=
.
dst
Berikut
ini sebuah program PASCAL yang mengandung suatu procedure rekursif untuk
menghitung jumlah uang diinginkan.
PROGRAM DEPOSITO ;
CONST Goal = 1000000;
Rate =
0.08;
VAR Ju : Real;
Thn: Integer;
PROCEDURE Hitung (VAR Thn :
Integer);
BEGIN
IF (Thn > 0) THEN
BEGIN
Ju
:= Ju/(1.0 + Rate);
Thn
:= Thn - 1;
Hitung(Thn);
END;
END;
BEGIN
Thn := 25;
Ju := Goal;
HITUNG(Thn);
WRITE(Ju);
END.
Pemanggilan pertama
procedure HITUNG dimana nilai Thn =25
Pemanggilan kedua
procedure HITUNG dimana nilai Thn = 24
Pemanggilan ketiga procedure HITUNG, dimana nilai
Thn = 23
Setelah 25 kali pemanggilan procedure HITUNG
keadaan stack adalah :
1.6
MAPPING KE STORAGE DARI STACK
Bentuk mapping ke storage dari stack yang paling sederhana
adalah dengan menggunakan pendekatan array satu dimensi. Hal ini karena sarana
yang digunakan untuk menyatakan suatu stack adalah array.
Jika diberikan stack S dengan
m elemen maka bentuk mappingnya seperti mapping array satu dimensi dengan m
elemen.
Selanjutnya jika terdapat dua stack S1 dan S2 masing-masing dengan jumlah maksimum elemennya
adalah M dan N, maka kedua stack ini dialokasikan dalam dengan bentuk sbb:
Konsep mapping seperti diatas dianggap tidak efisien, terutama jika
S1 dan S2 tidak penuh pada saat yang bersamaan.
Cara yang dianggap
lebih baik adalah :
Jika diketahui bahwa jumlah elemen S1 dan S2 tidak melebihi jumlah tertentu, misal N.
NOEL(S1) + NOEL(S2) <= N
Maka bentuk mapping yang digunakan adalah :
Tidak ada komentar:
Posting Komentar