LINEAR LIST
¨
Linear list adalah suatu struktur data
yang merupakan himpunan terurut dari satuan data atau dari record.
¨
Elemen yang terdapat dalam daftar
disebut simpul/node.
¨
Daftar disebut Linear karena elemen
nampak seperti baris, bahwa setiap simpul (kecuali simpul pertama dan terakhir)
selalu memiliki elemen penerus langsung (suksesor) dan elemen pendahulu langsung
(predesor).
¨
Misalnya 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” (list hampa).
¨
Suatu elemen dapat dihapus (delete)
dari sembarang posisi pada linear list .
¨
Suatu elemen baru dapat dimasukkan
(insertion) kedalam list dan dapat menempati sembarang posisi pada list
tersebut.
¨
Jadi suatu linear list dapat berkurang
atau bertambah setiap saat
Contoh
: file merupakan linier list yang elemen-elemennya berupa record.
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 yaitu posisi akhir dari list. Posisi ini disebut puncak
atau disebut sebagai “TOP(S)”.
¨
Prinsip Stack adalah LIFO ( Last In First Out ) atau
Terakhir masuk pertama keluar.
Setiap
elemen tidak dapat dikeluarkan (POP keluar) sebelum semua elemen diatasnya
dikeluarkan.
¨
Elemen teratas (puncak) dari stack
dinotasikan sebagai TOP(S)
Misal
diberikan stack S sebagai berikut :
S= [ S2,S2,………, ST
] è
maka TOP(S) = ST
¨
Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL(S).
Dari
stack diatas maka NOEL(S) = T.
NOEL(S)
menghasilkan nilai integer.
Jika diberikan
sebuah stack S = [A,B,C,D] maka stack S ini dapat digambarkan sebagai berikut :
OPERASI PADA STACK
1.
CREATE (STACK)
2.
ISEMPTY (STACK)
3.
PUSH (ELEMEN, STACK)
4.
POP (STACK)
Ø
CREATE(S)
Operator ini berfungsi untuk membuat sebuah stack kosong (menjadi hampa)
dan didefinisikan bahwa
NOEL (CREATE (S)) = 0 dan
TOP (CREATE(S)) = null / tidak terdefinisi
Ø
ISEMPTY(S)
Operator
ini berfungsi untuk menentukan apakah
suatu stack adalah stack kosong (hampa) atau tidak . Operasinya akan bernilai
boolean dengan definisi sebagai berikut :
ISEMPTY(S) = true, jika S
adalah stack kosong atau NOEL(S) = 0
False, jika S
bukan stack kosong atau NOEL(S) ¹ 0
Catatan : ISEMPTY(CREATE(S)) = true
Ø
PUSH(E,S)
¨ 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 )
Ø
POP(S)
¨ 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 1 dan elemen pada posisi TOP akan
berubah.
¨ Operator ini tidak dapat digunakan pada
stack kosong, artinya POP(CREATE(S)) =
error condition dan
POP(PUSH(E,S)) = S
Catatan :
TOP(PUSH(E,S)) = E
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.
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 :
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 :
1. Elemen-elemen suatu ekspresi
aritmetik (string) di-Scan dari kiri ke kanan.
2. Jika ditemukan simbol
"(" atau "Left parenthesis", maka simbol tersebut di-push
ke dalam stack.
3. 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.
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.
3. Bila
simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar
mulai dari simbol "(" yang pertama ditemukan dalam stack.
4. 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.
5. Bila
simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai
output.
6. 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 ;
Jadi ekspresi aritmatik
: ( ( A + B ) * C / D + E^F ) / G ;
dalam notasi postfix menjadi : AB+D*C/EF^+G/.
PROSES
REKURSIF
Stack juga dapat digunakan untuk menelurusuri
suatu program atau procedure yang rekursif.
Berikut ini sebuah 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 yahun yaitu
sebesar 8% per_tahun.
Penyelesaian :
Untuk
menyelesaikan masalah ini akan digunakan logika stack yatiu :
- 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 sebuh
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 :
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 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 :
