Stack, Queue & Tree [PDF]

Citation preview

Nama : Fadia Alissafitri NIM



: 2010511046



Kelas : A STRUKTUR DATA RANGKUMAN PERTEMUAN 5-7



1. Stack Definisi stack secara ADT (Abstract Data Type) adalah sebuah struktur data linear atau list di mana data hanya bisa masuk dan keluar dari satu ujung yang disebut “top”. Proses pemasukkan dan pengeluaran data ini mengikuti prinsip LIFO (Last-InFirst-Out) atau FILO (First-In-Last-Out). Contoh stack dalam bentuk fisik adalah sebuah tumpukan piring atau sebuah wadah berisi bola tenis.







Operasi dalam stack a. Push: memasukkan data ke dalam stack - Jika stack penuh, akan error - Jika tidak, pointer top akan di increment - Sebuah nilai baru akan dimasukkan ke posisi top, nilai tersebut menjadi top baru



b. Pop: mengeluarkan data dari stack



-



Jika stack kosong, akan error Jika tidak, data yang ada di top akan diambil dan dikeluarkan dari stack Top akan di decrement, data yang teratas sekarang menjadi top



c. Peek: mengembalikan data teratas dalam stack atau top d. IsEmpty: mengecek jika stack kosong. (jika benar mengembalikan true, jika salah false) e. IsFull: mengecek jika stack penuh Semua operasi di atas dijalankan secara Constant Time atau O(1)







Implementasi Stack dengan Array - Jika array kosong, maka posisi top akan berada di -1



-



Ketika ingin mendorong suatu nilai, maka push akan dipanggil dan top akan ber-increment ke index 0, lalu nilai dimasukkan



-



Proses push akan terus sama untuk nilai-nilai berikutnya







-



Jika ingin melakukan pop, maka top akan decrement 1, hingga sekarang posisi top berada di index 1 atau angka 10, namun data yang di pop tidak hilang



-



Jika ingin melakukan push lagi, maka top akan ber-increment dan data yang lama (5) akan ter-overwrite oleh data yang baru (7)



Implementasi Stack dengan Linked List Terdapat dua cara untuk menginsert atau delete elemen dari linked list: - Akhir list (tail)  waktu operasi O(n) - Awal list (head)  waktu operasi O(1) atau Constant Time Karena aturan stack menggunakan constant time, maka lebih baik menginsert atau delete data dari head. Bentuk umum linked list adalah seperti berikut:



-



-







Ketika melakukan push, akan dibuat node baru. Node baru berisi nilai dan alamat dari head node (top) saat itu Alamat dalam pointer head berubah menjadi alamat dari node baru dan node tersebut sekarang menjadi head node.



Ketika melakukan pop, link antara pointer head dan head node akan terputus dan head node terhapus Alamat dalam pointer head akan berubah kembali menjadi alamat dari node yang sekarang terdepan



Pengaplikasian Stack - Pemanggilan fungsi/rekursi - Evaluasi ekspresi - Backtracking (history call pada browser, undo pada editor) - Manajemen memori dan alokasi memori - Konversi bilangan desimal ke biner - Membalikkan urutan string



2. Infix, Prefix, dan Postfix Infix, Prefix, dan Postfix merupakan jenis-jenis notasi penulisan ekspresi aritmatika a. Infix: notasi dimana ekspresi ditulis dengan operator di antara operand Contoh: a + b + c b. Prefix: notasi dimana ekspresi ditulis dengan operator sebelum operand Contoh: + a + b c c. Postfix: notasi dimana ekspresi ditulis dengan operator setelah operand Contoh: a b c + +



Jika dalam satu ekspresi terdapat dua atau lebih operator yang sama, maka urutan pengerjeaanya mengikuti aturan presedensi. Berikut adalah prioritas pengerjaan operator: 1. Parentheses (tanda kurung)  ( ), [ ], { } 2. Exponents (eksponen)  ^ 3. Multiplication & Division (perkalian & pembagian)  *, / (dikerjakan dari kiri ke kanan) 4. Addition & Substraction (penjumlahan & pengurangan)  +, - (dikerjakan dari kiri ke kanan) 



Konversi Infix, Prefix, dan Postfix Infix a+b*c (a + b) * c a * (b + c) a/b+c/d (a + b) * (c + d) ((a + b) * c) – d







Prefix +a*bc *+abc *a+bc +/ab/cd *+ab+cd -*+abcd



Postfix abc*+ ab+c* abc+* ab/cd/+ ab+cd+* ab+c*d-



