Linked List Implementation II
Sub Topics :
Stack:
- Stack Concept
- Stack using Array and Linked List
- Infix, Postfix and Prefix Notation
- Evaluation
- Conversion
- Depth First Search
- Queue Concept
- Queue using Array and Linked List
- Priority Queues
- Breadth First Search
· Konsep Stack
Stack adalah struktur data penting yang menyimpan elemen secara teratur
Stack bisa di analogikan dengan :
Jika kita melihat tumpukan piring yang mana satu piring diletakkan di atas piring lain. Dan bila kita ingin mengambil piring tersebut, maka kita harus mengambil piring yang paling atas. Oleh karena itu, kita dapat menambahkan atau mengambil (menghapus) piring melalui piring yang paling atas (top of stack), berarti stack ini memiliki konsep LIFO (Last In First out).
- Stack adalah struktur data linear yang dapat diimplementasikan dengan menggunakan array atau linked list.
- Elemen dalam stack dapat ditambah dan dihapus hanya dari tumpukan yang paling atas (top of stack)
· Representasi Array
Stack memiliki 2 variabel :
- TOP yang berarti digunakan untuk menyimpan alamat dari element stack yang paling atas.
- MAX yang berarti digunakan untuk menyimpan angka maksimum dari elemen yang stack dapat menahan.
Jika TOP = NULL, maka itu menunjukan bahwa stack kosong.
Jika TOP = MAX-1, maka itu menunjukan bahwa stack penuh.
TOP = 4, Penyisipan dan penghapusan akan dilakukan pada posisi ini (4).
· Representasi Linked List
Teknik untuk membuat stack menggunakan array memang mudah, tapi kekurangannya adalah bahwa array harus di deklarasikan terlebih duhulu ukuran tetapnya.
Dalam linked stack, setiap node memiliki dua bagian :
- Satu untuk menyimpan data
- Satu untuk menyimpan alamat dari node berikutnya
Pointer START dari linked list digunakan sebagai TOP
Semua penyisipan dan penghapusan dilakukan dari node TOP.
Jika TOP = NULL, maka dapat diindikasikan bahwa stacknya kosong.
· Operasi pada Stack
Push(x) : Menambahkan item x ke top of the stack (stack yang paling atas)
Pop() : Menghapus item dari top of the stack (stack yang paling atas)
Top() : Reveal/return item teratas dari stack
Note : TOP juga dikenal sebagai peek.
Contoh Operasi stack :
· Aplikasi Stack
Ada beberapa aplikasi yang menggunakan struktur data stack yang akan kita bahas yaitu :
- Infix evaluation
- Postfix evaluation
- Prefix evaluation
- Infix to Postfix conversion
- Infix to Prefix conversion
- Depth First Search
· Infix, Postfix, dan Prefix Notation
Ada tiga notasi aritmatika yang dikenal : Prefix notation, juga dikenal sebagai Reverse Polish notation, Infix notation (yang sangat umum digunakan), Postfix Notation, juga dikenal sebagai Polish notation.
Postfix notation ditemukan oleh Jan Lukasiewicz seorang Polish Logician, ahlii matematika dan juga filsuf. Tujuannya adalah untuk mengembangkan parenthesis-free prefix notation (dikenal juga sebagai polish notation) dan postfix notation yang lebih dikenal sebagai Reverse Polish Notation atau RPN.
|
Prefix
|
Infix
|
Postfix
|
|
* 4 10
|
4 * 10
|
4 10 *
|
|
+ 5 * 3 4
|
5 + 3 * 4
|
5 3 4 * +
|
|
+ 4 / * 6 – 5 2 3
|
4 + 6 * (5 – 2) / 3
|
4 6 5 2 – * 3 / +
|
Prefix : operator yang tertulis sebelum Operand
Rumusnya : operator – left operand – right operand
Infix : operator yang ditulis diantara operand
Rumusnya : left operand – operator – right operand
Postfix : operator yang ditulis setelah operand
Rumusnya : left operand – right operand - operator
Prefix dan postfix notations tidak perlu tanda kurung untuk memprioritaskan yang dihitung terlebih dahulu. Dan notations ini jauh lebih mudah untuk dievaluasi oleh komputer.
Evaluation infix notation :
Diberikan Infix : 4 + 6 * ( 5 – 2 ) / 3.
Untuk mengevaluasi infix notation, kita harus mencari prioritas yang harus dihitung terlebih dahulu.
4 + 6 * (5 – 2) / 3 Cari operator yang diprioritaskan, yaitu ( )
4 + 6 * 3 / 3 Cari operator yang diprioritaskan, yaitu *
4 + 18 / 3 Cari operator yang diprioritaskan yaitu /
4 + 6 Cari operator yang diprioritaskan yaitu +
10
Evaluation Postfix notation :
Secara manual
Scan dari kiri ke kanan
5 6 7 x 3 2 ^- +, scan sampai mencapai operator pertama
5 6 7 x 3 2 ^- +, menghitung 6 x 5
7 30 3 2 ^- +, scan lagi sampai mencapai berikutnya operator
7 30 3 2 ^- +, menghitung 32
7 30 9- +, scan lagi untuk pencarian berikutnya operator
7 30 9- +, menghitung 30 – 9
7 21 +, scan lagi
7 21 +, menghitung 7 + 24
28, selesai
Menggunakan Stack
Algoritmanya :
Melakukan scan string dari kiri ke kanan, untuk setiap karakter dalam string:
Jika operan, push ke dalam stack.
Jika operator, pop dua kali (menyimpan dalam masing-masing variabel A dan B) dan push (B operator A).
Pay attention here! It is (B operator A), not (A operator B).
Hasilnya akan disimpan dalam satu-satunya unsur dalam stack.
String Stack
4 6 5 2 – * 3 / +
4 6 5 2 – * 3 / + 4 push(4)
4 6 5 2 – * 3 / + 4 6 push(6)
4 6 5 2 – * 3 / + 4 6 5 push(5)
4 6 5 2 – * 3 / + 4 6 5 2 push(2)
4 6 5 2 – * 3 / + 4 6 3 pop 2, pop 5, push(5 – 2)
4 6 5 2 – * 3 / + 4 18 pop 3, pop 6, push(6 * 3)
4 6 5 2 – * 3 / + 4 18 3 push(3)
4 6 5 2 – * 3 / + 4 6 pop 3, pop 18, push(18 / 3)
4 6 5 2 – * 3 / + 10 pop 6, pop 4, push(10) à the result
Evaluation prefix notation :
Secara manual
Scan dari kanan ke kiri
+ 7 – x 6 5 ^ 3 2
+ 7 – x 6 5 ^ 3 2
+ 7 – x 6 5 9
+ 7 – x 6 5 9
+ 7 – 30 9
+ 7 – 30 9
+ 7 21
+ 7 21
28
Menggunakakn stack
Evaluating prefix notation mirip dengan postfix notation dengan cara scan string dari kanan ke kiri.
Conversion Infix to Postfix notation
Secara manual
Algoritmanya :
1. Cari operator yang memiliki prioritas tertinggi
2. Letakan operator di belakang operand
3. Lakukan berulang sampai selesai
Conversion infix to postfix notation
Secara manual
A + B – C x D ^ E / F , prioritaskan operator yang memiliki power
A + B – C x D E ^ / F , letakan ^ dibelakang D dan E
A + B – C x D E ^ / F , x dan / memiliki prioritas yang setara
A + B – C D E ^ x / F , letakan x di akhir
A + B – C D E ^ x / F ,lanjutkan dengan algoritma yang sama hingga selesai
A + B – C D E ^ x F /
A + B – C D E ^ x F /
A B + – C D E ^ x F /
A B + – C D E ^ x F /
A B + C D E ^ x F / – , ini adalah Postfix notation
Conversion Infix to Postfix notation
Menggunakan stack
Algoritmanya :
Scan string dari kiri ke kanan, untuk setiap karakter dalam string :
- Jika itu adalah sebuah operand, tambahkan itu ke postfix string
- Jika itu adalah buka kurung, push itu ke dalam stack
- Jika itu adalah tutup kurung, pop stack sampai menemukan buka kurung.
tambah setiap popped element ke postfix string
- Jika itu adalah sebuah operator, pop sedangkan elemen atas stack memiliki prioritas yang lebih tinggi atau sama dengan karakter yang di scan.
Tambahkan setiap elemen yang muncul ke postfix string. Push karakter yang discan ke dalam stack.
Setelah scan semua karakter, pop semua elemen di stack dan tambahkan semuanya ke postfix string.
String Stack Postfix String
4 + 6 * (5 – 2) / 3
4 + 6 * (5 – 2) / 3 4
4 + 6 * (5 – 2) / 3 + 4
4 + 6 * (5 – 2) / 3 + 4 6
4 + 6 * (5 – 2) / 3 + * 4 6
4 + 6 * (5 – 2) / 3 + * ( 4 6
4 + 6 * (5 – 2) / 3 + * ( 4 6 5
4 + 6 * (5 – 2) / 3 + * ( – 4 6 5
4 + 6 * (5 – 2) / 3 + * 4 6 5 2
4 + 6 * (5 – 2) / 3 + * / 4 6 5 2 –
4 + 6 * (5 – 2) / 3 + / 4 6 5 2 – *
4 + 6 * (5 – 2) / 3 + / 4 6 5 2 – * 3
4 + 6 * (5 – 2) / 3 4 6 5 2 – * 3 / +
Conversion Infix to Prefix Notation
Secara manual
Algoritmanya :
1. Cari operator yang mempunyai prioritas tertinggi
2. Letakan operator tersebut sebelum operands
3. Lakukan berulang hingga selesai
A + B – C x D ^ E / F
A + B – C x ^ D E / F
A + B – C x ^ D E / F
A + B – x C ^ D E / F
A + B – x C ^ D E / F
A + B – / x C ^ D E F
A + B – / x C ^ D E F
+ A B – / x C ^ D E F
+ A B – / x C ^ D E F
– + A B / x C ^ D E F , ini adalah prefix notation
Conversion infix to prefix notation
Menggunakan stack
Ini sedikit memiliki kesamaan dengan conversion dari infix ke post fix.
· Depth First Search
DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.
Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.
Jadi, jika ada pohon biner seperti gambar di bawah ini :
Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L
Algoritmanya :
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
Visit order: A, C, B, E, D
· Other Stack Applications
Stacks banyak digunakan untuk :
- Membalik urutan data
- Mengkonversi infix expression ke postfix
- Mengkonversi postfix expression ke infix
- Masalah backtracking
- Sistem stack digunakan untuk setiap fungsi rekursif
- Mengubah angka desimal menjadi setara binernya
· Queue
Queue dapat diartikan sebagai antrean. Merupakan kumpulan data di mana penambahan data (elemen) hanya melalui satu sisi, yaitu depan (head) dan penghapusan data (elemen) hanya melalui sisi belakang (tail). Sifat ini sering disebut dengan FIFO (First In First Out)
· Operasi pada Queue
Push(x) : menambahkan item x ke belakang queue
Pop() : menghapus sebuah item dari depan queue
Front() : reveal/return item paling depan dari queue
Front juga dikenal sebagai peek.
· Aplikasi pada Queue
Ada beberapa aplikasi yang menggunakan struktur data queue diantarnya :
- Deques
- Priority Queues
- Breadth First Search
· Deques
DEQUE adalah antrian dimana elemennya bisa masuk dan keluar lewat kedua ujungnya (berbeda dengan queue yang hany bisa masuk lewat ujung belakang dan keluar lewat ujung depan). Biasanya DEQUE disajikan dengan menggunakan Double link list yang memiliki dua buah pointer yang menunjuk ke posisi sebelumnya dan sesudahnya.
DEQUE juga mempunyai dua jenis variasi yaitu :
Deque input terbatas : suatu deque yang membatasi pemasukkan elemen hanya pada satu ujung dari list, sementara penghapusan elemen boleh dilakukan pada kedua ujung list.
Deque output terbatas : merupakan kebalikan dari deque input terbatas yaitu suatu deque yang membatasi penghapusan elemen hanya pada satu ujung dari list, sementara pemasukkan elemen boleh dilakukan pada kedua ujung list
· Priority Queue
Priority Queue adalah queue dengan basis HPIFO ( Highest Priority In First Out ). Berbeda
dengan queue yang sangat tergantung kepada waktu kedatangan ( elemen yang datang
pertama akan selalu diambil / dihapus adalah elemen yang memilki priority tertinggi ( bila
yangmenjadi prioritas adalah waktu kedatangan maka Priority Queue berfungsi seperti queue
biasa ).
· Breadth First Search (BFS)
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.
0 komentar:
Posting Komentar