Tugas mandiri struktur data

Download Tugas mandiri struktur data

Post on 21-Jan-2015

5.469 views

Category:

Education

6 download

Embed Size (px)

DESCRIPTION

Makalah Tugas mandiri struktur data Semester 2

TRANSCRIPT

<ul><li> 1. TUGAS MANDIRI STRUKTUR DATA DENGAN OPERASI STACK (TUMPUKAN) MATA KULIAH : STRUKTUR DATA PROGRAM STUDI TEKNIK INFORMATIKA UNIVERSITAS PUTERA BATAM 2013 Nama : Asep Jaenudin NPM : 120210034 Kode kelas : 122-IF211-M5 Dosen : Ganda Sirait, S.Si., M.SI. </li></ul><p> 2. i KATA PENGANTAR Segala puji dan syukur penyusun panjatkan kehadirat Allah SWT yang telah menganugerahkan rahmat, karunia serta ridha-Nya, sehingga penyusun dapat menyelesaikan makalah Tugas mandiritentang STRUKTUR DATA DENGAN OPERASI STACK (TUMPUKAN).Makalah Tugas mandiriini disusun sebagai salah satu tugas pada mata kuliah Struktur Data. Dalam penyusunan makalah ini, penyusun telah banyak menerima bimbingan dan saran-saran dari berbagai pihak. Maka pada kesempatan ini penyusuningin mengucapkan terima kasih yang setulusnya kepada: 1. BapakGanda Sirait, selaku Dosen mata kuliah Struktur Datadi Universitas Putera Batam yang telah banyak memberikan penjelasan teori yang berkaitan dengan tugas makalah ini. 2. Rekan-rekan serta semua pihak yang tidak dapat penyusun sebutkan satu persatu yang telah membantu dalam pembuatan makalah ini. Akhirnya penyusun berharap makalah ini dapat berguna dan dapat dipergunakan sebagaimana mestinya. Penyusun mengharapkan kritik dan saran untuk kemajuan di masa-masa mendatang. Atas perhatiannya penyusunucapkan terima kasih. Batam, 3 Juni 2013 Penyusun 3. ii DAFTAR ISI KATA PENGANTAR......................................................................................... i DAFTAR ISI........................................................................................................ ii BAB I. PENDAHULUAN................................................................................... 1 1.1 Latar Belakang Masalah ........................................................................... 1 1.2 Rumusan Masalah..................................................................................... 2 1.3Tujuan dan Manfaat Penyusunan.............................................................. 2 BAB II. PEMBAHASAN.................................................................................... 3 2.1 PengertiandariStack .................................................................................. 3 2.2Pendeklarasian Stack ................................................................................. 6 2.3Skema Traversal Pada Stack...................................................................... 7 2.4Skema Search Pada Stack. ......................................................................... 7 2.5Operasi Dan FungsiPada Stack.................................................................. 7 2.6Deklarasi Stack Pada Bahasa Pemrograman.............................................. 11 2.7Penggunaan/Aplikasi Stack........................................................................ 13 2.8Operasi Logika Pada Struktur Data Stack ................................................. 14 2.9Aplikasi Stack Pada Pemrograman Pascal................................................. 19 BAB III. PENUTUP............................................................................................ 25 3.1 Kesimpulan............................................................................................... 25 3.2 Saran ........................................................................................................ 26 DAFTAR PUSTAKA.......................................................................................... 27 4. 1 BAB I PENDAHULUAN 1.1 Latar Belakang Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadi program secara keseluruhan lebih efisien dan sederhana seperti stack merupakan bagian dari struktur data yang dikategorikan ke dalam bentuk linier data, dimana operasi pemasukan maupun pengeluaran data selalu dilakukan pada salah satu sisinya. Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan aplikasi lain. Stack bersifat LIFO (Last In First Out) dan benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack itu. Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau dengan kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push. Pada stack jarang sekali dilakukan operasi traversal, karena keunikan stack justru pada operasi yang hanya menyangkut elemen TOP (atas). Struktur ini sering dipakai dalam informatika misalnya untuk merepresentasikan pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, dan backtracking. Satu hal yang perlu diingat adalah bahwa didalam suatu tumpukan dapat menambah (menyisipkan) data dan mengambil (menghapus) data lewat ujung yang sama yang disebut sebagai ujung atas tumpukan. Penyajian stack bisa menggunakan array, namun kurang tepat. Array bisa digunakan kalau elemen stack tidak melebihi batas maksimum. Tipe yang bisa digunakan adalah record. Manipulasi dengan menggunakan record mempunyai dua medan, yaitu medan penyimpanan elemen tumpukan dan medan pencatat posisi ujung atas tumpukan. Stack dapat diimplementasikan sebagai representasi berkait atau kontinyu (dengan tabel fix). TOP merupakan pintu untuk keluar masuknya elemen elemen stack. 5. 2 1.2 Rumusan Masalah Berdasarkan latar belakang tadi, maka penyusun menemukan beberapa permasalahan yang kiranya akan menjadi bahasan pada penyusunan makalah ini, diantaranya yaitu : 1. Apa pengertian dari stack pada struktur data? 2. Bagaimana pendeklarasian Stack? 3.Bagaimana skema traversal dari stack? 4. Bagaimana skema search dari stack? 5.Apa saja operasi-operasi dan fungsi dasar pada stack? 6. bagaimanadeklarasi stack pada Bahasa Pemrograman? 7. Bagaimana penggunaan/aplikasi dari stack? 8. Bagaimana operasi logika pada Struktur Data stack? 9. Bagaimana aplikasi Stack pada pemrograman pascal? 1.3 Tujuan dan Manfaat Penyusunan Tujuan makalah ini adalah untuk mengetahui lebih jauh tentang penggunaan operasi stack dalam struktur data. Sehingga tentunya akan dapat memberikan sebuah manfaat bagi diri kita maupun orang lain. Dengan penyusunan makalah ini, semoga ada manfaat yang dapat kita rasakan, terutama bagi rekan-rekan yang belajar tentang struktur data dan bagaimana implementasi dari struktur data tersebut dalam suatu aplikasi sederhana. 6. 3 BAB II PEMBAHASAN 2.1 Pengertian Stack Stack (tumpukan) dapat dikatakan sebagai list yang operasi penghapusan dan pemyisipan elemennya dilakukan disatu ujung. Dalam kehidupan sehari-hari, terdapat banyak kejadian yang mempunyai sifat seperti stack, salah satunya adalah ceritadibawah ini: Perhatikan sebuah tumpukian piring disebuah warung makan.Piring-piring tersebut tersusun rapat dari atas ke bawah(membentuk barisan berurutan). Setiap kali ada pembeli datang, maka piring yang paling atas akan diambil(menghapus elemen) yang berarti mengurangi jumlah piring dalam tumpukan. Bila tumpukan itu sudah habis atau tinggal sedikitmaka pegawai warung akan menambahkan piring lain yang masih bersih (menambah elemen) piring yang paling terakhir diletakkan pasti akan terletak ditumpukan paling atas dan piring yang terletak paling atas dalam tumpukan itu pasti merupakan tumpukan piring yang terakhir kali dimasukkan. Kesimpulannya adalah penambahan dan penghapusan elemen hanya dapat dilakukan diujung atas tumpukan piring. Proses seperti itu biasa disebut Last In First Out(LIFO). Secara formal sebuah stack bertipe T didefinisikan sebagai sebuah barisan berhingga atas elemen-elemen bertipe T, bersama-sama dengan operasinya berikut: 1) Inisiasi stack menjadi kosong. 2) Mencari tahu status stack kosong atau tidak. 3) Mencari tahu stack penuh atau tidak. 4) Mencari panjang stack(jumlah elemen stack). 5) Memasukkan elemen baru pada stack, yaitu top stack jika stack tidak penuh. 6) Jika stack tidak kosong, mengambil elemen teratas(top stack). Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak. 7. 4 Gambar 1. Ilustrasi Stack 1 Gambar 2. Ilustrasi Stack 2 Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau dengan kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push, dan untuk memindahkan data dari tempat tersebut digunakan perintah pop. Sedangkan dalam penyajiannya, stack bisa memakai array atau linked list. Adapun definisi-definisi seperti : Definisi 1: Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya. Definisi 2: Diberikan suatu himpunan yang terurut himpunan sebagai S = {S1, S2, ......., ST}, T pada anggota S merupakan linier order, sehingga stack dari himpunan tersebut memiliki informasi sebagai berikut: 1. Elemen puncak dari stack dalam himpunan S dikatakan sebagai TOP, sehingga : TOP[S} = ST ............................................................................(1) 2. Banyaknya elemen stack dalam himpunan S dikatakan sebagai NOEL, sehingga NOEL = T, dimana himpunan dari S tersebut dapat disusun sebagai : S = {S1, S2, .........., SNOEL} ..................................................(2) 8. 5 Dari dua definisi tersebut di atas maka suatu stack dapat digambarkan sebagai berikut : 1. Suatu stack dalam keadaan kosong akan memiliki informasi NOEL(S) = 0 dan TOP(S)= undefined. S 2. Untuk stack yang bukan kosong, maka akan memiliki informasi seperti yang digambarkan di bawah ini dimana informasi yang ada adalah NOEL(S) = 1 dan TOP(S) = Merah. S 3. Untuk stack yang berisi lebih dari n jumlah data maka informasi yang ada pada stack tersebut berisikan NOEL(S) = 2 (jika berisi 2 data) dan TOP(S) = Biru seperti ditunjukan pada gambar di bawah ini : S Elemen-elemen yang berada dalam stack tersebut di atas, memiliki prinsip dasar dalam pengoperasiannya yaitu prinsip LIFO (Last In First Out) atau yang masuk paling belakang akan memiliki prioritas untuk keluar paling depan. 9. 6 Suatu stack dapat digambarkan sebagai suatu array (larik) berdimensi satu yang elemen-elemennya berkisar antara 1 sampai n elemen. Dengan demikian jika suatu stack didefinisikan dengan n elemen maka dapat dikatakan jumlah maksimum dari stack atau NOEL(S) nya adalah n, sehingga penambahan elemen stack yang ke n+1 tidak diperkenankan atau stack tersebut dalam kondisi overflow. Hal tersebut juga berlaku untuk stack dengan nilai minimum yaitu NOEL(S) dari stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen atas stack tersebut akan mengakibatkan stack tersebut dalam kondisi underflow. Dua kondisi tersebut merupakan dasar dalam merancang suatu aplikasi pemrograman komputer. 2.2 Pendeklarasian Stack Stack dapat dideklarasikan sebuah record yang mempunyai sebuah array data untuk menyimpan elemen stack dan sebuah variabel Top untuk menunjuk stack elemen atas (top element). Deklarasi selengkapnya sebagai berikut: Tipestack adalah nama pengenal tipe untuk stack. Maks_stack merupakan jumlah meksimum elemen stack. Dataadalah array yang digunakan untuk menyimpan data-data stack. Array yang digunakan disini adalah model array linier. Indeks array dimulai dari s/d maks_stack. Tipedata adalah tipe data dari elemen-elemen stack. Top dipakai untuk menunjuka elemen teratas dari stack. Nilai yang diizinkan adalah 0 s.d. maks-stack. Jika array diakses dari indeks kecil (1) ke arah indeks besar (maks_stack), maka nilai ini akan bertambah 1 bila ada penambahan elemen; dan berkurang 1 jika ada penghapusan elemen. S adalah nama variabel yang bertipe stack. Tipestack = record Data : array[1..maks_stack] of tipe data Top : 0..maks_stack; End; Var S : tipestack; 10. 7 2.3 Skema TraversalPada Stack Pada stack, jarang sekali dilakukan traversal, karena keunikan Stack justru pada operasi yang hanya menyangkut elemen TOP. Namun dibutuhkan traversal misalnya untuk mencetak isi Stack.Pemrosesan traversal yaitu mengolah seluruh elemen tabel secara sistematik.Skemanya adalah : Contoh penggunaan skema pada pascal: - Prosedur memasukkan nilai seluruh elemen tabel. 2.4 Skema Search Pada Stack Skema search adalah algoritma pencarian yang mirip dengan pencarian berkas. Pada stack, elemen yang diproses hanyalah elemen pada TOP. Maka hampir tidak pernah dilakukan search. Penggunaan search pada stack tidak dijamin untuk menemukan solusi optimal untuk masalah pencarian. 2.5 Operasi dan Fungsi Dasar Pada Stack Dalam penggunaannya suatu stack memiliki beberapa operasi yang dapat diterapkan seperti membuat stack, penambahan elemen ke dalam stack, menghapusan elemen dari dalam stack, dan operasi lain yang berhubungan dengan stack tersebut. Procedure ProsesTraversal (Var TI:TabInt); Var i:integer; Begin Inisialisasi; {prosedur persiapan sebelum pemrosesan} For i:=IdxMin to IdxMax do Begin Proses (TI[i]); {proses terhadap elemen saat itu} End; Terminasi; {prosedur aksi setelah pemrosesan selesai} End; Procedure InputTabInt (Var TI : TabInt); Var i : Integer; Begin For i := IdxMin to IdxMax do Begin Write (Elemen ke-,i); Readln (TI[i] ); End; End; 11. 8 Ada empat operasi dasar yang didefinisikan pada stack, yaitu : 1. CREATE(stack) 2. ISEMPTY(stack) 3. PUSH(elemen,stack) 4. POP(stack) 1. Create Operasi Create (Stack) digunakan untuk membuat suatu stack baru dengan nama stack, yang nilai elemen saat stack tersebut dibuat adalah NOEL(S) = 0, TOP(S) = NULL (tidak terdefinisikan). Operator ini berfungsi untuk membuat sebuah stack kosong dan didefinisikan bahwa : NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null Algoritma Create(S) Algoritma ini memuat suatu prosedur untuk membuat stack, yang memberikan kondisi noel dari stack akan bernilai nol dan top dari stack tersebut belum dapat didefinisikan, sehingga implementasi dari algoritma create stack adalah: 2. IsEmpty Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam keadaan kosong atau berisi. Operasi ini memiliki 2 (dua) kondisi boolean yaitu : a. True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0. b. False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan NOEL(S) &gt; 0. 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. Procedure Create(var S : Stack); Begin S.Noel := 0; . End; Catatan : ISEMPTY(CREATE(S)) = true 12. 9 Algoritma IsEmpty(S) Algoritma untuk operasi Isempty memberikan informasi Boolean yaitu kondisi benar (true) atau salah (False), sehingga pada implementasinya algoritma ini menggunakan fungsi yang dibuat sendiri.Implementasinya sebagai berikut : 3. Push Ope...</p>