Rabu, 22 Mei 2013

Stack dan Queue STACK dan QUEUE

PENGERTIAN STACK

Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman

Bersifat LIFO (Last In First Out)

Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack

Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. 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

Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
Clear : digunakan untuk mengosongkan stack
IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

Stack with Array of Struct

Definisikan Stack dengan menggunakan struct

Definisikan MAX_STACK untuk maksimum isi stack

Buatlah variabel array data sebagai implementasi stack secara nyata

Deklarasikan operasi-operasi/function di atas dan buat implemetasinya

Deklarasi MAX_STACK

#define MAX_STACK 10 //hati-hati mulai dari 0 jadi 0-9

Deklarasi STACK dengan struct dan array data

typedef struct STACK{

int top;

char data[10][10]; //misalkan : data adalah array of string

//berjumlah 10 data, masing-masing string

//menampung maksimal 10 karakter

};

Deklarasi/buat variabel dari struct

STACK tumpuk;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah KOSONG!

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!

Ilustrasi stack pada saat inisialisasi:

Fungsi IsFull

Untuk memeriksa apakah stack sudah penuh?

Dengan cara memeriksa top of stack, jika sudah sama dengan

MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full

Ilustrasi:

Fungsi IsEmpty

Untuk memeriksa apakah stack masih kosong?

Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!

Program:

Fungsi Push

Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack

Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (diincrement)

Ilustrasinya:

Fungsi Pop

Untuk mengambil elemen teratas dari stack.

Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang

Ilustrasinya:

Programnya:

Fungsi Print

Untuk menampilkan semua elemen-elemen stack

Dengan cara looping semua nilai array secara terbalik, karena kita harusmengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil!

QUEUE DENGAN MENGGUNAKAN ARRAY

Queue = Antrian

Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya

DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian

Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular

Array

QUEUE DENGAN LINIEAR ARRAY

Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar

di ujung satunya

Sehingga membutuhkan variabel Head dan Tail

DEKLARASI QUEUE

OPERASI-OPERASI PADA QUEUE

- Create()

o Untuk menciptakan dan menginisialisasi Queue

o Dengan cara membuat Head dan Tail = -1

- IsEmpty()

o Untuk memeriksa apakah Antrian sudah penuh atau belum

o Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

o Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala

antrian (elemen pertama dalam antrian) yang tidak akan berubahubah

o Pergerakan pada Antrian terjadi dengan penambahan elemen

Antrian kebelakang, yaitu menggunakan nilai Tail

- IsFull()

o Untuk mengecek apakah Antrian sudah penuh atau belum

o Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1

adalah batas elemen array pada C) berarti sudah penuh

- Enqueue(data)

o Untuk menambahkan elemen ke dalam Antrian, penambahan

elemen selalu ditambahkan di elemen paling belakang

o Penambahan elemen selalu menggerakan variabel Tail dengan cara

increment counter Tail

- Dequeue()

o Digunakan untuk menghapus elemen terdepan/pertama dari Antrian

o Dengan cara mengurangi counter Tail dan menggeser semua

elemen antrian kedepan.

o Penggeseran dilakukan dengan menggunakan looping

- Clear()

o Untuk menghapus elemen-elemen Antrian dengan cara membuat

Tail dan Head = -1

o Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus

arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai

-1 sehingga elemen-elemen Antrian tidak lagi terbaca

- Tampil()

o Untuk menampilkan nilai-nilai elemen Antrian

o Menggunakan looping dari head s/d tail

JTree Sederhana

JTree merupakan komponen yang digunakan untuk membuat struktur pohon. Salah satu yang membuat rumit di JTree adalah cara menambah datanya. Anda perlu membuat TreeModel dan juga menambahkan MutableTreeNode. Sayangnya tidak ada kelas yang dapat menyederhanakan proses pembuatan data di JTree.
Jikalau bisa disederhanakan, kenapa tidak Anda yang mencoba untuk menyederhanakan cara pembuatan data di JTree? Dan artikel ini akan membahas tentang membuat JTree dinamis sederhana. Hanya ada satu root dan beberapa child :

      
Root

|_Child 1

|_Child 2

|_Child 3

|_Child 4

|_Child 5

|_Child 6

|_Child 7

|_Child 8

Membuat Kelas Creator

Untuk mempermudah pembuatan data di JTree, ada baiknya kita buat kelas Creator. Creator maksudnya kelas ini yang akan kita gunakan untuk membuat data TreeModel untuk JTree.
Sederhananya, kurang lebih kelasnya seperti pada kode dibawah ini :

      
/*

 *  Copyright (c) 2011, StripBandunk and/or its affiliates. All rights reserved.

 * 

 *       http://stripbandunk.com/

 * 

 *  STRIPBANDUNK PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

 */

