Summary of 3rd meet : Stack and Queue

Stack and Queue

1. Stack 

Stack adalah salah satu konsep data structure dimana elemen-elemen yang disimpan dalam lajur linear. Konsep ini mudah dipahami dengan contoh tumpukan piring, dimana piring terakhir yang ditumpuk akan menjadi piring pertama yang diambil. Istilah ini disebut LIFO yang merupakan singkatan dari Last In, First Out. Dalam stack, elemen yang terakhir dimasukkan akan menjadi yang pertama untuk diproses. Stack dapat diimplementasikan dengan Array maupun Linked List. Seperti yang kita ketahui, jika mengimplementasikannya dengan array maka kapasitas elemen akan bersifat statis. Berbeda dengan menggunakan linked list yang akan bersifat dinamis. Ada beberapa operasi yang dapat dilakukan dalam konsep stack:

1. push (x) , yaitu untuk menginsert elemen

2. pop (), yaitu untuk menghapus elemen, dan

3. top (), yaitu untuk mengembalikan elemen

semua operasi tersebut akan dilakukan dari stack paling atas atau elemen terakhir yang diinputkan.

2. Queue

Queue adalah salah satu konsep data structure yang memiliki kemiripan dengan Stack. Perbedaannya adalah elemen yang pertama kali dimasukkan akan diproses terlebih dahulu. Konsep ini mirip dengan proses mengantri. Sebut saja saat mengantri tiket bioskop. Orang yang lebih dulu mengantri akan dilayani terlebih dahulu, disebut juga dengan istilah FIFO, yang merupakan singkatan dari First In, First Out. Sama seperti stack, queue juga dapat diimplementasikan dengan array maupun linked list. Operasi yang dapat dilakukan dalam konsep queue:

1. push (x), yaitu menginsert elemen

2. pop (), yaitu untuk menghapus elemen, dan

3. front (), yaitu untuk mengembalikan elemen

semua operasi tersebut akan dilakukan dari elemen yang pertama kali diinputkan.

Infix, Postfix, dan Prefix

Contoh:

infix    : 4*10

prefix  : *4 10

postfix : 4 10*

Contoh lain : (contoh ini merupakan soal dari kelas data structure)

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

prefix   : /+ 1 3 ^*100 5 30

postfix  : 1 3 + 100 5 * 30^/

Umumnya, kita sehari-hari menggunakan notasi infix saat berhitung, namun mesin komputer lebih mudah menghitung dengan notasi postfix dan prefix. Notasi prefix dapat digunakan dengan konsep stack, dimana angka/ operand (dibaca dari paling belakang) akan dimasukkan kedalam stack hingga bertemu dengan operator. Saat bertemu operator, maka angka terakhir yang dimasukkan akan dioperasikan dengan angka sebelumnya. Sebaliknya, notasi postfix menggunakan konsep queue yang caranya sama dengan prefix. Hanya saja dibaca dari depan.