Stack and Implementation

Pertemuan 5

Pada pertemuan kelima kita diajarkan mengenai Stack and Implementation.

Pada pertemuan ke 5, topik pembicaraan nya memiliki sangkut paut dengan pertemuan ke empat.

Stack : Memiliki 2 konsep , LIFO (Last In First Out) dan FILO (First in Last Out). Sebagai Contoh, semisal ada tumpukan piring, kita pasti mengambil tumpukan piring teratas terlebih dahulu kecuali ada orang yang repot yang ingin mengambil piring dari tengah, Memang ada 2 kemungkinan. Tetapi kalau kita ambil contoh tabung yang hanya memiliki 1 tempat keluar seperti misalkan tabung bola tenis (kalau beli di supermarket beli bola tenis yang 1 tabung memiliki isi 3) hanya bisa dikeluarkan dari one side saja. Itulah konsep dari stacking.
Dalam stacking ada yang dimaksud dengan Top. Yang digunakan untuk mengidentifikasikan parameter yang ada di atas.  Contoh yang sering digunakan adalah Tower Of Hanoi, dimana untuk menyelesaikan masalah tower of hanoi, yang di keluarkan dari tiang masing masing adalah balok yang ada di paling atas.

Dalam Stack ada 3 macam operasi: push (untuk menambahkan item ke dalam Top of the stack), pop (untuk menghapus item yang ada di Top). dan Top itu sendiri (untuk menunjuk item mana yang ada dipuncak / diatas).


Queue : Memiliki konsep FIFO (First In First Out) dan LILO (Last in Last Out). Dimana benda yang masuk pertama kali pasti akan keluar terlebih dahulu. Contohnya bila kita sedang mengantri di kasir, orang yang pertama kali mengantri pasti akan keluar terlebih dahulu, First come first serve then out!
Istilah - istilah dalam Queue:

• Front : Tempat dimana data pertama akan diletakkan.
• Rear : Tempat untuk menentukan berapa banyak jumlah data yang dimasukkan.
• Kita juga mengenal instilah Dequeue dan Enqueue. 
• Dequeue : Melepaskan front, atau mendelete data atau biasa juga disebut pop.
• Enqueue : Memasukkan data baru.

Bila kita akan mendelete data, maka indikator Front akan mundur. Dan bila kita memasukkan data, maka indikator rear yang akan mundur.

Pada pertemuan ini kita juga membahasa mengenai postfix, prefix, dan infix, Seperti yang sudah dibicarakan pada pertemuan sebelumnya.
Lalu kita juga diperkenalkan dengan DFS (Depth First Search) dan BFS.

DFS (Depth First Search)

DFS adalah sebuah algoritma untuk mentranvers dan mencari data dalam tree dan graph. DFS biasanya digabungkan dengan cara rekursif.

Algorithma:

Prepare an empty stack

Push source/root into stack

Mark source/root

While stack is not empty

  Pop an item from stack into P

  For each node X adjacent with P

  If X is not marked

  Mark X

  Push X into stack

Nama : Dickson S.
NIM : 1701291283
www.binus.ac.id || www.skyconnectiva.com

Pertemuan ke-4


Dalam pertemuan kali ini, kami diajarkan mengenai "Introduction to Tree, Binary Tree and Expression Tree".

Tree : adalah koleksi dari 1 atau lebih node. (seperti yang di tunjukan dalam gambar).

Note : Dalam tree ada yang disebut sebagai root dan ada juga yg disebut sebagai leave.

Root : Adalah node yang berada pada yang paling atas atau yang paling utama. Dalam contoh gambar berikut, rootnya adalah 2.

Leaf : Adalah node yang berada pada yang paling bawah dimana ia sudah tidak beranak cucu atau memilik cabang lagi. Leave pada gambar berikut adalah 2,5,11 dan 4.

Ada juga yang disebut dengan Level. Dimana setiap Tingkat memiliki level tertentu apa bila berada dalam baris yg sama. Contohnya:

• Level 1 : 2 (karena berada dalam baris pertama dan di baris tsb hanya ada angka 2).
• Level 2 : 7 dan 5.
• Level 3 : 2 , 6, dan 9.
• Level 4 : 5, 11, dan 4.

Tree juga sering disebut seperti silsilah keluarga, contohnya Orangtua (Parent) dari angka 7 dan 5 adalah 2. Anak (Child) dari angka 6 adalah 5 dan 11, dan seterusnya.

Binary Tree :
Binary Tree adalah struktur dari Tree yang setiap nodenya hanya boleh memiliki kurang dari 2 anak dari rootnya sampai leaf. Biasanya 2 anak cabang tersebut dibedakan menjadi bagian kiri dan bagian kanan.

Tipe Tipe Binary Tree:

• Perfect Binary Tree : Setiap bagian dari tree tsb memiliki depth yang sama. 

•  Complete Binary Tree : Setiap bagian memiliki depth yg sama kecuali pada bagian akhir akan ada kosong 1 node.

• Skewed Binary : adalah Binary yang setiap bagiannya hanya memiliki 1 anak saja.
• Balanced Binary Tree : Balanced ("seimbang") maka setiap bagian node dari binary tree tsb memiliki nilai maksimum node lebih besar 2^k dari level sebelumnya. 

Representasi dalam Binary Tree:

• Index Left Child adalah 2p + 1, dimana p adalah indeks parent.
• Index Right Child adalah 2p + 2.
• Index Parent adalah (p-1)/2.

Dalam Tree ada juga proses yang disebut sebagai prefix, postfix, dan infix.
Prefix : adalah bentuk equation dimana letak operator berada di depan.
Postfix : adalah bentuk equation dimana letak operator berada di belakang.
Infix : adalah bentuk equation dimana letak operator berada di tengah.

