KATA PENGANTAR

Segala Puji bagi Allah Subhanahu wa Ta’ala, Tuhan semesta alam. Shalawat dan salam semoga tetap terlantun bagi kekasih-Nya, Muhammad Shalallahu ‘alaihi wa sallam, beserta keluarganya yang mulia, sahabatnya yang tercinta, dan pengikutnya yang setia hingga akhir zaman. Berawal dari rasa keingintahuan yang mendalam akan suatu ilmu, dan rasa tanggung jawab serta kesadaran akan tugas pembuatan makalah yang diberikan Ibu dosen mata kuliah Struktur Data, kami selaku penyusun berusaha mengerjakan dan menyelesaikannya dengan semaksimal mungkin. Walaupun sangat jauh dari kesempurnaan dan bahkan mungkin tidak sesuai dengan yang diharapkan, namun penyusun harap Ibu dosen dapat menerimanya.

Makalah yang penyusun buat berjudul “STACK ( TUMPUKAN )”. Makalah ini terbagi kedalam tiga bagian atau bab. Bab pertama pendahuluan yang membahas sepintas tentang latar belakang, tujuan dan ruang lingkup. Bab kedua Isi makalah, membahas tentang STACK (TUMPUKAN). Bab ketiga penutup, berisi kesimpulan, saran, dan daftar pustaka. Saran dari pembaca terutama Ibu dosen sangat penyusun harapkan demi perbaikan selanjutnya. Akhirnya hanya kepada Allah SWT. penyusun bersyukur atas terselesaikannya makalah ini serta menyerahkan diri kepada-Nya, atas segala kekurangan dan kekhilafan atas apa yang penyusun tulis dalam makalah ini. Semoga makalah ini bermanfaat untuk pembinaan akhlak umat, demi kebaikan hidup dunia akhirat. Semoga Allah SWT mencatatnya sebagai amal baik terhadap apa yang telah kita lakukan. Amiin

Makassar, 14 September 2010

Kelompok X

BAB 1

PENDAHULUAN1.1 Latar Belakang

Sebagaimana yang telah dijelaskan sepintas dalam kata pengantar bahwa penyusun

makalah berusaha menyajikan tulisannya kedalam tiga bab. Bab pertama pendahuluan berisi

tentang latar belakang, tujuan, dan ruang lingkup. Bab kedua pembahasan materi, Stack

(Tumpukan) secara umum. Bab ketiga penutup berisi kesimpulan,saran, dan daftar pustaka.

1.2 Tujuan

Tujuan utama pembuatan makalah ini adalah sebagai wujud rasa tanggung jawab

penyusun selaku mahasiswa atas kewajibannya, dalam hal ini penyusun berusaha menyelesaikan

tugas yang diberikan dosen mata kuliah Struktur Data untuk membuat makalah yang membahas

tentang Stack secara umum serta pengaplikasiannya . Selain itu penyusun pun berusaha

mendalami suatu bidang ilmu yang masih asing dan belum penyusun pahami mudah-mudahan

dengan ini penyusun menjadi lebih memahami tentang pembahasan materi ini. Pemicu demi

perbaikan diri dari hari keharipun menjadi tujuan dari pembuatan makalah ini. Terakhir mudah-

mudahan usaha penyusun dicatat sebagai amal baik yang di-ridhai Allah Subhanahu wa Ta’ala

dan dapat berguna. Amiin.

1.3 Ruang Lingkup

Ruang lingkup pembahasan materi yang disajikan penyusun dalam makalah ini adalah

seputar Stack (Tumpukan). Untuk memulai pada pembahasan penulis awali dengan ucapan

Bismillahi Tawakkaltu ‘al Allah.

BAB II

PEMBAHASAN MATERI

STACK

n 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.

n 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 :

S = [ S1, S2, .........., ST ] à maka TOP(S) = ST.

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 :

n OPERASI DASAR PADA STACK

Ada empat operasi dasar yang didefinisikan pada stack, yaitu :

1. CREATE(stack)

2. ISEMPTY(stack)

3. PUSH(elemen,stack)

4. POP(stack)

m CREATE

Operator ini berfungsi untuk membuat sebuah stack kosong dan didefinisikan bahwa :

NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null

m 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.

m 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).

m 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

n 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.

n 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 :

m 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.

Misalkan NEXT CHAR adalah suatu karakter terakhir dalam suatu string. Berikut ini bentuk flowchart (logika proses) yang digunakan pada proses matching ini :

m 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 ;

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/

