Stack and Implementation

Stack.

  Atau Tumpukan, adalah kumpulan dari elemen-elemen data yang disimpan dalam sebuah jalur linear, yang hanya dapat diakses melalui 1 jalan saja (pintu masuk dan keluar sama).

  Sebagai contoh Kotak Bola Tennis. Jalan tersebut dinamakan sebagai TOP, yaitu Posisi paling atas dari suatu tumpukkan. Misalnya kotak tersebut memiliki kondisi maksimal berisi 3 buah bola, kotak tersebut dalam keadaan terbuka, dan kosong. Kotak tersebut masih kosong, posisi TOP tadi berada di dasar kotak sehingga TOP. Jika kita memasukkan 1 bola ke dalamnya, maka posisi TOP tersebut akan naik dan berada di atas bola 1. Jika kita masukkan bola hingga bola ke-3, maka posisi TOP sekarang berada di posisi tutup kotak bola tennis(Posisi MAX), artinya kotak bola tennis sudah tidak mampu untuk menampung bola lainnya.
Di dalam Struktur Data, Stack dapat digunakan untuk Parsing, Evaluation, dan Backtrack. Elemen-elemen yang ditumpukkan dapat berupa Integer, Char, String, dan lain sebagainya.

   Konsep utama dari Stack adalah LIFO (Last In First Out) atau disebut sebaga FILO(First In Last Out). Benda terakhir yang dimasukkan ke dalam tumpukkan akan menjadi benda pertama yang keluar di dalam Stack. Memasukkan elemen baru ke dalam Stack disebut PUSH dan Mengeluarkan elemen lama dari dalam Stack disebut POP. Dengan konsep LIFO/FILO yang digunakan, maka suatu element yang di PUSH terakhir kali adalah elemen yang dapat di POP untuk pertama kali.

Contoh :

Beberapa Fungsi yang dapat digunakan dalam Stack :
 1. isEmpty : Digunakan untuk mengecek kosong atau tidaknya suatu Stack.
 2. isFull : Digunakan untuk mengecek penuh atau tidaknya suatu Stack.
 3. Size : Digunakan untuk mengetahui jumlah data pada Stack.
 4. Top / Peek / Pick : Digunakan untuk mengambil data TOP dari suatu Stack.
 5.Clear : Digunakan untuk mengosongkan Stack.


Representasi pada Array.

   Nilai Index digunakan untuk mengetahui letak dari suatu elemen di dalam suatu Stack. Sehingga elemen pertama kali yang dimasukkan nilai indexnya adalah 0 (dalam bahasa C), dan nilai TOP akan berpindah menjadi nomor index 1. Dari hal ini dapat disimpulkan bahwa data dalam suatu stack penuh, jika :
TOP == MAX(total data) - 1.

Jika TOP == NULL ,
maka Stack dinyatakan kosong.

Contoh Representasi pada Array :

Representasi pada Linked List.
  
    Setiap yang node yang ada di sini memiliki 2 fungsi, yaitu
  1. Menyimpan nilai.
  2. Menyimpan alamat pointer Node berikutnya.

   Pointer TOP bergerak, untuk menambah atau menghapus data yang ada.

Contoh :

   


Infix, Prefix, and Postfix.

   Salah satu bentuk konkrit penggunaan Stack adalah mengubah Infix, menjadi Prefix atau Postfix.
Infix = Operator di antara Operand.
Prefix = Operator di depan Operand.
Postfix = Operator di belakang Operand.

   Operator adalah angka, ataupun variabel yang digunakan untuk menyatakan sebuah nilai. sedangkan Operand adalah %, x, /, +, -,  atau alat yang digunakan untuk membantu memanipulasi sebuah nilai.
Ketika melakukan suatu Compute, atau menghitung suatu permasalahan matematika dalam kehidupan sehari-hari, kita menggunakan Infix. Di dalam perhitungan Infix, mengetahui Precedense-nya sangat penting untuk memecahkan permasalahan matematika. Precedense adalah operand dari suatu permasalahan matematika yang harus diprioritaskan terlebih dahulu pengerjaannya.

Depth First Search and Breadth First Search.

   DFS dan BFS adalah 2 jenis metode pencarian suatu data dalam Tree atau Graph. Terdapat perbedaan diantara keduanya :


*Urutan berdasarkan Angka

*Urutan berdasarkan Angka

Giga Dharmawan Goeij
1701327806
42 PFT

www.binus.ac.id ||www.skyconnectiva.com

Introduction to Tree, Binary Tree, and Expression Tree

