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

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

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 gam