Pengertian Stack
Stack (Tumpukan) adalah Struktur data linier yang dapat diimplementasikan dengan baik menggunakan array / Linked List
- Stack bersifat LIFO (Last In First Out), artinya data yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack
Contoh dari stack adalah seperti gambar diatas. Seperti tumpukan piring (A-F), piring yang satu akan ditumpuk diatas piring yang lainnya. Bila kita ingin mengambil piring tersebut, kita harus mengambil piring dari yang paling atas (F). Jadi piring yang paling bawah / paling pertama ditumpuk (A), akan menjadi piring yang paling terakhir diambil
Array Representation
- Stack memiliki 2 variabel :
1. Top = Digunakan untuk menyimpan alamat unsur elemen dari stack
2. Max = Digunakan untuk menyimpan jumlah maksimum elemen yang dapat ditahan oleh stack
- Jika Top = NULL, maka Stack is empty(kosong)
- Jika Top = MAX-1, maka Stack is Full (penuh)
Liked List Representation
- Didalam Linked Stack, setiap node memiliki 2 bagian :
1. Bagian yang menyimpan data
2. Bagian yang menyimpan alamat dari next node
- Start pointer dari Linked List digunakan sebagai Top
- Jika Top = NULL, itu berarti mengindikasikan bahwa Stack kosong
- Push() = Digunakan untuk memasukkan data
- Pop() = Digunakan untuk menghapus data
- Top() = Digunakan untuk mengembalikan data dari stack
Stack Applications
- Infix evaluation
- Postfix evaluation
- Prefix evaluation
- Infix to Postfix conversion
- Infix to Prefix conversion
- Depth First Search
Infix, Postfix dan Prefix Notation
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 ditulis setelah Operand (Rumus = Operator, Left Operand, Right Operand)
- Infix = Operator berada diantara Operand
- Postfix = Operator ditulis setelah Operand (Rumus = Left Operand, Right Operand, Operator)
Depth First Search
Depth First Search adalah algoritma untuk melakukan penelusuran / pencarian struktur graf / pohon berdasarkan kedalaman
- DFS memiliki banyak aplikasi seperti :
1. Menemukan artikulasi point dan brigde didalam graph
2. Menemukan komponen yang terhubung
3. Topological sorting
Aplikasi stack lainnya
Stack biasanya digunakan untuk :
- Reverse the order of data
- Convert infix menjadi postfix
- Convert postfix menjadi infix
- Backtracking problem
- Syetem stack biasanya digunakan di setiap fungsi recursive
- Converting angka desimal menjadi binary equivalent
QUEUE
Pengertian Queue
Queue (Antrian) adalah Struktur data penting yang menyimpan data secara teratur.
- Queue bersifat FIFO (First In, First Out), artinya data yang pertama kali masuk akan menjadi data
yang pertama kali keluar
Contoh :
Saat orang menunggu Bis. Orang yang berdiri di paling depan, akan menjadi orang pertama yang
masuk ke bis
Queue memiliki 2 Variabel : Front dan Rear
Operasi pada Queue :
- Push(x) : Digunakan untuk menambahkan data x ke bagian belakang Queue
- Pop() : Digunakan untuk menghapus data dari bagian depan Queue
- Front() : Mengembalikan data paling depan dari Queue
Queue Applications
- Deques
- Priority Queues
- Breadth First Search
Deques
Deques adalah proses dimana elemen dapat dimasukkan / dihapus dikedua ujung.
- Juga dikenal sebagai Head-Tail Linked, karena elemen dapat ditambahkan / dihapus dari depan
(head) / belakang (tail).
2 Varian dari Double-Ended Queue, termasuk :
- Input Restricted Deque = Insertion dapat dilakukan hanya pada salah satu Dequeue & penghapusan
dapat dilakukan dari kedua ujung
- Output Restricted Deque = Penghapusan dapat dilakukan hanya pada salah satu Dequeue &
Insertion dapat dilakukan pada kedua ujungnya
Breadth First Search
Breadth First Search (BFS) adalah Algoritma untuk melakukan penelusuran / pencarian struktur graf
- BFS memiliki banyak aplikasi seperti :
1. Menemukan komponan terhubung didalam graph
2. Menemunkan jalan terpendek dalam unweighted graph
3. Metode Ford-Fulkerson untuk komputasi aliran maksimum
No comments:
Post a Comment