package stripbandunk.tutorial.jtreedemo;

import javax.swing.tree.DefaultMutableTreeNode;

import javax.swing.tree.DefaultTreeModel;

import javax.swing.tree.TreeModel;

/**

 *

 * @author Eko Kurniawan Khannedy

 */

public class TreeModelCreator {

private DefaultTreeModel model;

private DefaultMutableTreeNode root;

public TreeModelCreator(String rootData) {

root = new DefaultMutableTreeNode(rootData);

model = new DefaultTreeModel(root);

}

public void addChild(String child) {

root.add(new DefaultMutableTreeNode(child));

}

public TreeModel getModel() {

return model;

}

}

view raw
          TreeModelCreator.java

Menggunakan Kelas Creator untuk JTree

Setelah membuat kelas TreeModelCreator, kita dapat menggunakan kelas tersebut untuk membuat TreeModel untuk JTree, contohnya seperti berikut :

      
TreeModelCreator creator = new TreeModelCreator("Root");

creator.addChild("Eko");

creator.addChild("Kurniawan");

creator.addChild("Khannedy");

creator.addChild("StripBandunk");

jTreeSample.setModel(creator.getModel());

view raw
          Form.java
          This Gist brought to you by GitHub.

Hasil Akhir

Hasil akhirnya adalah sebagai berikut :

JTree Demo

SUMBEER

Tree Pada Java

Terminologi

binary tree

maaf saya menggunakan istilah asing untuk terminologinya. soalnya saya sudah terbiasa pakai istilah ini, kalaupun diterjemahkan kuq hasilnya malah jadi aneh…

Path
Bayangkan seperti orang yang berjalan dari node ke node lain melalui garis yang menghubungkannya. Garis-garis penghubung yang delewati itulah yang dinamakan dengan path.

Root
Node pada posisi paling atas disebut root. Dalam sebuah tree hanya terdapat satu root saja.

Parent
Setiap node (kecuali root) mempunyai cabang yang menguhubungkan tepat satu node lain di atasnya. Node di atasnya inilah yang disebut parent.
Child
Setiap node bisa mempunyai satu atau lebih cabang yang menghubungkan ke node lainnya. Node di bawahnya inilah yang disebut dengan child.
Leaf
Node yang tidak mempunyai child disebut dengan leaf. Dalam sebuah tree hanya ada satu root saja tetapi bisa mempunyai banyak leaf.
Subtree
Setiap node bisa dipertimbangkan menjadi root nya subtree, yang terdiri dari beberapa children, dan children nya children.
Visiting
Sebuah node dikatakan dikunjungi ketika kendali program sampai pada sebuah node, biasanya untuk tujuan menyelesaikan beberapa operasi pada node, seperti mengecek nilai datanya kemudian menampilkannya.
Traversing
Traverse maksudnya mengunjungi semua node dalam tree untuk tujuan tertentu, misalnya: untuk mengurutkan datanya.
Level
Level node adalah banyaknya generasi node yang dihitung mulai dari root. Jika kita mengasumsikan bahwa root adalah level 0, maka children adalah level 1, grandchildren adalah level 2, dan seterusnya.
Key
Medan data dalam sebuah objek biasanya didesain dengan menggunakan sebuah key. Nilai dari key ini digunakan untuk melakukan pencarian data atau operasi lainnya.

Tree menggunakan Java
Beberapa class untuk mendemonstrasikan binary tree di java

Class Node –> untuk membuat node
class Node
{
int iData;                  // data yang digunakan sebagai kunci
double fData;        // data lain
node childKiri;     // node child kiri
node childKanan;        // node child kanan
public void tampilNode()
{
// (bagian dari tubuh method)
}
}
Class Tree –> membuat susunan Tree nya dimana di dalamnya juga terdapat beberapa method untuk:
pencarian node
penyisipan node
penghapusan node

class Tree
{
private Node root;    // satu-satunya data dalam tree
public void cari(int key)
{
tempat penulisan statemen cari
}
public void sisip(int id, double dd)
{
tempat penulisan statemen sisip
}
public void hapus(int id)
{
tempat penulisan statemen hapus
}
// klo ada method laen tulis di sini
}   // akhir dari kelas tree

sumber

Sorting dan Searching in Java

