Session 5 (Stack , Queue dan Implementasi)

Stack adalah tumpukan dari suatu data.

Dalam kehidupan stack bisa dinyatakan seperti piring yg memiliki konsep

LIFO (Last in First Out) : data yang terakir masuk akan pertama kali keluar

FILO (First in Last Out) : data yang pertama kali masuk akan keluar terakir

Dalam stack ada 2 variabel ;

TOP : untuk menunjukan data teratas pada stack

MAX : untuk menujukan jumlah data pada stack

Jika Top = NULL maka stack kosong

jika Top = Max - 1 berarti stack penuh.

Pada stack, jika menambah data maka TOP akan naik dan jika menghapus data  TOP akan turun.

Operasi – operasi pada Stack (Tumpukan)

Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :

1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.

2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.

3. Clear : digunakan untuk mengosongkan Stack.

4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.

5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.

6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.

7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

Macam – macam Stack

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

2. Double Stack dengan Array

Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

QUEUE (ANTRIAN)

A. Definisi Queue (Antrian)

          Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

          Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

         Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

B. Operasi-operasi pada Queue

1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.

2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

3. EnQueue : berfungsi memasukkan data kedalam antrian.

4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.

5. Clear : Menghapus seluruh Antrian

6. IsEmpty : memeriksa apakah antrian kosong

7. IsFull : memeriksa apakah antrian penuh.

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

DFS : pencarian solusi dengan menelusuri lebih dahulu akar - akarnya,jika tidak ketemu pencarian akan dipindah ke node yang lain pada level yang sama

Keuntungan menggunakan metode DFS:

- Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

- Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi.

Kekurangan dari metode DFS ini yaitu:

- Memungkinkan tidak ditemukannya tujuan yang diharapakan.

- Hanya akan menemukan 1 solusi pada setiap pencarian.

BFS : pencarian solusi dimana semua node pada level n akan ditelusuri terlebih dahulu.

Keuntungan yang didapat apabila menggunakan metode BFS ini yaitu:

- Tidak akan menemui jalan buntu.

- Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.

- Jika ada satu solusi maka bread-first search akan menemukannya.

Dan kekurangan dari metode BFS ini yaitu:

- Membutuhkan memori yang cukup banyak.

- Membutuhkan waktu yang cukup lama.

Nama: Ardi Yuriansyah

Nim: 1701290816

Kelas: 02PFT

www.binus.ac.id

session 4 (Introduction to Tree, Binary Tree and Expression Tree)

Tree memiliki 8 konsep, yaitu:

- Node di bagian atas disebut sebagai root.

- Garis yang menghubungkan orang tua anak itu adalah edge.

- Node yang tidak mempunyai anak adalah leaf.

- Node yang memiliki orang tua yang sama di sebut sibling.

- Degree dari node adalah banyak sub node dari degree tersebut.

- Height/Depth adalah tingkat maksimum dari node dalam sebuah pohon.

- Jika ada garis yang menghubungkan P untuk Q, lalu p disebut leluhur-Q, dan q adalah keturunan dari  P.

- Node paling atas disebut = Root

- Line nya disebut = Edge

- Node yang tidak punya anak disebut = Leaf

- Node yang punya atas nya sama disebut = Sibling

Binary Tree Concept

- Pohon biner adalah sebuah struktur data pohon berakar di mana setiap node telah di paling dua anak-anak.

- Kedua-dua anak biasanya dibedakan kiri dan kanan anak anak.

- Node yang tidak memiliki anak disebut leaf.

Berikut adalah tipe - tipe pada binary tree :

1. Perfect Binary Tree : dimana setiap tingkatan memiliki kedalaman yang sama.

2. Complete binary tree : pohon yang memiliki tipe yang sempurna.tetapi kesempurnaan tidak seharusnya memiliki kelengkapan.!

3. Skewed Binary Tree : setiap node/simpul yang memiliki 1 anak/hanya berakar 1

Ada beberapa peraturan di dalam sebuah binary tree yaitu:

- Tingkat 0 : max nodenya hanya 1

- Tingkat 1 : max nodenya hanya 2

- Tingkat 2 : max nodenya hanya 4

- Tingkat 3 : max nodenya hanya 8

- Dalam beberapa literatur, tingkat pohon biner dimulai dengan 1 (root).

- Rumus binary tree yaitu 2k.

