Stack & Queue

Stack

Stack adalah salah satu struktur data yang memiliki sistem kerja Last In First Out (LIFO), yang terakhir masuk pertama keluar. Dapat di ilustrasikan seperti sebuah tumpukan buku, ketika mengambil sebuah buku di dalam tumpukan itu maka harus diambil satu persatu dari buku yang paling atas dari tumpukan buku tersebut. Sebuah stack hanya dapat ditambahkan dan dikurangi elemennya hanya dari satu sisi yakni elemen atasnya atau biasa disebut Top Of Stack.

Fungsi dalam Stack:

Fungsi init: fungsi yang digunakan untuk inisialisasi atau membuat stack baru yang masih kosong.

Fungsi full: digunakan untuk mengetahui stack penuh atau tidak.

Fungsi empty: digunakan untuk mengetahui stack kosong atau tidak.

Fungsi clear: digunakan untuk mengosongkan stack. Stack dianggap kosong apabila                puncak stack berada pada posisi -1.

Fungsi push: digunakan untuk menambahkan data ke dalam stack. Penambahan data             tidak bisa dilakukan apabila stack sudah penuh. Urutan perintahnya adalah:         menambahkan nilai top dan menambahkan data pada posisi nilai top. Jika dalam    Linked List menggunakan method addLast

Fungsi pop: digunakan untuk mengeluarkan data teratas stack dengan syarat bahwa              stack tidak kosong. Urutan perintahnya adalah : menghapus data pada posisi nilai   top dan menurunkan nilai top. Jika dalam Linked List menggunakan method     removeLast

Queue

Queue adalah 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 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.

Fungsi dalam Queue:

Fungsi init : digunakan untuk membuat queue baru atau kosong, yaitu dengan         memberi nilai awal (head) dan nilai akhir (tail) dengan -1.

Fungsi full: digunakan untuk mengetahui apakah queue sudah penuh atau belum.   Dilakukan dengan memeriksa nilai akhir (tail) apakah sudah sama dengan maksimal         queue.

Fungsi empty: digunakan untuk mengetahui apakah queue masih kosong atau tidak.               Dilakukan dengan memeriksa nilai akhir (tail) bernilai -1 atau tidak.

Fungsi enqueue : digunakan untuk menambahkan elemen ke dalam queue.

Fungsi dequeue : digunakan untuk mengambil elemen dari queue, dengan cara      memindahkan semua elemen satu langkah ke posisi depannya sehingga elemen yang         paling depan tertimpa.

Fungsi clear : digunakan untuk menghapus semua elemen dalam queue. Ada dua   cara yang bisa digunakan, yaitu menuliskan fungsi seperti inisialisasi atau   memanggil fungsi remove sampai queue kosong.

Infix yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

Contoh :

A + B * C

( A + B ) * C

A – ( B + C ) * D ^ E

Postfix

A  +  B  *  C

Pada soal diatas diketahui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses dimulai  dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C , postfixnya dengan menggabungkan operand B dan C menjadi BC lalu memindahkan operator ke belakang operand C, sehingga fungsi B * C, notasi postfixnya menjadi BC*. Sehingga hasil sementara dari notasi postfix adalah

A + BC*

selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan BC*, gabungkan operand tersebut, sehingga menjadi ABC*, lalu pindahkan operator + ke belakang operand ABC*, sehingga hasil akhir menjadi

ABC*+

Prefix

A  +  B  *  C

diketahaui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses dimulai  dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C , prefixnya dengan menggabungkan operand dan memindahkan operator kedepan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Sehingga hasil sementara dari notasi prefix adalah

A + *BC

selanjutnya mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC, gabungkan operand, sehingga menjadi A*BC, lalu pindahkan operator kedepan operand, sehingga hasil akhir menjadi

+ A * B C