SESSION 3&6| Linked List Implementation
Stack
Koleksi data item yang hanya dapat diakses pada akhir bagian stack. Item terakhir yang dimasukkan ke stack adalah item yang paling pertama dikeluarkan. Itulah mengapa stack disebut Last In First Out (LIFO) data structure. Stack mempunyai 2 variable, TOP untuk menyimpan alamat elemen stack paling atas, MAX untuk menyimpan alamat elemen stack paling atas.
Jika TOP = NULL, maka stack kosong.
Jika TOP = MAX – 1, maka stack penuh.
Dalam linked stack, setiap node mempunyai 2 bagian:
- satu untuk menyimpan data
- satu untuk menyimpan alamat ke node selanjutnya
Infix, Postfix, and Prefix Notation
Prefix : Operator Operand Operand
Postfix : Operand Operand Operator
Infix : Operand Operator Operand
| 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 / + |
Depth First Search
Algoritma untuk melintas/mencari dalam tree/graph.
Queue
Sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisi belakang, dan penghapusan dilakukan lewat ujung lain. Queue memiliki kosnep elemen yang pertama kali masuk, lalu elemen yang pertama kali keluar.
Queue disebut juga sebagai First in First Out (FIFO).
Front adalah startnya pointer. Penambahan data baru dilakukan di rear, dan penghapusan dilakukan di front.
Jika Front = Rear = NULL, maka queue kosong.
Beberapa aplikasi yang menggunakan queue:
- Deques
- Priority Queues
- Breadth First Search
Breadth First Search
Seperti DFS, sebuah algoritma untuk melintas/mencari dalam tree/graph.
DFS menggunakan stack, namun BFS menggunakan queue.