* EXPRESSION TREE CONCEPT

- Prefix = *+ab/-cde

- Postfix = ab+cd-e/*

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

 contoh soal

1.)  a+(b/2)*3/2

      - Prefix = +a/*/b232

      - Postfix = ab2/3*2/

2.) 2+a+(b/2)*3

      - Prefix = +2+a*/b23

      - Postfix = 2ab2/3*++

cara mencari nya dengan rumus ( V=cetak , L=kiri , R=kanan )

- LVR = infix

- LRV = postfix

- VLR = prefix

*SOAL cari Prefix,Postfix, dan Infix

c/a*2+3/12+21

Jawaban

- Prefix = +*/ca2+/31221

- Postfix = ca/2*312/21++

- Infix = c/a*2+3/12+21

Nama: Ardi Yuriansyah

Nim: 1701290816

Kelas: 0PFT

www.binus.ac.id

Data Structur/Array

Pada pertemuan kemarin, kelas besar kami kedatangan dosen tamu yang bernama Okky Pribadi. Beliau lulusan dari Bina Nusantara (BINUS). Di pertemuan minggu lalu, beliau menceritakan dan memotivasi kami agar kami lebih menyukai jurusan kami (Teknik Informatika). 

Beliau adalah seorang Freelance Programmer. Beliau lebih menyukai pekerjaan Freelance Programmer ketimbang pekerjaan kantoran, alasannya cukup menyenangkan karena pekerjaan Freelance Programmer penghasilannya lebih banyak dari pada kantoran.

pelajaran yang saya ambil dari pertemuan minggu lalu, apabila kita niat untuk melaksanakan sesuatu, pasti hasilnya akan sempurna dan apabila kita memiliki bakat yang tersembunyi mengapa kita tidak mencoba untuk mengembangkan bakat tersebut yang dapat berguna untuk orang lain.

Nama: Ardi Yuriansyah
Nim : 1701290816

www.binus.ac.id

Single Linked List

Linked list adalah salah satu bentuk struktur data, yang berisi sekumpulan data (node) yang tersusun secara sekuensial saling sambung menyambung  dinamis dan terbatas.

- Linked List sering disebut juga Senarai Berantai
- Linked List saling terhubung dengan bantuan variabel pointer
- Masing-masing data dalam Linked List disebut dengan node (simpul) yang
menempati alokasi memori secara dinamis dan biasanya berupa struct
yang terdiri dari beberapa field. 

Single Linked List adalah sebuah LINKED LIST yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LINKED LIST, suatu daftar isi yang saling berhubungan.

Ilustrasi single LINKED LIST:

Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LINKED LIST. Bila dalam single LINKED LIST pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

Ada 2 Tipe Single Linked List yaitu:

·         Single Linked List Circular

·         Single Linked List Non Circular

1.     Single Linked List Circular

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,
maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Pengertian:
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi Single Linked List Circular
- Setiap node pada linked list mempunyai field yang berisi pointer ke node
  berikutnya, dan juga memiliki field yang berisi data.
- Pada akhir linked list, node terakhir akan menunjuk ke node terdepan
  sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi
  ke head.

PEMBUATAN SINGLE LINKED LIST CIRCULAR
Deklarasi node
Dibuat dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};

Penjelasan:
- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data
  bertipe integer dan field next yang bertipe pointer dari TNode
- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari
  TNode yang berguna sebagai kepala linked list.

Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

SINGLE LINKED LIST CIRCULAR MENGGUNAKAN HEAD
- Dibutuhkan satu buah variabel pointer: head
- Head akan selalu menunjuk pada node pertama

Deklarasi Pointer Penunjuk Kepala Single Linked List
Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju,
melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:

TNode *head;

Fungsi Inisialisasi Single LinkedList
void init(){
head = NULL;
}

Function untuk mengetahui kosong tidaknya Single LinkedList
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}

PENAMBAHAN DATA
Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat
pertama kali (data masih kosong), maka penambahan data dilakukan pada
head nya.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head
akan menunjuk pada data baru tersebut sehingga head akan tetap selalu
menjadi data terdepan. Untuk menghubungkan node terakhir dengan node
terdepan dibutuhkan pointer bantu. 

Nama : Ardi Yuriansyah

Nim : 1701290816

www.binus.ac.id