Stack & Implementation

Stack
Stack bisa dibilang sebagai array linear karena stack berupa tumpukan. Istilah dalam Stack yaitu LIFO ( Last In First Out) atau FILO (First In Last Out). Contoh dalam kehidupan sehari - hari seperti tumpukan buku atau piring.
Dalam Stack terdapat 2 variabel, yaitu TOP dan MAX.
Top digunakan untuk menunjukkan elemen paling atas dari Stack. sedangkan Max untuk menunjukkan jumlah data dalam Stack.
Jika Top = NULL maka berarti Stack kosong, jika Top = Max - 1 berarti Stack penuh.
Pada Stack, jika menambah data maka Top akan naik, tetapi jika ada hapus data maka Top akan turun.
Beberapa operasi pada Stack :
- is_empty(); = untuk mengecek stack kosong
- is_full(); = untuk mengecek stack penuh
- top(); atau peek(); = untuk kembali ke index top
- push(x); = untuk menambah x pada Top didalam stack
- pop(); = untuk menghapus data dari Top dalam stack

Representasi Stack dalam array:

Representasi Stack dalam Linked List:

Dalam Linked Stack, setiap node memiliki 2 bagian:

- 1 bagian untuk menyimpan data

- 1 bagiannya lagi untuk menyimpan alamat dari node selanjutnya

Start pointer pada linked list digunakan sebagai Top, dan semua penambahan serta pengurangan data dilakukan di node yang ditunjuk oleh TOP.

Code untuk Stack: 

Untuk menambah data :

      struct stack *push (struct stack *top, int val){

         struct stack *ptr;

         ptr = (struct stack*) malloc (sizeof(struct stack*));

         ptr -> data = val;

         if (top == NULL){

              top = ptr;

              top -> next = NULL;

         } else {

              ptr -> next = top;

              top = ptr;

         }

         return top;

      }

Untuk menghapus data :

      struct stack *pop (struct stack *top){

         struct stack *ptr;

         ptr = top;

         if (top == NULL){

              printf(“\n STACK UNDERFLOW”);

         } else {

              top = top -> next;

              printf(“\nThe deleted value: %d”, ptr -> data);

              free(ptr);

         }

         return top;

      }

Untuk menampilkan data :

      struct stack *display(struct stack *top){

         struct stack *ptr;

         ptr = top;

         if (top == NULL){

              printf(“\n STACK IS EMPTY”);

         } else {

              while(ptr != NULL){

                  printf(“\n%d”, ptr -> data);

                  ptr = ptr -> next;

              } 

         }

         return top;

      }

Notasi Infix, Prefix, dan Infix

      

Prefix : operator ditulis sebelum operand

Infix : operator ditulis diantara operand

Postfix : operator ditulis setelah operand

Kita butuh notasi Prefix dan Postfix karena notasinya tidak membutuhkan kurung () untuk menghitungnya.

Prefix dan Postfix lebih mudah dihitung / dievaluasi oleh komputer.

Depth First Search (DFS) dan Breadth First Search (BFS)

Depth First Search merupakan algoritma untuk mencari didalam tree atau graph. DFS dimulai dari root hingga kebawah. Breadh First Search juga merupakan algoritma untuk mencari, bedanya dengan DFS, BFS mencari dengan menyebar kiri kekanan, sedangkan DFS mencari lurus hingga kedalaman.

Contoh DFS yang benar :

Contoh BFS :

www.binus.ac.id

www.skyconnectiva.com

Tree

Tree
Tree merupakan kumpulan dari 1 atau lebih node.

Dalam Tree,
- node paling atas disebut Root
- garis yang menghubungkan parent (orang tua) ke child (anak) disebut Edge
- node yang tidak memiliki children (anak) disebut Leaf
- node yang memiliki parent yang sama disebut Sibling
- degree dari node adalah total subtree dari node tersebut
- ketinggian / kedalaman suatu tree merupakan degree maksimum dari node dalam tree
- jika ada edge yang menghubungkan P ke Q maka P disebut Ancestor dari Q, sedangkan Q disebut Descendant dari P

