datStruct-2

STACK

stack adalah data structure yang menyimpan kumpulan element, mirip seperti array dan linked list.
namun, operasi pada stack yaitu insert dan deletion hanya dapat dilakukan pada 1 sisi, yang umumnya disebut "TOP".

apabila di dalam linked list kita dapat insert middle, before, after, pada Stack kita hanya dapat melakukan insert head.

prinsip stack yaitu last-in first-out (LIFO)

analogi : seperti tumpukan piring, kita dapat memindahkan/menabahkan piring hanya dari paling atas.

stack dapat di representasikan dalam bentuk ARRAY dan LINKED LIST. dalam teknik pembuatan mungkin array lebih mudah, namun kelemahan array dibanding linked list yaitu pada array perlu mendeklarasikan jumlah dari element itu.

operation pada stack:
1. push() : yaitu  untuk menambahkan suatu element / item paling atas
2. pop()  : untuk memindahkan / remove suatu element yang paling atas
3. top() : untuk mengembalikan nilai dari element yang paling atas

Stack juga digunakan pada notasi postfix dan prefix.
infix : 4 * 10                  (normal)
prefix : * 4 10                (operator ditulis sebelum operand)
postfix : 4 10 *              (operator ditulis setelah operand)

prefix dan postfix akan memudahkan komputer dalam membaca operasi matematika.
kompleksitas pada infix : O(N^2)                  *N = panjang string
sedangkan pada postfix dan prefix : O(N)

dengan STACK, komputer dapat membaca notasi postfix dan prefix lebih cepat dibanding infix.

4 + 5 * 6 pada POSTFIX

1. push(4)
2. push(5)
3. push(6)
4. pop(5), pop(6), push(5*6)
5. pop(30), pop(4), push(30+4)

result = 34








kita juga dapat melakukan conversion dari infix  ke postfix dan prefix dengan menggunakan stack.

DEPTH FIRST SEARCH (DFS) yaitu sebuah algoritma untuk menelusuri atau mencari pada sebuah tree atau graph. pertama-tama, kita memulai dari root kemudian terus berjalan hingga ke cabang cabang berikutnya sebelum backtracking.

VISIT ORDER : A , C , B , E, D

QUEUE

apabila prinsip stack adalah last-in first-out (LIFO), pada queue prinsipnya adalah first-in first-out (FIFO). inilah yang membedakan stack dengan queue.

analogi : ketika mengantri bus, orang yang mengantri paling dahulu akan masuk ke dalam bus paling dahulu pula. orang paling terakhir akan masuk paling terakhir.

sama seperti stack, queue dapat dipresentasikan dengan ARRAY dan LINKED LIST.
apabila pada stack menggunakan "TOP", pada queue kita menggunakan "FRONT" dan "REAR".
setiap INSERTION akan dilakukan pada REAR, dan setiap DELETION akan dilakukan pada FRONT.

operation dalam queue:
1. push() : yaitu  untuk menambahkan suatu element / item ke antrian / queue paling belakang (rear)
2. pop()  : untuk memindahkan / remove suatu element pada antrian paling depan (front)
3. front() : untuk mengembalikan nilai dari item yang berada paling depan (front) dari antrian

apabila menggunakan array, maka dapat terjadi suatu  kondisi apabila kita melakukan push sebanyak size array, lalu pop sebanyak size array, lalu ketika kita push lagi data akan tersimpan diluar array tersebut. untuk menanggulangi hal ini, dapat digunakan CIRCULAR QUEUE

pada circular queue, digunakan wrap-around index L dan R.
jika R mencapai size maksimum dari array, maka R akan di set ke 0, begitupula dengan L.

BREADTH FIRST SEARCH (BFS) sama seperti DFS pada queue.
apabila DFS menggunakan STACK, pada BFS menggunakan QUEUE.