Data Structure – 3

Session – 3

Implementasi Linked List

1. Stack

Adalah tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain.

Stack bersifat LIFO (Last In First Out) artinya benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack

Operasi-operasi yang biasanya tredapat pada Stack yaitu:

1. Push : berguna untuk menambah item pada stack pada tumpukan paling atas
2. Pop : berguna untuk mengambil item pada stack pada tumpukan paling atas
3. Clear : berguna untuk mengosongkan stack
4. IsEmpty : berguna untuk mengecek apakah stack sudah kosong
5. IsFull : berguna untuk mengecek apakah stack sudah penuh

 

2. NOTASI INFIX, PREFIX, POSTFIX

• Infix : adalah notasi yang berbentuk operator atas operand, operator berada diantara operand
• Prefix : adalah notasi yang berbentuk operator atas operand, operator berada diatas operand
• Postfix : adalah notasi yang berbentuk operator atas operand, operator berada dibelakang operand

 

Contoh – contoh operasinya :

Infix        :  4 + 6 * ( 5 – 2 ) / 3

Prefix     :  + 4 / 3 * 6 – 5 2

Postfix   :  4 6 5 2 – * 3 / +

 

3. QUEUE

Adalah antrian sekumpulan data penambahan dan penghapusan pada implementasi suatu array dan linked list  Bersifat FIFO (First In First Out) dan memiliki karateristik :

1. elemen antrian.
2. front (elemen terdepan antrian).
3. tail (elemen terakhir).
4. jumlah elemen pada antrian.
5. status antrian.

 

4. DFS dan BFS

• DFS (depth first search)

adalah pencarian pada suatu node dalam setiap level dari paling kiri

Kelebihan DFS :

1. Pemakaian memori yang sedikit
2. Jika solusi yang dicari berada paling kiri dengan mudah ditemukan

Kelemahan DFS :

1. Jika level dinaikkan tak terhingga, maka Solusi tidak complete
2. Tidak optimal dalam mengatasi solusi yang sama dalam level yang berbeda

 

• BFS (Breadth First Search)

adalah pencarian secara melebar yang mengunjungisimpul secara pre oder

Kelebihan BFS :

1. Tidak akan menemui jalan buntu.
2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.
3. Jika ada satu solusi maka bread-first search akan menemukannya

Kelemahan BFS :

1. Membutuhkan memori yang cukup banyak.
2. Membutuhkan waktu yang cukup lama.