Contoh Tree beserta keterangannya:
             
                

Keterangan :
- Degree dari Tree tersebut adalah 3
- Degree dari B adalah 2
- Height (ketinggian) = 3
- Parent (orang tua) dari C = A
- Children (anak) dari A = B, C, D
- Siblings (saudara) dari E = F
- Ancestor (leluhur) dari F = A, B
- Descendant (keturunan) dari B = E, F
- Root = A
- Leaf = E, F, G

Binary Tree
Binary Tree adalah rooted tree data structure dimana setiap node paling banyak memiliki 2 child.
2 child ini biasanya dibedakan menjadi left child dan right child.
Perbedaan Binary Tree dengan Binary Search Tree :

Binary Tree boleh tidak urut, jadi antara left child, parent dan right child nilainya bebas tidak harus urut.
Tetapi pada Binary Search Tree harus urut, left child harus lebih kecil dari parent dan right child harus lebih besar dari parentnya.

Selain Binary, terdapat juga Unary dan Ternary.

Jenis - jenis Binary Tree:

- Perfect Biinary Tree : Binary Tree dimana setiap level punya node yang sama

- Complete Binary Tree : Binary Tree yang disalah satu levelnya boleh ada yang belum terisi, Perfect Binary Tree merupakan Complete Binary Tree

- Skewed Binary Tree : Binary Tree dimana setiap node memiliki paling banyak 1 child

Binary Tree dalam array:

               

Keterangan:

- Index pada array menunjukkan nomor node

- Index 0 adalah node Root

- Index left child adalah 2p + 1 dimana p adalah index parent

- Index right child adalah 2p + 2

- Index parent adalah (p - 1) / 2

Binary Tree dalam Linked List:

        struct node {

            int data;

            struct node *left;

            struct node *right;

            struct node *parent;

         };

         struct node *root = NULL;

Prefix, Postfix, Infix

                       

Prefix  : *+ab/-cde

Postfix  : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Cara mengubah Infix, Prefix dan Postfix.

Infix -> LVR

Prefix -> LRV

Postfix -> VLR

ingat KaBaTaKu (Kali Bagi Tambah Kurang)

contoh:

             2 + a + (b / 2) * 3

maka:

prefix : + 2 + a * / b 2 3

postfix : 2 a b 2 / 3 * + *

tugas :      c / a * 2 + 3 / 12 + 21

prefix :     + / + / c * a 2 3 12 21

postfix :    c a 2  * / 3 + 12 / 21 +

Implementasi Prefix dalam Linked List:

     void prefix(struct tnode *curr) {

        printf( “%c “, curr->chr );

        if ( curr->left  != 0 ) prefix(curr->left);

        if ( curr->right != 0 ) prefix(curr->right);
     }

Postfix :

     void postfix(struct tnode *curr) {

        if ( curr->left  != 0 ) postfix(curr->left);

        if ( curr->right != 0 ) postfix(curr->right);
        printf( “%c“, curr->chr );

     }

Infix:

     void infix(struct tnode *curr) {

        if ( curr->left  != 0 ) infix(curr->left);

        printf( “%c“, curr->chr );

        if ( curr->right != 0 ) infix(curr->right);
     }

www.binus.ac.id

www.skyconnectiva.com

Session 3 (Dosen Tamu) - Algoritma dan Struktur Data

Algoritma
Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria.

Struktur Data
Struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.



Array
Array merupakan kumpulan elemen data yang sama karena elemen data tersebut harus memiliki tipe data yang sama (homogen). 

