Agie wahyu winata: STACK. I. STACK DAN QUEUE DENGAN LINKED LISTPengertian Linked list . Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen- elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori. Bentuk Umum : Infotype . List l adalah list kosong, jika First(L) = Nil. Elemen terakhir dikenali, dengan salah satu cara adalah karena Next(Last) = Nil. Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null. Single Linked List. Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana- mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL). Pembuatan Single Linked List dapat menggunakan 2 metode. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List. Circular Double Linked List. Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran. Operasi- Operasi yang ada pada Linked List. Elemen tersebut lalu dikembalikan oleh fungsi. Contoh Program Array pada Pascal. Ditulis oleh: Lynx krish - Rabu, 05 Desember 2012. Variabel bisa kita gunakan yang saat ini hanya bisa menampung satu data hanya pada satu variabel saja. Dalam banyak kasus kita akan repot. BELAJAR PEMROGRAMAN pascal : STACK (TUMPUKAN) - Blognya Anak GAPTEK Blog dengan info Teknologi dan Entertainment Tergaptek. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut. Head berpindah ke elemen sesudahnya. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data- data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori. Contoh program stack pembalik kata: //header #include <iostream.h> #include <stdio.h> #include <stdlib.h> #include <conio.h> #define maxstack 200 struct STACK //membuat jenis data abstrak 'STACK'A. STACK DENGAN SINGLE LINKED LISTSelain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori. Misalnya pada stack dengan array disediakan tempat untuk stack berisi 1. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia. Operasi- operasi untuk Stack dengan Linked List. Push di sini mirip dengan insert dalam single linked list biasa. QUEUE DENGAN DOUBLE LINKED LISTSelain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list. Operasi- operasi Queue dengan Double Linked List. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong. Berikut ini adalah contoh program pascal animasi stack (tumpukan). Program AnimasiStack; Uses wincrt; const max = 10; var top,i : byte; pil,tem,E : char; stack : array Program recort; uses crt; type mahasiswa=record nama:string Tidak ada istilah full pada stack. Maka bentuk deklarasinya dalam PASCAL adalah : TYPE Stack. Berikut ini tiga buah contoh aplikasi stack. Membuat program stack dengan Pascal Listing program : uses crt; const lowbound = 0; upbound = 5; type pstack = ^stack; stack = record info : byte; x,y. Berikut ini adalah beberapa buah contoh program bilangan urut yang menggunakan while-do pada turbo pascal. Program ini menggunakan bentuk. Contoh Program Menggunakan SWITCH CASE Pada Pemrograman C++. Tidak ada istilah full pada stack. Program tidak menentukan jumlah elemen stack yang mungkin ada. Penyajian tumpukan dalam bahasa Pascal dapat disajikan dalam beberapa cara, yaitu dengan tipe data array, record, atau pointer. Jika benar maka queue sudah penuh. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head). II. STACK DAN QUEUE DENGAN ARRAY1. STACK DENGAN MENGGUNAKAN ARRAYPengertian Stack. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga. Operasi- operasi/fungsi Stack. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH! QUEUE DENGAN MENGGUNAKAN ARRAY. Stack Dengan Linked List VS Stack Dengan Array. Berikut ini adalah perbandingan algoritma pada operasi- operasi dasar dari Stack Dengan Linked List dan Stack Dengan Array, dengan menggunakan bahasa pemrograman Pascal. Stack Dengan Linked List Stack Dengan Arrayoperasi : create()procedure create; begintop : = nil ; end; procedure create; begintop : = 0; end; operasi : empty()function empty : boolean; begin empty : = false ; if top = nil then empty : = true ; end; function empty : boolean; begin empty : = false ; if top = 0 then empty : = true ; end; operasi : full()tidak ada istilah full pada stack. Hal ini berkaitan dengan penggunaan alokasi memori pada linked list yang lebih dinamis jika dibandingkan dengan array, sehingga pemborosan memory dapat dihindari. Program tidak menentukan jumlah elemen stack yang mungkin ada. Kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. Tempat akan sesuai dengan banyaknya elemen yang mengisi stack. Queue Dengan Linked List VS Queue Dengan Array Implementasi queue menggunakan array. Misal didefinisikan suatu linear list A yang terdiri atas T buah elemen sebagai berikut : A = . 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.* DEFINISI STACKStack 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 = . Dari stack di atas, maka NOEL(S) = T. Selanjutnya, jika diberikan sebuah stack S = . POP(stack)* CREATEOperator ini berfungsi untuk membuat sebuah stack kosong dan didefinisikan bahwa : NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null* ISEMPTYOperator 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 kosongatau. ISEMPTY(S) = true, jika NOEL(S) = 0= false, jika NOEL(S) * 0. Catatan : ISEMPTY(CREATE(S)) = true.* PUSHOperator 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).* POPOperator 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* DEKLARASI STACK PADA BAHASA PEMROGRAMANDalam 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 1. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 1. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain yaitu TOP. Selanjutnya gabungan kedua variabel ini diberi nama STACK. Kemudian didefinisikan bahwa : NOEL(S) = TOP. 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 STACKLogika 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 PARENTHESESProses 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. Jika ditemukan simbol . Jika ditemukan simbol . Berikut ini bentuk flowchart (logika proses) yang digunakan pada proses matching ini : * NOTASI POSTFIXBentuk 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. Perkalian (*) atau Pembagian (/)3. Penjumlahan (+) atau Pengurangan (- )Aturan yang digunakan dalam proses transformasi tersebut adalah : 1. Ekspresi aritmatik yang diberikan di- . Bila simbol yang di- scan adalah . Bila simbol yang di- scan adalah . Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack. 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. 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.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
January 2017
Categories |