Evaluasi Postfix menggunakan Stack Dalam parsing postfix, kita membaca notasi dari kiri ke kanan. Misalkan terdapat stack kosong, dan stack tersebut akan diisi untuk menampung operand. Saat parsing, setiap bertemu dengan operand, operand tersebut akan di push ke dalam stack. Ketika bertemu dengan operator, maka dua operand terakhir dalam stack akan di pop, lalu dilakukan operasi matematika terhadap operator tersebut.



Hasil dari operasi tersebut akan dimasukkan kembali ke dalam stack, lalu operand berikutnya dalam stack juga dimasukkan. Proses ini akan berulang sampai akhir ekspresi sehingga jawaban didapatkan.







Evaluasi Prefix menggunakan Stack Proses parsing prefix hampir sama dengan postfix, hanya saja kita membaca dari kanan ke kiri







Konversi Infix ke Postfix menggunakan Stack Algoritma: 1. Buat sebuah stack 2. Baca ekspresi infix dari kiri ke kanan (looping) 3. If : karakter yang terbaca adalah operand, masukkan ke variable penampung string postfix 4. Else : karakter adalah operator :



5. 6. 7. 8.



Jika stack tidak kosong atau operator yang menjadi top dalam stack mempunyai prioritas lebih tinggi, maka semua operator dalam stack akan di pop dan dimasukkan ke dalam string postfix. Jika tidak keduanya, operator di push ke dalam stack If : karakter adalah ‘(‘, push ke dalam stack If : karakter adalah ‘)’, pop semua operator dalam stack dan masukkan ke string hingga bertemu dengan ‘(‘, lalu hilangkan kedua tanda kurung Setelah loop selesai, pop sisa-sisa operator dalam stack dan masukkan ke string Cetak string postfix



3. Queue Queue merupakan sebuah struktur data linear dimana operasi dijalankan sesuai urutan terentu. Perbedaannya dengan stack adalah dalam queue data dimasukkan dari satu ujung dan dikeluarkan dari ujung yang satu lagi. Kedua ujung tersebut adalah front dan rear. Ujung yang di depan disebut front sedangkan ujung yang di belakang disebut rear. Sistem yang digunakan dalam queue adalah FIFO (First-In-First-Out), dimana data yang pertama masuk juga merupakan data yang pertama keluar, seperti antrian. Contoh pengaplikasian nyata queue adalah network printer, dimana printer akan melakukan instruksi satu persatu sesuai dengan urutan. 



Operasi dalam Queue a. Enqueue: merupakan operasi yang fungsinya setara dengan operasi push pada stack, yaitu mendorong/memasukkan data ke queue.



b. Dequeue: berfungsi untuk mengeluarkan data dari queue, setara dengan operasi pop pada stack.



c. Front: mengembalikan data yang ada di front, setara dengan operasi peek dalam stack. d. Rear: mengembalikan data yang ada di rear. e. IsEmpty: mengecek jika queue kosong atau tidak. f. IsFull: mengecek jika queue penuh atau tidak.



Sama seperti stack, semua operasi di atas dijalankan pada waktu constant time atau O(1). Jika hanya terdapat satu data pada queue, maka data tersebut merupakan front dan juga rear.







Implementasi Queue menggunakan Array Katakan kita mempunyai sebuah array berukuran 10. Front dan rear bisa ditempatkan di mana saja, tidak harus mulai dari 0. Misalkan front ada di index 2 dan rear di index 6. Jika ingin melakukan enqueue, maka posisi rear akan diincrement 1, sekarang rear berada di index 7, lalu kita memasukkan data pada index tersebut.



Jika ingin melakukan dequeue, kita bisa cukup melakukan increment pada front sehingga posisi front sekarang ada di index 3, tak peduli apa yang ada di dalam index 2 karena isi queue hanya mencakupi apa yang ada di front sampai dengan rear.



Jika array sudah full, kita bisa membuat array yang lebih besar dan mengkopi semua data ke array yang lebih besar tersebut. Jika ada kasus dimana array sudah mencapai index terakhir, tetapi masih ada sisa array yang kosong di depan index front, maka kita tidak bisa lagi meng-enqueue data, karena kita tidak dapat melakukan enqueue pada front.



Untuk mengatasi hal ini, kita dapat menggunakan konsep Circular Array. Circular array divisualisasikan sebagai array berbentuk lingkaran.



Untuk melakukan enqueue, terlebih dahulu dicek jika (rear+1)%N == front. N merupakan size dari array. Maka akan terjadi seperti gambar di bawab. Jika hal ini terjadi, itu berarti array sudah penuh dan tidak bisa di enqueue lagi.



Namun, lain halnya jika array masih ada sisa yang kosong. Misalkan array terisi dari index 2 sampai 9, dan index 0 dan 1 masih kosong. Maka bisa dilakukan enqueue dengan cara (rear+1)%N. Hasilnya menjadi 10%10 = 0. Kini, rear berada pada index 0 dan data baru akan dimasukkan ke index 0.



Untuk melakukan dequeue, maka yang perlu dilakukan adalah posisi front dijadikan sebagai (front+1)%N. Disini front berada pada index 2, jadi (2+1)%N menghasilkan 3. Kini front sekarang berada pada index 3 dan index yang kosong sekarang berupa index 1 dan 2.







Implementasi Queue menggunakan Linked List Karena insert/delete data dapar dilakukan dari dua ujung, maka jika kita melakukan enqueue pada head node, dequeue kita lakukan pada tail. Jika dequeue dilakukan pada head, maka enqueue dilakukan pada tail.



Namun, akibat dari insert/delete dari tail adalah membutuhkan waktu operasi O(n). Untuk menjadikan waktu operasi O(n), katakana bahwa head adalah front dan tail adalah rear, pada tail harus dibuat sebuah pointer rear yang menampung address dari node. Jadi jika ingin melakukan enqueue dan dequeue, kedua pointer pada head dan tail harus diupdate.



Saat melakukan dequeue, maka address pada pointer rear akan berubah menjadi address dari node baru. Dengan car aini, maka kedua operasi enqueue dan dequeue menggunakan waktu constant time.



4. Tree Tree adalah sebuah struktur data hierarki nonlinier yang terdiri atas node yang terhubung oleh sebuah edge (link antara dua node). Contoh tree dalam dunia nyata adalah struktur pengurus sebuah organisasi.



Pada tree, node yang teratas disebut dengan root dan memiliki hierarki tertinggi, katakanlah setara dengan CEO dalam sebuah organisasi. Berikut gambaran umum struktur data tree beserta komponennya.



Terdapat beberapa istilah pada tree: a. Root: node paling atas b. Parent: atasan dari satu atau lebih node. Dalam contoh berarti, D adalah parent dari H dan I c. Child: bawahan dari suatu node. Dalam contoh berarti H adalah child dari D d. Sibling: dua atau lebih node yang memiliki parent yang sama. F dan G merupakan sibling karena memiliki parent yang sama yaitu C e. Leaf: node yang tidak memiliki child f. Sub-tree: tree dari root/node. Disini berarti A mempunyai 2 sub-tree yaitu B dan C. Lalu B mempunyai 2 sub-tree yaitu D dan E Height (panjang) dan Depth (kedalaman) dari sebuah tree diukur dari jumlah edge. Height merupakan jumlah edge pada jalur terpanjang dari suatu node sampai leaf node.Sedangkan depth merupakan jumlah edge dari root sampai node itu sendiri. Berikut ilustrasi dari height dan depth.







Binary Tree Binary tree adalah struktur data tree yang memiliki syarat khusus dimana setiap node dapat memiliki maksimal dua anak.



Jika diilustrasikan dalam linked list, maka tiap node memiliki tiga buah field, dua berisi address dari anak kiri dan anak kanan, satu berisi data.



Binary tree memiliki beberapa jenis: a. Strict/Proper Binary Tree: Setiap node dapat memiliki 2 atau 0 anak



b. Complete Binary Tree: Semua level kecuali yang paling bawah harus penuh dan semua node harus sekiri mungkin. Maksud dari ini adalah semua node memiliki level tertentu. Root node berada di level 0, berarti node yang dibawahnya berada di level 1, begitupun seterusnya. Dalam complete binary tree, setiap level harus terisi penuh. Ketentuan



suatu level terisi penuh adalah jumlah maksimum node pada level i adalah 2i. Jadi, misalkan pada level 2, maksimum node yang dibutuhkan adalah 22 = 4. Jika pada level terbawah tidak terisi penuh, tidak masalah, namun node harus berada pada sisi kiri, alias tida boleh ada bagian di kiri yang kosong.



c. Perfect Binary Tree: Tipe binary tree dimana setiap node mmiliki dua anak dan semua leaf node berada pada level yang sama.



d. Balanced Binary Tree: Tipe binary tree dimana perbedaan height subtree dari tiap node adalah 1 atau 0.