Stack & Queue

PENGERTIAN STACK & QUEUE

1. Stack

• Stack adalah linear data structure yang elemennya hanya dapat di insert dan di delete dari satu sisi, yang disebut top. 

• Stack sendiri memiliki konsep yang mirip dengan tumpukan piring, dimana jika kita ingin meletakkan piring, maka kita akan meletakan piring di paling atas (insert), serta ketika ingin mencuci piring tersebut, maka piring yang kita ambil adalah piring paling atas juga (delete).
• Prinsip yang dipakai dalam stack adalah LIFO (Last In First Out), artinya elemen yang dimasukkan terakhir adalah yang dikeluarkan pertama.
• Fungsi insert dalam stack dinamakan push operation, sedangkan fungsi delete dalam stack dinamakan pop operation.

2. Queue

• Queue adalah linear data structure yang elemennya hanya dapat di-insert dari satu sisi yang disebut rear dan hanya dapat di delete dari satu sisi juga yang disebut front.

sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/

• Konse queue mirip dengan konsep orang mengantri, dimana orang baru akan mengantri di urutan paling belakang (insert) dan yang akan dilayani dahulu adalah orang yang paling depan (delete).
• Prinsip yang dipakai dalam queue adalah prinsip FIFO (First In First Out), dimana elemen yang dimasukkan pertama akan dikeluarkan pertama juga.
• Fungsi insert dalam queuedinamakan enqueue operation, sedangkan fungsi delete dalam stack dinamakan dequeue operation.

sumber : https://www.hackerearth.com/practice/notes/stacks-and-queues/

• Kelemahan queue adalah ketika pointer left sudah mencapai elemen maximal, maka elemen sebelumnya yang di delete akan kosong (left to right). Sehingga diperlukan Circular Queue, dimana ketika pointer right/rear telah mencapai MAX, maka pointer right akan berlaku sebagai index 0 kembali, Sehingga menghasilkan bentuk siklus/circular.

• Pengaplikasian queue antara lain pada:
• Deques
• Priority Queues
• Breadth-First-Search (BFS)

<<Perbedaan Antara Stack dan Queue>>

sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/

NOTASI INFIX, POSTFIX, DAN PREFIX

Terdapat dua istilah dalam infix, postfix, prefix, yaitu:

• Operator : tanda operasi (contoh : '+' , '-' , '*' ,  dll)
• Operand : sebuah objek yang ada pada operasi matematika (contoh : 2 + 5, maka operand nya adalah 2 dan 5)

Infix : operator ditulis di antara operand ( misal : (2 * 5) + 10 ) --> operand, operator, operand

Prefix : operator ditulis sebelum operand ( misal : + * 2 5 10 ) --> operator, operand, operand

Postfix : operator ditulis setelah operand ( misal : 2 5 * 10 + ) --> operand, operand, operator

Kenapa perlu menggunakan notasi prefix/postfix?

• Tidak perlu menggunakan tanda kurung untuk menentukan precedence, sehingga mempermudah komputer dalam mengoperasikan operasi hitung, yang artinya mempercepat dan menghemat alokasi memori komputer.

Catatan :

• Hal penting dalam membuat notasi prefix/postfix adalah memahami urutan prioritas (precedence) dari operasi hitung, dan apabila terdapat precedence yang sama dalam satu operasi hitung, maka menggunakan associative (left to right atau right to left --> tergantung dari operasi yang digunakan).

Contoh :

Infix : ( (1 + 3) / (100 * 5) ^ 30 )

Prefix : / + 1 3 ^ * 100 5 30

Postfix : 1 3 + 100 5 * 30 ^ /


Contoh penerapan stack dalam konversi infix to prefix / infix to postfix :

• Infix to Prefix

• Infix to Postfix

BFS dan DFS

Algoritma dalam melintasi atau melakukan pencarian dalam tree atau graph dapat menggunakan BFS dan DFS berikut:

1. Breadth-First-Search (BFS)

• Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu.
• BFS merupakan salah satu bentuk penerapan queue, dimana algoritma ini memerlukan sebuah antrian (queue) untuk menyimpan simpul yang telah dikunjungi.

Visit order : A, B, C, D, E

• Catatan : tiap simpul hanya dapat dikunjungi satu kali lalu masuk ke dalam antrian, sehingga memerlukan boolean untuk menandai simpul yang sudah dikunjungi atau belum.
• Algoritma :

1. Kunjungi simpul v
2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu
3. Kunjungi simpul-simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya.

2. Depth-First-Search (DFS)

• DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman.
• Cara kerja : 
• Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.
• Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.
• DFS merupakan salah satu penerapan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon /tree. Selain itu DFS dapat diselesaikan dengan cara rekursif.

Visit order: A, C, B, E, D

• Algoritma :

1. Masukkan simpul root ke dalam tumpukan dengan push
2. Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas
3. Hapus isi stack teratas dengan prosedur pop
4. Periksa apakah simpul pohon yang disimpan tadi mempunyai anak simpul
5. Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack
6. Jika tumpukan kosong --> berhenti, tapi jika tidak --> kembali ke langkah 2

<<Perbedaan Antara BFS dan DFS>>

sumber : https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/