Tree Concepts.

   Tree adalah kumpulan dari suatu node yang saling berhubungan secara bertingkat. Seperti artinya, Tree (pohon) dapat diliustrasikan sebagai suatu pohon. Pohon tersebut memiliki struktur one-to-many, yang artinya dari hanya 1 induk dengan banyak anak. Ada 3 model data mengenai node yang saling berhubungan ini :

   1. Tiap node dapat memiliki data dan link menuju ke node lainnya,

   2. Tiap node hanya memiliki 1 induk kecuali Root (akar),

   3. Dan tiap node dapat mempunyai anak berapapun jumlahnya.

     Tree :

   Gambar di atas merupakan contoh sebuah Tree sederhana.

-Root : Angka 1, yang berada pada posisi paling atas. Beberapa sumber menggunakan Level 0 sebagai awal pada baris Root. Tetapi di dalam pembahasan ini, Level 1 akan digunakan pada baris Root .

-Degree :  Total sub tree dari sebuah Node. Contoh : Total Degree dari angka 6 berjumlah 2.

-Children :  Node yang terhubung langsung dengan Node yang berada di atasnya. Contoh : Children dari angka 6 adalah 7 dan 8.

- Leaf : Node yang tidak memiliki Children. Contoh : Angka 4, 5, 9, dan 10.

-Parent : Node yang terhubung langsung dengan Node yang berada di bawahnya. Contoh : Parent dari angka 4 dan 5 adalah angka 3.

-Sibling : Node yang berada pada Level yang sama, dan memiliki Parent yang sama . Contoh : Sibling dari angka 7 adalah angka 8.

-Descendant(Keturunan): Adalah Seluruh node yang terhubung dari suatu Node, dan berada di bawahnya. Contoh : Descendant dari angka 2 adalah angka 3, 4 dan 5. 

-Ancestor : Kebalikan dari Descendant. Contoh : Ancestor dari angka 10 adalah angka 8,6, dan 1.

-Edge : Garis yang menghubungkan antar node.

-Predecesor :  Node yang berada di atas Node tertentu.

-Successor :  Node yang berada di bawah node tertentu.

-Subtree : Suatu node beserta Descendant-nya.

-Size :  Banyak node dalam suatu Tree.

-Height : Banyaknya Level dalam suatu Tree.

Graphs Vs. Trees

Binary Tree. 

   Merupakan salah satu contoh dari beberapa Tree lainnya, Binary Tree Maksimal hanya memiliki 2 Children saja. 'Bi' yang ada dalam kata Binary artinya 2, begitupula dengan yang Unary (Uno, 1) dan Ternary, yang memiliki 3 Children. Dalam Binary Tree, Children dari suatu Node dibagi menjadi 2 kubu, yaitu kiri dan kanan saja.

Beberapa jenis Binary Tree :

1. Complete Tree.

*Internal Nodes : Node yang memiliki Child/Children.

*Terminal Nodes : Node yang tidak memiliki Chile/Children.

2. Perfect /Full Tree.

*Perfect/Full Tree Termasuk Perfect Tree

3. Skewed Tree.

*Setiap Node maksimal hanya memiliki 1 Child.

Binary Tree Insertion.

   BST Disebut juga sebagai Ordered Binary Tree, meiliki Aturan dalam penggunaannya :

1. Child di sebelah kiri suatu Node Harus lebih kecil dari angka Parentnya sendiri.

2. Child di sebelah kanan suatu Node Harus Lebih besar atau samadengan dengan Parentnya sendiri.

Contoh :

Giga Dharmawan Goeij

1701327806

42PFT

www.binus.ac.id ||www.skyconnectiva.com

Array Vs. Linked List

   Array dan Linked List merupakan 2 cara dari beberapa cara untuk mengatur atau menstruktur data. Terdapat perbedaan diantara Array dan Linked List, dan perbedaan ini menyebabkan perbedaan penggunaannya pula. Misalnya penggunaan Array, adalah ketika kita ingin menggunakan variable yang sama dengan nilai yang berbeda (dibedakan dengan nomor Index). Tetapi perlu diingat bahwa Array hanya dapat menampung tipe data yang homogen dan alokasi memori akan tetap digunakan meskipun tidak digunakan, sehingga menyebabkan penggunaan Array tidak Flexible, dan tidak Efisien dalam penggunaan memori. Berbeda dengan Linked List, yang lebih mudah dan lebih efektif dalam menambah,mengurangi, mencari data yang terdapat didalamnya.

