Stack Concept
Stack adalah tumpukan, biasanya dalam program konsep ini dipake di dalam array atau linked list. Tumpukan ini mempunyai algo seperti last in first out (posisi terakhir,keluar pertama).
Array Representation
Terdapat 2 variabel yaitu top dan max. Top disini maksudny element yang letaknya terakhir dari sebuah stack. Max adalah nilai maks dari element stack yang menahan.
Rumusnya : TOP = NULL -> menandakan stack ny kosong.
TOP = MAX - 1 -> menandakan stackny penuh.
Linked List Representation (Stack)
Terdapat variabel head,tail,next pada single linked list sedangkan di double linked list ditambah dengan variabel prev.
Stack Operations
Terdapat 3 variabel(hanya sebagai patokan) untuk mengoperasikannya :
Evaluation Infix Notation
Evaluasi infix berikut : 4 + 6 * (5-2) / 3.
*Untuk mengevaluasi infix berikut,kita harus mencari operator utama yang fungsinya didahulukan pertama.
Front dan rear berada di posisi yang kita bisa hapus dan kita bisa sisipkan suatu nilai di antaranya.
Linked List Representation (Queue)
Terdapat dua bagian :
Stack adalah tumpukan, biasanya dalam program konsep ini dipake di dalam array atau linked list. Tumpukan ini mempunyai algo seperti last in first out (posisi terakhir,keluar pertama).
Array Representation
Terdapat 2 variabel yaitu top dan max. Top disini maksudny element yang letaknya terakhir dari sebuah stack. Max adalah nilai maks dari element stack yang menahan.
Rumusnya : TOP = NULL -> menandakan stack ny kosong.
TOP = MAX - 1 -> menandakan stackny penuh.
Linked List Representation (Stack)
Terdapat variabel head,tail,next pada single linked list sedangkan di double linked list ditambah dengan variabel prev.
Stack Operations
Terdapat 3 variabel(hanya sebagai patokan) untuk mengoperasikannya :
- Push() : untuk menambah nilai.
- Pop(): untuk menghapus nilai.
- Top() -> disebut jg sbg peek: untuk mengembalikan nilai teratas dari tumpukan.
Infix, Postfix, and Prefix Notation
- Prefix = Reverse Polish Notation.
- Postifx = Polish Notation.
Rumusnya :
- Infix = kiri operands,operator,kanan operands.
- Prefix = operator,kiri operands,kanan operands.
- Postfix = kiri operands,kanan operands,operator.
Evaluation Infix Notation
Evaluasi infix berikut : 4 + 6 * (5-2) / 3.
*Untuk mengevaluasi infix berikut,kita harus mencari operator utama yang fungsinya didahulukan pertama.
4 + 6 * (5 – 2) / 3 search the highest precedence operator, it is ( )
4 + 6 * 3 / 3 search the highest precedence operator, it is *
4 + 18 / 3 search the highest precedence operator, it is /
4 + 6 search the highest precedence operator, it is +
10
Evaluation Postfix Notation
Mulai dari kiri ke kanan
7 6 5 x 3 2 ^ – + , scan until reach the first operator
7 6 5 x 3 2 ^ – + , calculate 6 x 5
7 30 3 2 ^ – + , scan again until reach next operator
7 30 3 2 ^ – + , calculate 32
7 30 9 – + , scan again to search next operator
7 30 9 – + , calculate 30 – 9
7 21 + , scan again
7 21 + , calculate 7 + 24
28 , finish
Evaluation Prefix Notation
Mulai 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
Conversion Infix to Postfix Notation
- Cari operator utama yang fungsinya didahulukan pertama.
- Letakkan operator sebelum operands.
- Ulangi sampai selesai.
A + B – C x D ^ E / F , power has the highest precedence
A + B – C x D E ^ / F , put ^ behind D and E
A + B – C x D E ^ / F , x and / have same level precedence
A + B – C D E ^ x / F , put x at the end
A + B – C D E ^ x / F , continue with the same algorithm till finish
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 / – , this is the Postfix notation
Conversion Infix to Prefix Notation
- Cari operator utama yang fungsinya didahulukan pertama.
- Letakkan operator sebelum operands.
- Ulangi sampai 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 , this is the Prefix notation
Depth First Search
DFS adalah sebuah algoritma yang mencari melintas atau mencari di pohon atau grafik.
DFS mempunyai beberapa aplikasi :
- Menemukan titik arkulasi dan jembatan dalam grafik.
- Mememukan komponen yang terhubung.
- Topological sorting.etc.
Algorithm:
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
Queue
Queue adalah antrian, biasanya dalam program konsep ini dipake di dalam array atau linked list. Element paling belakang disebut rear, element paling depan disebut front.
Array Representation
Array Representation
Linked List Representation (Queue)
Terdapat dua bagian :
- Satu yang bisa menyimpan data.
- Yang lainnya menyimpan alamat untuk element selanjutnya.
Queue Operations
Terdapat 3 variabel(hanya sebagai patokan) untuk mengoperasikannya :
- Push() : Untuk menambah nilai.
- Pop(): Untuk menghapus nilai.
- front(): Memanggil kembali nilai paling depan pada antrian.
Circular Queue
Circular queue pengoperasiannya mirip dengan queue dengan mode FIFO (First In First Out), tetapi karena bentuknya yang circular posisi element terakhir bertemu dengan element pada posisi pertama.
Ada 3 aplikasi di circular queue:
- Deques
- Priority Queues
- Breadth First Search
Deques
Deques adalah daftar yang dimana bisa kita tambahin atau delete nilai pada kedua ujungnya pada suatu element.
Dua variasi dari double-ended queue :
- Input restricted deque : hanya bekerja pada salah satu dequeue sementara penghapusan dapat dilakukan pada kedua ujugnnya.
- Output restricted deque : hanya bekerja pada salah satu dequeue sementara penyisipa dapat dilakukan pada kedua ujungnya.
Priority Queue
Priority queue adalah data tipe abstrak yang dimana setiap element diprioritaskan.
Cara kerja dasarnya :
- Element yang mempunyai prioritas yang tinggi akan diproses duluan.
- Kedua element yang prioritasnya selevel akan diproses sesuai FCFS(First Come First Served).
Breadth First Search
hampir sama seperti DFS merupakan algoritma yang berguna untuk tranversing atau mencari di dalam tree atau graph.
BFS menggunakan konsep queue.
Algorithm BFS :
BFS menggunakan konsep queue.
Algorithm BFS :
Prepare an
empty queue
Push
source/root into queue
Mark
source/root
While
queue is not empty
Pop an item from queue into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into
queue
Example :
Komentar
Posting Komentar