Linked List
Linked List merupakan struktur data yang dinais dimana elemennya dapat ditambah atau dihapus kapan saja karena dijalankan saat run-time. Setiap elemen pada Linked List disebut node (titik). Keuntungan dari Linked List adalah lebih menghemat memori karena elemen yang tersedia sesuai kebutuhan yang ingin dipakai saja.



Perbedaan Array dan Linked List

Dosen Tamu
Pada Senin, 10 Maret 2014 kelas besar Struktur Data 42PGT kedatangan dosen tamu bernama Ongky Pribadi, S.Kom. (CMIIW). Beliau bekerja sebagai programmer freelance dan dulunya lulusan Sistem Informasi. Beliau memilih untuk tidak bekerja dikantoran dan lebih memilih freelance. Saat ini beliau telah membuat banyak aplikasi untuk berbagai perusahaan dan beliau biasanya melakukan maintenance jika diperlukan. Misalnya dengan program yang hanya memerlukan 2 modul bisa berharga 12 juta untuk membuatnya, sedangkan untuk maintenance bisa mencapai 300ribu perdatang. Intinya bekerja dibagian teknologi seperti programmer merupakan pekerjaan yang memberikan gaji yang cukup besar.

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

Linked List Implementation

Linked List

Linked List merupakan struktur data yang dinamis dimana elemennya dapat ditambah atau dihapus kapan saja karena dijalankan saat run-time, tidak seperti array yang bila memesan memori sebanyak 5, maka bila diisi lebih dari itu akan error dan array dijalankan pada saat compile-time.
Setiap elemen pada Linked List disebut node (titik).
Keuntungan dari Linked List ini yaitu lebih menghemat memori karena elemen tersedia sesuai kebutuhan yang ingin dipakai saja.
Linked List dibedakan menjadi beberapa jenis, seperti :

1. Single Linked List
2. Double Linked List
3. Circular Single Linked List
4. Circular Double Linked List

Single Linked List

Single Linked List berarti hanya menggunakan single / 1 pointer saja pada Linked Listnya.

Dalam Single Linked List terdapat Push Depan dan Push Belakang untuk menambah, sedangkan Pop Depan, Pop Belakang untuk menghapus. Pada Single Linked List hanya terdapat -> (next).

            

             

Contoh Push Depan :

void pushDepan(int number)
{
    curr = (struct data*)malloc(sizeof(struct data));
    curr->number = number;
    curr->next = NULL;

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

Contoh Push Belakang :

void pushBelakang(int number)
{
    curr = (struct data*)malloc(sizeof(struct data));
    curr->number = number;
    curr->next = NULL;

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

Contoh Pop Depan :

void popDepan()
{
    if(head==NULL)
    {
        printf("data not found");
        getchar();
        head = tail = curr = NULL;
    }
    else
    {
        curr=head;
        if(head==tail)
        {
            head = tail = NULL;
        }
        else
        {
            head = head->next;
            free(curr);
        }                    
    }
}

Contoh Pop Belakang :

void popBelakang()
{
    if(head==NULL)
    {
        printf("data not found");
        getchar();
        head = tail = curr = NULL;
    }
    else
    {
        curr = head;
        if (head==tail)
            head = tail = NULL;
        else
        {
            while (curr->next!=tail)
                curr = curr->next;
                tail = curr;
                curr = curr->next;
                tail->next = NULL;
        }
        free(curr);
    }
}

Double Linked List

Double Linked List merupakan Linked List yang berpointer ganda (2). Pada Double Linked List terdapat -> (next) dan <- (prev).

                        

Circular Single Linked List

Pada Circular Single Linked List, node terakhir berisi pointer yang menunjuk ke node pertama dan tidak ada yang memuat nilai NULL pada list. Pada Linked List ini hanya menggunakan satu pointer (next).

                       

Circular Double Linked List

Pada Circular Double Linked List, sama saja seperti Circular Single Linked List, hanya pada Linked List ini menggunakan pointer ganda (prev dan next).

                         

www.binus.ac.id

www.skyconnectiva.com