Didalam pemograman Java terdapat dua algoritma yang dapat digunakan dua metode yaitu sorting dan searching. Dibawah ini akan membahas dua algoritma tersebut dan beserta contoh listing pemograman dalam java.
1. Sorting

Sorting adalah proses menyusun elemen - elemen dengan tata urut tertentu dan proses tersebut terimplemantasi dalam bermacam aplikasi.

Macam - macam algoritma sorting :

Insertion Sort

Salah satu algoritma sorting yang paling sederhana adalahinsertion sort. Algoritma Insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian arrayyang belum diurutkan dan kemudian diletakan sesuai dengan posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang terisisa pada bagian array yang belum diurutkan.

Selection Sort

Selection Sort adalah memilih elemen dengan nilai yang paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke-n, dimana n adalah jumlah total elemen dikurangi 1.

Merge Sort

Sebelum pembahasan mengenai algoritma merge sort, akan dijelaskan garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut.

Pola Divide and Conquer

Beberapa algoritma mengimplentasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah:

1. Divide
Memilah masalah menjadi sub masalah.

2. Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif.

3. Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama.

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai dengan rangkaiannya.

Studi Kasus dalam pemograman java dengan menggunakan algoritmaSorting :

Class Bubble :

Class insert

Class Output :

2. Searching

Searching merupakan kegiatan untuk menemukan atau mencari suatu data yang ditentukan disuatu tempat, apakah sudah sesuai atau belum. Algoritma searching mempunyai beberapa metode, salah satunya adalah metode pencarian beruntun atau disebut juga denganSequential Search. Sequantial Search adalah metode pencarian yang dimulai dari data elemen pertama.

Studi Kasus dalam pemograman java dengan menggunakan algoritmaSearching :

Class Searching :

Hasil Output :

Stack dan Heap

· Dalam java, dikenal 2 buah jenis memory, yaitu ^[1&2]:

1. Stack (tempat local variable dan tumpukan method)

2. Heap (tempat instance variable dan object)

· Bila ada program berikut [1] :

Program xx

1. public class A {

2. B b1 = new B();

3. String s = "halo";

4. int i = 10;

6. public static void main(String[] args) {

7. A a = new A();

8. a.myMethod();

9. }

10.

11. private void myMethod() {

12. System.out.println(s);

13. }

14. }

class B {}

Yang terletak di stack :

1. Method main()

2. Method myMethod()

3. Variable reference a (baris 7)

Yang terletak di heap :

1. Variable reference b1 (baris 2)

2. Variable reference s (baris 3)

3. Variable i (baris 4)

4. Object dari kelas B (baris 2)

5. Object String dengan nilai “halo” (baris 3)

6. Object dari kelas A (baris 7)

SUMBER

MAP pada Java

Suatu array yang berisi N elemen bisa juga dilihat sebagai asosiasi (pemetaan) antara elemennya dengan bilangan 0, 1, ..., N-1 yang merupakan indeksnya. Jika i adalah salah satu bilangan ini, maka kita bisa mengambil elemen yang dipetakan oleh bilangan i, dan juga kita bisa meletakkan elemen baru pada posisi ke-i.
Suatu peta (map) adalah generalisasi dari array. Seperti array, map juga memiliki operasi untuk mengambil dan meletakkan elemen. Akan tetapi pada map, operasi ini tidak dilakukan pada bilangan 0, 1, ... N-1, akan tetapi pada sembarang Object.
Beberapa bahasa pemrograman menggunakan istilah array asosiatif (associative array) karena kesamaan perintah dengan array biasa. Pada bahasa pemrograman tersebut, kita bisa menuliskan A["joko"] yang digunakan untuk memetakan "joko" pada suatu elemen di dalam array.
Java tidak menggunakan perintah yang sama pada map, akan tetapi idenya serupa : Map adalah seperti array yang indeksnya adalah objek sembarang, bukan integer. Pada map, objek yang digunakan sebagai "indeks" disebut kunci (key). Objek yang ditunjuk oleh indeks tersebut disebut nilai (value).
Satu kunci hanya boleh menunjuk pada satu nilai, akan tetapi satu nilai bisa ditunjuk oleh beberapa kunci.
Dalam Java, map didefinisikan dalam interface java.util.Map, yang memiliki beberapa metode untuk bekerja dengan map. Jika map adalah variabel dengan tipe Map, maka berikut ini adalah beberapa metodenya :

Baca selengkapnya »

Stack dan Queue

Pengertian Stack

Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman
Bersifat LIFO (Last In First Out)
Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack
Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. 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.