Sebelum masuk ke implementasi linked list itu sendiri, ada baiknya kita
mengenal konsep - konsep yang berhubungan dengannya.
Stack
-------
Stack bisa diartikan sebagai tumpukan. Data disusun
seolah-olah berada di atas data lainnya. Maka, data yang pertama masuk, akan
berada di paling bawah dan data yang terakhir masuk akan berada di paling atas.
Ini berarti, data yang berada di paling atas akan menjadi data yang pertama
kali keluar, maka stack disebut juga Last in First out (LiFo).
Istilah penting :
1. Push / enqueue / enstack = Menambahkan data ke dalam stack / queue
2. Pop / dequeue / destack = Mengambil data dari stack / queue
Implementasi Stack menggunakan Array
---------------------------------------------------
Untuk melakukan implementasi stack dengan array dibutuhkan setidaknya 2
variabel pembantu.
Dalam contoh ini diguakan Top dan Max.
1. Top menunjukkan elemen paling atas dari stack.
2. Max menunjukkan panjang array yang digunakan, yang juga berarti jumlah
maksimal elemen yang dapat ditampung di dalam stack.
Sebagai contoh, pada Stack di atas, Top menunjukkan angka 4,
yang berarti array index ke 0 hingga 4 telah terisi.
Kemudian Max munujukkan angka 8, yaitu kapasitas maksimum array.
Nilai awal Top biasanya adalah -1, yaitu angka yang tidak menjadi index pada
array.
Apabila nilai Top adalah -1, berarti array tersebut masih kosong.
*Apabila kita melakukan Push:
Selama Top + 1 >= Max, Top akan ditambah 1.
*Apabila kita melakukan Pop
Selama Top tidak sama dengan -1, Top akan dikurang 1.
Implementasi Stack menggunakan Linked List
---------------------------------------------------------
Membuat stack dengan menggunakan array jauh lebih mudah, namun panjang
stack terbatas karena harus dideklarasikan terlebih dahulu. Disinilah dimana
linked list lebih berguna, karena panjangnya tidak terbatas.
Untuk menggunakan linked stack / linked list, setiap node harus memiliki 2
bagian:
-Bagian yang menyimpan data
-Bagian yang menyimpan alamat / address dari node selanjutnya
Jika belum ada data, Top = NULL
Aplikasi dari Stack
-------------------------
Stack dapat digunakan untuk:
1. Evaluasi infix
2. Evaluasi postfix
3. Evaluasi Prefix
4. Konversi Infix menjadi Postfix
5. Evaluasi Infix menjadi Prefix
6. Depth First Search
Infix, Prefix, Postfix
---------------------------
Infix, Prefix, Postfix berbeda dari urutan penulisan operator dan operand.
Mengapa kita membutuhkan prefix dan postfix? Karena prefix dan postfix lebih
mudah untuk dievaluasi oleh komputer.
Operator misalnya + - * / dst
Operand misalnya 1 2 3 a b c
Urutan:
Prefix : Operator Operand Operand
Postfix : Operand Operand Operator
Infix : Operand Operator Operand
Contoh :
1. Infix 4 + 6 * (5 - 2) / 3
Prefix + 4 / * 6 - 5 2 3
Postfix 4 6 5 2 - * 3 / +
2. Infix 5 + (12 * 3) / 2
Prefix + 5 / * 12 3 2
Postfix 5 12 3 * 2 / +
Depth First Search
-------------------------
Depth First Search atau DFS adalah algoritma untuk melintasi atau mencari data
di sebuah tree atau grafik.
DFS dimulai dari akar tree, kemudian menelusuri sedalam mungkin dari
setiap cabang sebelum kemudian berbalik arah.
Aplikasi dari DFS misalnya untuk:
- Mencari titik sambung dari titik-titik di dalam sebuah grafik
- Mencari komponen yang terhubung
- Pengurutan secara topologi
Pada gambar di atas, urut-urutan dari perjalanannya adalah
A, C, B, E, D
Queue
----------
Queue atau antrian berarti elemen yang pertama kali masuk,
juga adalah elemen yang pertama kali keluar.
Karena itu, queue disebut juga First in First Out (FIFO).
Implementasi Queue dengan Array
---------------------------------------------
Membutuhkan 2 variabel, yaitu Front dan Rear, sehingga penambahan data dan
penghapusan data dapat dilakukan secara terpisah.
Sebagai contoh pada array di atas, Front adalah 0, dan Rear
adalah 5.
Implementasi Queue dengan Linked List
--------------------------------------------------
Untuk menggunakan linked stack / linked list, setiap node harus memiliki 2
bagian:
-Bagian yang menyimpan data
-Bagian yang menyimpan alamat / address dari node selanjutnya
Pointer untuk Start dinamai Front.
Semua pemasukan data baru akan dilakukan di Rear, dan semua penghapusan akan
dilakukan di Front.
Jika Front = Rear = NULL (kosong), maka queue tersebut adalah kosong.
Circular Queue
-------------------
Circular queue, sesuai namanya adalah sebuah queue melingkar, yaitu dimana
bagian akhir queue tersambung dengan bagian awalnya.
Beberapa aplikasi dari queue adalah sebagai berikut:
1. Deques
2. Priority Queue
3. Breadth First Search (BFS)
Deque
---------
Adalah list dimana elemen-elemennya dapat ditambah atau dihapus pada kedua
ujungnya.
Deque disebut juga head-tail linked list.
Priority Queue
---------------------
Priority Queue adalah tipe data abstrak dimana setiap elemen memiliki prioritas
terntenu.
Angka yang lebih kecil berarti prioritasnya lebih tinggi (Lihat F sebagai
contoh)
Breadth First Search
----------------------------
Breadth First Search atau BFS adalah algoritma untuk menelusuri atau mencari di
dalam sebuah tree atau grafik.
Dimulai dari akar sebuah tree, kemudian menelusuri semua "tetangga"
pada tingkat yang sama hingga mencapai goal.
Perbedaan dari DFS dan BFS adalah DFS menggunakan stack sedangkan BFS
menggunakan queue.
Urutan : A, B, C, D, E
0 komentar: