Stack & Queue

STACK (tumpukan) 

       Suatu tumpukan yang memiliki konsep dimana barang yang masuk terakhir, adalah barang yang nantinya akan keluar terlebih dahulu (Last In Fisrt Out). Contohnya seperti pada penggunaan piring. Piring yang dicuci paling terakhir akan diletakkan di paling atas, kemudian ketika kita akan menggunakan piring, maka kita akan mengambil piring yang terletak di paling atas tersebut.
       Stack bisa diimplementasikan secara array dan linked list. Apabila menggunakan array, terdapat batasan. Jika kita booking 9 data, maka hanya bisa isi 9 data. Sedangkan pada penggunaan linked list, unlimited(tidak ada batasan). Selain itu, penggunaan array harus melakukan deklarasi terlebih dahulu.

Stack operation :

• push (x) : menambah data x (yang ditambah adalah data paling atas).
• pop () : data yang terakhir masuk adalah data yang ditarik.
• top () : mengambil data paling atas.

Dalam penerapan stack terdapat 3 metode:
> infix - operand, operator, operand.
   Misal : 4 * 10
> prefix - operator, operand, operand. 
   Misal : * 4 10
> postfix - operand, operand, operator.
   Misal : 4 10 *

CONTOH :
( ( 7 - 3 ) * ( 90 / 2 ) ^ 14)
prefix : * - 7 3 ^ / 90 2 14 
postfix : 7 3 - 90 2 / 14 ^ *


Mengapa kita butuh notasi infix, prefix dan postfix?

• Karena di masa lalu, komputer belum bisa mendeteksi kurung kurawal. Maka, notasi infix harus diubah ke dalam notasi prefix dan postfix dengan tujuan untuk menghilangkan tanda kurungnya.

QUEUE (antrian)

       Queue memiliki konsep dimana yang pertama masuk, maka ialah yang akan keluar pertama kali (First In First Out). Contohnya ketika kita mengantri di ATM, siapa yang masuk terlebih dahulu, maka ia dapat menggunakan ATM tersebut terlebih dahulu dan keluar terlebih dahulu.
       Queue juga dapat diimplementasikan secara array dan linked list. Pada queue, elemen ditambahkan di belakang (rear) dan elemen akan dihapus di depan (front).

Queue operation :

• push (x) :  menambah data x di belakang
• pop () : menghilangkan data paling depan (data yang pertama masuk)
• front () : mengembalikan data paling depan

Terdapat beberapa aplikasi penggunaan queue:

• Deque : elemen dapat ditambahkan baik dari depan maupun dari belakang
• Priority queue : data tipe abstrak dimana setiap elemennya diproses berdasarkan prioritas. Elemen dengan prioritas yang lebih tinggi akan diproses terlebih dahulu, baru setelahnya elemen dengan prioritas yang lebih rendah. Namun, apabila terdapat elemen dengan prioritas yang sama, maka akan dilakukan proses berdasarkan elemen yang masuk terlebih dahulu.
• Breadth first search : algoritma untuk mencari sesuatu dalam graph atau pohon. Dimulai dari akar pohon dan terus secara menyeluruh sampai kepada simpul-simpul, dan tetangga-tetangga dari simpul-simpul tersebut.