Contoh : 2+a+b/2 * 3

    Prefix : + 2 + a * / b 2 3

    Profix : 2 a b 2 / 3 * + + 

Contoh : a + (b/2) * 3 / 2

    Prefix : + a / * / b 2 3 2 

    Profix : a b 2 / 3 * 2 / +

*Note : (Seperti matematika dasar, operator bagi dilakukan lebih dahulu lalu  perkalian, lalu penjumlahan, apa bila ada parentheses () maka equation itu dihitung lebih dahulu).

Dimana:

• Infix : Left V Right.
• Prefix : V Left Right.
• Postfix Left Right V.

Tugas : C / A * 2 + 3 / 12 + 21
     Prefix : + + / * / C A 2 3 12 21 
     PostFix : C A 2 3 1 2 21 / * / + +


Nama : Dickson Saputra.
NIM : 1701291283

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

Pada pertemuan ke-3

Kami kedatangan tamu dalam bimbingan belajar Struktur data. Ia adalah Okky Pribadi. Bpk. Okky sendiri merupakan salah satu alumni universitas Binus. Sebagai lulusan Sistem Informasi. Namun, ia merupakan salah satu programmer yg bekerja di berbagai bidang seperti web designing untuk kostumernya dalam bidang entertainment maupun media. Beliau memiliki working experience yang banyak sehingga memungkinkannya untuk semakin maju setiap tahunnya. Mulai dari web designing untuk konsumer dan produsen.
Ia berposisi dalam bidang freelancing programmer, karena memiliki keuntungan yang lebih banyak, dan memiliki sisi positifnya yang bisa menguntungkan profit dibandingkan bekerja dikantoran.

Melalui pertemuan itu, kita bisa belajar banyak dari saran-saran yang diberikan seperti mempelajari bahasa bahasa yang sering digunakan menurut beliau sendiri bahasa yang ia tekuni adalah Java dan C# dalam web dan gaming. Pertemuan seperti ini memotivasi kita untuk belajar lebih tekun. Dan kita bisa lebih dipersiapkan saat kita lulus nanti agar tetap di jalur yang sama dengan jurusan Teknik Informatika.

Nama : Dickson S.
NIM : 1701291283

Linked List

Bahasa Melayu untuk Linked List = Senarai Berantai


Linked List dibedakan menjadi Single Linked List(Memiliki 1 node), Double Linked List(Memiliki 2 node, seperti next atau previous), Multiple Linked List(Memiliki node lebih dari 2).
 
Single Linked List
 
Dibagi menjadi 3 Cara : Push Depan, Push Belakang, Push Tengah.
Dalam penggunaan Single Linked List, ada baiknya kita mengerti konsep penggunaan struct (dalam bahasa C) terlebih dahulu.
Selain itu, juga ada cara untuk menDelete data yang telah dimasukkan atau yang sudah ada dalam linked list, penghapusan tsb disebut sebagai POP.
Pop sendiri dibagi menjadi 2 macam : POP depan, dan POP belakang.







 

 *Notice: Pada bagian belakang node (Tail Node) selalu memiliki nilai NULL.

Push Depan : Yang dimaksud dengan push depan adalah jika user memasukkan data baru maka, data tersebut akan ditetapkan kedalam alamat current / *curr. Setelah itu alamat yg memiliki data tsb akan di push ke arah head. Sehingga head = curr. Yang awalnya berurutan melalui Head, Tail, Current. Saat di push ke depan menjadi Head Current Tail. (inti dari push depan : data head berada di depan, data yang ada di tail berada di belakang).

Berikut adalah contoh Implementasi dari Push Depan dalam bahasa C:

struct Mahasiswa{
        char nama[25];
        struct Mahasiswa *next;
};

struct Mahasiswa *curr;
*curr = (struct Mahasiswa *) malloc (sizeof(struct Mahasiswa);
strcpy (curr -> nama, nama);
curr -> next = head;
head=curr;


Push Belakang: Memiliki konsep yang sama dengan push depan, namun dalam rangka Push Belakang, pada bagian Tail yang akan di push sehingga pada akhirnya yang berawal dengan posisi Head Current Tail. Saat disisipkan data baru menjadi Current (dalam Node tersendiri), Head (dengan Node Tersendiri), Tail(dengan Node tersendiri). Saat diimplementasikan Push belakang, posisinya akan menjadi -> Head & Current (dalam 1 node!), node, dengan Tail (node sendiri dengan terakhirnya diisikan NULL).

Berikut adalah contoh Implementasi dari Push Belakang dalam bahasa C:

if (head == NULL){
     head = tail = curr;
}else{
     tail -> next = curr;
     tail = curr;
}
tail -> next = NULL;
} 

POP Depan : Dalam menghapus depan, kita harus memastikan bahwa data yang sudah dimasukkan yang tadinya berada di current, sekarang berada pada head (depan).

void popdepan(){
      if (head == tail){
            head = tail = NULL;
            free (curr); //penghapusan dalam link list dsb sebagai FREE.
      }else{
            head = head ->next;
            free (curr);
      }
}

POP Belakang: Dalam menghapus Belakang, kita harus memastikan bahwa data yang sudah dimasukkan yang tadinya berada di current, sekarang berada pada head (depan).

void popbelakang(){
      struct Mahasiswa *curr = head;
      if (head == tail){
            head = tail = NULL;
            free (curr);
      }else{
             while(curr -> next != tail){
             curr = curr -> next;
      }   tail = curr;
          free (curr -> next);
          tail -> next = NULL;
      }
}