Stack & Queue

Stack

Pengertian Stack atau Tumpukan adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), barang yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  Stack (Tumpukan) adalah list linier yang punya elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan  dan Penghapusan selalu dilakukan di TOP.

Macam-macam operasi di stack :

• Push(x) : memasukkan sebuah nilai ke dalam stack.
• Pop() : menghapus nilai terakhir di posisi paling atas dari sebuah tumpukan.
• Top() :  posisi data teratas dari tumpukan.

Contoh-contoh stack :

 1.     Stack dengan Array

•  Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.

2. Double Stack dengan Array   

•  Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

Prefix, Infix, dan Postfix Notation.

Prefix  : Operator yang di tulis sebelum operan. (operator operan operan)

Contoh: + 4 / *6 - 5 2 3

Infix    : Operator yang ditulis diantara operan. (operan operator operan)

Contoh: 4 + 6 * (5 - 2) / 3

Postfix : Operator yang ditulis setelah operan. (operan operan operator)

Contoh: 4 6 5 2 - * 3 / +

Contoh penyelesaian dari persamaan prefix:

+ 4 / *6 - 5 2 3

+ 4 / *6 3 3

+ 4 / 18 3

+ 4 6

10

Contoh penyelesaian dari persamaan infix:

4 + 6 * (5 -2) / 3

4 + 6 * 3 / 3

4 + 18 /3

4 + 6

10

Contoh penyelesaian dari persamaan postfix:

4 6 5 2 - * 3 / +

4 6 3 * 3 / +

4 18 3 / +

4 6 +

10

============================================================

Queue

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusannya saja, penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear).  Queue(urutan) dapat diartikan adalah data yang pertama kali masuk maka data tersebut akan pertama kali keluar First in First Out (FIFO). Queue juga dapat diimplementasikan dengan penggunaan array atau linked list.

Seperti pada stake, queue juga memiliki beberapa operasi yang biasa digunakan seperti:

•     Push(x): menambahkan item x ke belakang antrian
•     Pop()       : menghapus item dari depan antrian
•     Front(): mengungkapkan / mengembalikan item paling depan dari antrian.

I.          Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut.

II.        Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Algoritma ini mirip dengan algorima BFS yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, kemudian berbalik kembali ke titik-titik sebelumnya sampai pada titik pertama.

Deques

Deques adalah suatu daftar/list dimana elemen yang digunakan untuk memasukkan(insert) atau menghapus(delete) di bagian kedua ujungnya yaitu head dan tail.

Priority Queue

Priority Queue adalah tipe data abstrak di mana masing-masing elemen diberi prioritas.

Aturan umum elemen antrian prioritas adalah:

•    Elemen dengan prioritas lebih tinggi adalah proses sebelum elemen dengan prioritas lebih      rendah. 
•      Dua elemen dengan prioritas yang sama diproses berdasarkan urutan kedatangan.