n 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 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 :

n 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 :

Contoh Soal

Contoh deklarasi :

const MaxElemen = 255;type Tumpukan = recordIsi : array [1..MaxElemen] of integer ;Atas : 0..MaxElemenend;var T : Tumpukan ; Dengan deklarasi di atas kita

menganggap bahwa elementumpukan T, yang tersimpandalam larik T.Isi , adalah bertipeinteger dan banyaknya elementumpukan maksimum adalahsebesar MaxElemen, yang dalam halini 255 elemen. Tipe data dari medanAtas harusbilangan bulat antara 0 sampaiMaxElemen, karena nilainyamenunjukkan banyaknya elemenyang ada dalam suatu tumpukan,

operasi push dapat implementasikan sebagai berikut :procedure PUSH (Var T : Tumpukan; X: Integer);BeginT.Atas := T.Atas + 1;T.Isi[T.Atas] := xend;procedure PUSH (Var T : Tumpukan; X: Integer);Beginif T.Atas := MaxElemen thenwriteln (‘Tumpukan Sudah Penuh’)ElseBeginT.Atas := T.Atas + 1; T.Isi[T.Atas] := xEndend;

Jika kontrol berupa data bertipe boolean, maka prosedurnya :procedure PUSH (Var T : Tumpukan; var Penuh: boolean; x: Integer);beginif T.Atas := MaxElemen then{* Tumpukan sudah penuh *}Penuh := trueelsebeginPenuh := falseT.Atas := inc (T.Atas) ;T.Isi[T.Atas] := xendend;

operasi pop dapat implementasikan sebagai berikut :procedure POP (Var T : Tumpukan; X: Integer);beginT.Atas := T.Atas -1;T.Isi[T.Atas] := xend;procedure POP (Var T : Tumpukan; X: Integer);beginif T.Atas := MaxElemen thenwriteln (‘Tumpukan Sudah KOsong’)elsebeginT.Atas := T.Atas -1; T.Isi[T.Atas] := xendend;

Contoh Program :

const Elemen = 255; function POP (var T : Tumpukan) : char;type S255 = string [Elemen]; beginTumpukan = record POP :=T.Isi [T.Atas];Isi : S255; T.Atas := T.Atas-1;Atas : 0..Elemen end;end;var T : Tumpukan; beginI : integer; clrscr;Alfabet : S255; Awalan (T);

write ('Isikan Data : ');procedure AWALAN (var T : Tumpukan); readln (Alfabet);begin clrscr;T.Atas := 0 ; writeln ('Data asli :');end; writeln(Alfabet);

writeln;procedure PUSH (var T : Tumpukan; X:char); writeln('Setelah dibalik:');begin for I := 1 to length (Alfabet) doT.Atas := T.Atas+1; PUSH (T, Alfabet[I]);T.Isi := X for I := 1 to length (Alfabet) doend; write (POP(T));

writelnend.

Setelah Program di RUN

Di Enter

BAB III

PENUTUP

3.1 Kesimpulan

Pada “STACK” Data hanya bisa di ambil secara berurutan, tidak bias di ambil secara langsung.

Hal ini berada dengan system yang ada pada “LINKED LIST” di mana data dapat di ambil secara acak, bias di tengah, di atas atau terakhir, bahkan data dapat langsung di hapus.

3.2 Saran

Makalah yang kami sajikan ini sangat jauh dari kesempurnaan karena banyaknya kekurangan dan kesalahan, Oleh sebab itu untuk memperkaya pengetahuan tentang pembahasan STACK (TUMPUKAN) dapat pembaca gali sendiri dalam sumber-sumber lain yang membahas tentang hal tersebut. Akhir kata kami ucapkan terima kasih Wabillahhitopik walhidayah assalammualaikum Wr.Wb.

DAFTAR PUSTAKA

www.google.com

Wikipedia.org

“Struktur Data” oleh Bambang Hariyanto, IR. MT.

Handbook “Algoritma & Struktur Data“ oleh Kartika Firdausy, ST. MT.

TUGAS MATA KULIAH STRUKTUR DATA

“STACK ( TUMPUKAN )”

Disusun Oleh :

RAHMAT KARUNIA GALIB (D42109114)

EMYL SATRIA BAKRI (D42109115)

AHMAD AMINUDDIN (D42109124)

TEKNIK INFORMATIKA

JURUSAN TEKNIK ELEKTRO

FAKULTAS TEKNIK

UNIVERSITAS HASANUDDIN MAKASSAR

2010