3 - Linked List Implementation 2 - Kelvin Ricadson - 2101691101

Stack

Pengertian Stack pada struktur data adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack pada struktur data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak.

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 terdapat pada Stack yaitu :

1.      Push  : digunakan untuk menambah item pada stack pada tumpukan paling atas.

2.      Pop    : digunakan untuk mengambil item pada stack pada tumpukan paling atas.

3.      Clear  : digunakan untuk mengosongkan stack.

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS). Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack. Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

                                                                          

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack.

Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

                                                              

Array Representation

Stack memiliki dua variabel:
TOP yang digunakan untuk menyimpan alamat elemen paling atas dari stack
MAX yang digunakan untuk menyimpan jumlah maksimum elemen yang dapat disimpan stack
Jika TOP = NULL, maka menunjukkan bahwa stack kosong
Jika TOP = MAX - 1, maka stack sudah penuh

Linked Array Representation

Teknik membuat stack menggunakan array lebih mudah, namun kekurangannya adalah array harus dinyatakan memiliki beberapa ukuran tetap. Dalam sebuah linked stack, setiap node memiliki dua bagian : Yang menyimpan dataSalah satu yang menyimpan alamat simpul berikutnya. Petunjuk START dari linked list digunakan sebagai TOP Semua penyisipan dan penghapusan dilakukan pada simpul yang ditunjukkan oleh TOP .Jika TOP = NULL, maka itu menunjukkan bahwa stack kosong

Infix, Postfix, and Prefix Notation

Notasi Postfix  diberikan oleh Jan Lukasiewicz yang adalah seorang Polandia ahli logika, matematikawan, dan filsuf. Tujuannya adalah untuk berkembang. Notasi awalan bebas tanda kurung (juga dikenal sebagai notasi polandia) dan notasi postfix yang lebih dikenal dengan Reverse Polish

Ada 3 notasi aritmatika :

1.      Prefix notation

Prefix à Operator ditulis sebelum operan.

Contoh dari Prefix , yaitu :

* 4 10

+ 5 * 3 4

+ 4 / * 6 – 5 2 3

2.      Infix notation

Infix à Operator ditulis antara operan.

Contoh dari Infix , yaitu :

4 * 10

5 + 3 * 4

4 + 6 * (5 – 2) / 3

3.      Postfix notation

Postfix à Operator ditulis setelah operan.

4 10 *

5 3 4 * +

4 6 5 2 – * 3 /  +

Contoh :

1. Ubahlah 1/ (2 * 3 - 5) menjadi Prefix and Postfix notation

Prefix : 1 / (2 * 3 - 5 ) -> 1 / (* 2 3 - 5 ) -> 1 / ( - * 2 3 5 ) -> / 1 - * 2 3 5

Postfix : 1 / ( 2 * 3 – 5 ) -> 1 / ( 2 3 *- 5 ) -> 1 / ( 2 3 * 5 - ) -> 1 2 3 * 5 - /

Depth First Search ( DFS )

DFS adalah algoritma untuk mencari di pohon atau grafik.

Pencarian menggunakan DFS adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan kenode paling dalam lainnya yang masih memiliki successor yang belum di ekspansi.

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. DFS dapat diimplementasikan dengan fungsi rekursif atau iteratif.

                                                  

Breadth First Search (BFS)

BFS adalah sebuah algoritma pencarian solusi yang digambarkan dengan struktur pohon. Dimana penyelesaiannya dilakukan dimulai dari simpul akar kemudian melebar sesuai dengan tingkatan yang ada didalam pohon.

Algoritma BFS :

1     Masukkan simpul ujung (akar) ke dalam antrian

2.    Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi

3.    Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4.   Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian

5.   Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

6.    Ulangi pencarian dari langkah kedua.

                                       

Queue

Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang ( tail ) dan penghapusan data hanya melalui sisi depan ( head ). Berbeda dengan stack yang bersifat LIFO ( Last In First Out ), maka queue bersifat FIFO ( First In First Out ), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.

Linked List Representation

Mirip dengan stack, teknik membuat antrian menggunakan array itu mudah, namun kelemahannya adalah bahwa array memilik beberapa ukuran tetap.

Dalam Linked queue, setiap elemen memiliki 2 elemen :

1.     Satu untuk menyimpan data

2.     Satu untuk menyimpan alamat elemen berikutnya

Petunjuk start dari linked list digunakan sebagai FRONT.

Semua penyisipan akan dilakukan di REAR, dan semua penghapusan dilakukan diujung DEPAN.

Jika FRONT=REAR=NULL, maka menunjukkan bahwa antrian kosong.

Operasi Queue

1.      Push(x) : menambahkan data x kebagian belakang antrian.

2.      Pop() : menghapus data dari bagian depan antrian.

3.      Front() : mengembalikan item paling depan dari antrian.

GAMBAR

Deques

Adalah antrian dimana elemennya bisa masuk dan keluar lewat kedua ujungnya (berbeda dengan queue yang hanya bisa masuk lewat ujung belakang dan keluar lewat ujung depan). Biasanya deque disajikan dengan menggunakan double linked list yang memiliki dua buah pointer yang menunjuk keposisi sebelumnya dan sesudahnya.

Ada 2 varian antrian double-ended, meliputi :

1.     Input restricted deque

Dalam sisipan deque ini bisa dilakukan hanya pada salah satu dequeue sementara penghapusan bisa dilakukan dari kedua ujungnya.

2.     Output restricted deque

Dalam penghapusan dequeue ini bisa dilakukan hanya pada salah satu dequeue sementara sisipan bisa dilakukan pada kedua ujungnya.

Priority Queue

Antrian prioritas adalah tipe data abstrak dimana masing-masing elemen diberi prioritas.

Aturan umum elemen pemrosesan antrian prioritas :

1.      Elemen dengan prioritas yang tinggi adalah proses sebelum elemen dengan prioritas yang rendah.

2.      Dua elemen dengan prioritas yang sama diproses berdasarkan First Come First Served ( FCFS ).