Secara mendasar, perbedaan antara Array dan Linked List adalah sebagai berikut :

No.	Array	Linked List
1	Setiap element hanya berisikan Data	Setiap element terdiri dari 2 bagian : Data Address & Pointer Address.
2	Bersifat Statis :       ·    Volumenya tetap, tidak tergatung pada jumlah data.       ·    Alokasi memori ditentukan saat mendefinisikan Array.       ·    Pengaksesan data menggunakan nomor index.	Bersifat Dinamis       ·     Volume berubah, sesuai dengan jumlah data.       ·     Alokasi memori ditentukan saat data baru dibuat.       ·     Pengaksesan data dilakukan secara linear(dari elemen pertama / akhir).
3	Pengaksesan data menggunakan nomor Index.	Pengaksesan data dengan cara linear (dimulai dari element awal atau akhir ).

Giga Dharmawan Goeij

1701327806

42PFT

www.binus.ac.id  || www.skyconnectiva.com

Link List Implementation

Linked List (Senarai Berantai).

   Seperti yang sudah dijelaskan sebelumnya, merupakan koleksi data yang tersusun secara linear. Penggunaan Linked List memberikan kemudahan dan lebih efektif dalam melakukan penambahan, pengurangan dan pencarian suatu Node/Simpul di dalam Linked List itu sendiri. Hal ini dapat terjadi karena penyimpanan elemen-elemen dari Linked List tidak ditempatkan dalam sebuah blok memori seperti Array. Perlu diingat sebuah Linked List tidak memungkinkan adanya pengaksesan data secara acak, artinya untuk dapat mengakses data pada nomor sekian wajib untuk melewati elemen-elemen sebelum nomor tersebut.

   3 types of Linked List :

1.Singly Linked List

Add caption

      

  Pada gambar di samping, yang dinamakan sebagai node/simpul adalah sebuah kotak, yang isinya terbagi menjadi 2 bagian, yaitu Bagian Data (Medan Informasi) dan Bagian Alamat (Medan Penyambung). Perlu diingat bahwa pada Bagian Alamat (Medan penyambung) adalah pointer yang menunjuk ke node/simpul berikutnya, sehingga isinya dapat berupa alamat lokasi node/simpul berikutnya, ataupun bernilai NULL. Setiap Medan Penyambung node/simpul paling akhir dari Linked List ini harus bernilai NULL.

2.Doubly Linked List

  Dalam Doubly Linked List, setiap node memiliki 2 link, yaitu untuk menunjuk pada node/simpul berikutnya, ataupun menunjuk pada node/simpul sebelumnya.Umumnya disebut sebagai Next dan Previous, atau Forward dan Backwards. Hal ini memudahkan pembacaan data (dari depan /dari belakang), sehingga penambahan dan penghapusan data dapat dilakukan pada node/simpul yang ada di sebelah kanan / kiri pointer.


3.Multiple Linked List

 



  Memliki pointer lebih dari 1, dan setiap pointernya menunjuk pada jenis data yang sama dengan urutan yang berbeda. Pada gambar disamping 2 pointer menunjukkan urutan berdasarkan name dan age. 









Ketika node/simpul terakhir suatu Linked List memiliki pointer pada node pertama sehingga Linked List tersebut tidak memiliki nilai NULL di dalamnya, makan Linked List tersebut dapat dinamakan sebagai Circular Linked List.

Hal yang dapat dilakukan dalam penggunaan Linked List :
  1.Insert
      Dapat dilakukan dengan 3 cara :
             1.Push Depan
             adalah ketika user memasukkan node/simpul baru ke dalam linked list, maka data tersebut akan berada pada alamat current/*curr. Setelah itu alamat yang memiliki data tersebut kemudian akan di "Push" ke arah Head, sehingga data pada current/*curr =head (artinya data telah berpindah ke depan menjadi head)

             2.Push Tengah
            adalah ketika user memasukkan node/simpul ke dalam linked list tetapi diantara kedua node/simpul yang sudah ada.

             3.Push Belakang
             Mirip dengan Push Depan, hanya saya penempatan node/simpulnya ada pada sebelum NULL (pointer node/simpul yang ditambahkan menunjuk pada NULL)


  2.Delete
      Dilakukan dengan memutuskan hubungan rantai node/simpul terlebih dahulu baru kemudian dihapus. Jika node/simpul berada di tengah rangkaian, maka rangkaian yang terputus perlu untuk disambungkan kembali. artinya proses delete dapat dilakukan dengan 3 cara :
            1.Pop Depan
            2.Pop Tengah
            3.Pop Belakang
Langkah-langkah yang digunakan untuk menghapuskan node/simpul :
1. Buat Cursor bantu yang menunjuk pada awal node/simpul.
2. Pindahkan Cursor pada node/simpul berikutnya, kemudian putuskan sambungan antar node awal dengan node berikutnya.
3. Jika berada di akhir rangkaian Linked List, putuskan dengan rangkaian sebelumnya. tetapi jika berada di tengah rangkaian, pindahkan penunjuk node ke berikutnya, atau ke akhir, atau pada node berikutnya setelah node yang akan dihapus


.
www.binus.ac.id || www.skyconnectiva.com
Giga Dharmawan Goeij
1701327806
42PFT

Pointer, Array, and Introduction to Data structure

Array.
   
   Merupakan suatu variabel, terdiri dari sekumpulan data yang memiliki tipe data yang sama. Setiap data di dalam array disimpan dalam alamat memori yang berbeda, dan disebut sebagai Elemen Array. Karena Elemen Array memiliki nilai dan alamat memori yang berbeda, maka tiap Elemen Array diberi nama Nilai Indeks dalam bentuk angka, sesuai dengan urutan datanya.
Dalam beberapa bahasa pemograman, seperti C, C++, Nilai Indeks dimulai dari angka 0. Untuk bahasa pemograman seperti Pascal, Nilai Indeks yang digunakan dimulai dari angka 1. Secara garis besar, menentukan jumah Array yang ingin disiapkan dideklarasi dengan menggunakan bracket ( [] ).
   Jumlah Array dapat kita tentukan sendiri dengan mengisi jumlah yang kita inginkan.
Misalnya int a[5], artinya kita menyiapkan 5 Elemen Array saja, tidak kurang tidak lebih, tidak dapat diubah lagi kecuali kita mengganti angka '5' di dalam bracket tersebut. tetapi ada juga yang seperti :
int a [] ={1,2,3,4}. Arti dari bracket yg kosong tersebut adalah kita menyiapkan Array sebanyak jumlah dari data di dalam kurung kurawal ( {} ), yang tiap datanya dibatasi oleh tanda koma ( , ).
   Dalam penggunaannya, kita dapat menginisialisasikan sendiri isi dari Array, bisa juga menginput datanya,atau bahkan dapat menetapkan nilai tersebut.

Beberapa operasi yang dapat dilakukan menggunakan Array :
1. Tranvesal.

2. Insertion.

3.Searching.

4.Deletion.

5.Merging.

6.Sorting.

   Dengan demikian, dapat disimpulkan juga penggunaan Array sangat penting, jika kita ingin 'bermain-main' dengan sejumlah data.


  Jenis-jenis Array :

1. Array 1 Dimensi
      Seperti namanya, hanya memiliki 1 Dimensi saja. 

      -Syntax :
           tipe_data nama_array [jumlah_elemen];

          contoh:
               int umur [10];
               int nilaimahasiswatetanggasebelah [500];

          cara mengaksesnya :
               umur [4]= 17;  //umur Nilai Indeks ke-4 adalah 17.

2. Array 2 Dimensi
      Sedikit berbeda, Array ini memiliki 2 Dimensi. Untuk mempermudah pemahaman, anggaplah 1 Dimensi mewakilkan Elemen Baris, dan 1 Dimensi lainnya mewakilkan Elemen Kolom. Bayangkan terciptanya sebuah tabel. Total jumlah dari Elemen yang ada adalah Baris x Kolom.

      -Syntax :
           tipe_data nama_array [jumlah_elemen_Baris] [jumlah_elemen_Kolom];

          contoh:
               int X [10] [20];

          cara mengaksesnya :
               X [4][16]= 123;  //Isi tabel X pada baris 4 kolom 16 Nilai adalah 123.

3. Array Multidimensi
      Memiliki banyak Dimensi. Bayangkanlah sebuah kotak, di dalam kotak tersebut tersedia tempat untuk beberapa kotak, dan setiap kotak tersebut memiliki kotak-kotak lagi di dalamnya. Penggambarannya sedikit sulit, tetapi semakin sering anda menggunakannya semakin baik pua pemahaman anda.
      Syntax, dan cara mengaksesnya kurang lebih sama dengan Array 2 Dimensi, hanya lebih banyak bracket ( [] ), sesuai dengan jumlah Dimensi yang diinginkan.  



Pointer.

   Berbeda dari variabel biasa, Pointer merupakan variabel yang berisikan alamat memori sebagai nilainya. Jadi isi nilai pointer adalah alamat dari variabel yang mempunyai nilai tertentu. 
Sebuah gambaran mengenai pointer :
(& adalah alamat, * adalah isi. )

int pointer=6;   //int pointer adalah 6.
int *pointer2 = &pointer; //isi dari int pointer2 adalah alamat dari int pointer, yang nilainya 6.
int *pointer2=6; //isi dari int pointer2 adalah 6.


Struktur Data.

   Adalah penyusunan, penempatan, pengaturan data atau penstrukturan data.
Contoh penstrukturan data :
     1. Array




          Seperti yang sudah dijelaskan di atas, Array merupakan suatu contoh dari Struktur Data. Penyimpanan data oleh Array hanya bisa dilakukan dengan kumpulan dari tipe data yang sama.



     2. Linked List

          Adalah koleksi data yang tersusun secara linear. Penyisipan dan pemindahan data dapat dilakukan di semua tempat dalam sebuah Link List. Pada gambar disamping, Data ( angka 2 )terletak di sebuah lokasi memori yang disebut node/simpul. Setiap node tersebut memiliki pointer ke node berikutnya, sehingga tercipta sebuah garis dengan satu arah yang dinamakan Single Link List. Double Link List adalah ketika node memiliki 2 arah berlainan ( bolak-balik ).


     3.Queues

          Adalah antrian. Artinya yang pertama datang adalah yang pertama keluar. Prinsip ini sering disebut sebagai FIFO ( First In First Out ).
Pada gambar disamping Enqueue adalah memasukkan suatu Elemen kedalam antrian, dan Dequeque adalah mengeluarkan suatu Elemen keluar antrian.
Hanya ada 1 pintu masuk dan pintu keluar, jadi Queues membutuhkan variabel head and tail.


     4. Stacks

 
          Menggunakan prinsip LIFO ( Last In First Out ). Penambahan dan pengurangan data selalu dilakukan di top, yaitu bagian teratas suatu Stack. Bottom adalah bagian terbawah dari suatu stack.




     5. Binary Trees

          Merupakan suatu pohon yang setiap node/simpulnya paling banyak memiliki 2 cabang anak. Secara umum anak setiap node dibedakan menjadi kiri dan kanan.





     6. Hash Table

   


  Digunakan dalam penyimpanan data sementara.Tujuan penggunaannya adalah untuk mempercepat pencarian kembali dari banyaknya data yang disimpan.





Tipe Data.

   Merupakan jenis data yang dapat diolah komputer untuk melakukan suatu jenis operasi, ataupun memenuhi kebutuhan suatu objek dalam pemograman komputer.

Contoh Tipe data pada bahasa C :
Void, Int, Long, Short, Char, Float, Bool, etc


Absctract Data Type.

   Atau ADT, adalah koleksi data dan operasi yang dapat digunakan untuk memanipulasi data tersebut. Dalam bahasa C++, ADT dapat dibuat dalam sebuah class. Class di C++, merupakan pengembangan dari struct bahasa C.

Contoh ADT dibagi menjadi 2 :
Built-in : Boolean, Integer, Array, dll
User-Defined : Stacks,Queues,dll


Struktur.

   Struktur dalam pemograman adalah kumpulan tipe-tipe data yang ditetapkan oleh pengguna, dikumpulkan dan dikemas kedalam suatu paket. Berbeda dengan Array, Struktur mengalokasikan memori dinamis, dan cara mengakses data dari suatu Struktur adalah menggunakan titik ( . ).

Contoh struktur :

struct Pendidikan
{
char tingkat[10];
char sekolah[100];
};


Untuk Nested Structure, sama seperti struktur pada umumnya, hanya saja mereka memiliki struktur lagi, didalamnya.
Contoh Nested Structure :

struct Pendidikan
{
char tingkat[10];
char sekolah[100];
};
struct data
{
char kode[10];
char nama[100];
int index;
Pendidikan pencapaian[4];
};
 siswa data[50];

Contoh Akses menggunakan titik ( . ) :
siswa[0].kode= 007;
siswa[1].pencapaian.sekolah='Maju Lagi';


Memory Allocation.

   Disingkat menjadi Malloc, merupakan fungsi standart untuk pengalokasian memori. Dibagi menjadi 2:
Dynamic : Memori yang dialokasi dapat berubah
Static      : Memori yang dialokasi tidak dapat berubah



Giga Dharmawan Goeij
1701327806
42PFT



www.binus.ac.id  ||  www.skyconnectiva.com