3 - Konsep Stack - Wobsi Prawira S - 21010693315

Konsep Stack

  Stack.. salah satu konsep dari tipe data abstrak terstruktur yang pertama kali diajukan dalam desain komputer milik Alan M.Turing pada tahun 1946 ( sumber Wikipedia ). Stack atau tumpukan memiliki dua operasi dasar yaitu pop dan push.

Push adalah proses menambahkan data  ke atas tumpukan

Pop berfungsi sebaliknya, yaitu mengambil data paling atas dari tumpukan dan membuangnya

Kedua operasi inilah yang menjadi identitas sebuah stack sehingga stack bekerja secara LIFO (Last-In-First-Out), artinya data yang masuk terakhir akan keluar pertama kali.. Selain operasi push dan pop, ada juga menambah operasi “peek” yaitu melihat isi data paling atas tanpa membuangnya.

Stack using array and linked list

Araay

Stack memiliki dua variabel:

TOP yang digunakan untuk menyimpan alamat elemen paling atas dari stack

MAX yang digunakan untuk menyimpan jumlah maksimum elemen yang dapat disimpan stack

Jika TOP = NULL, maka menunjukkan bahwa stack kosong

Jika TOP = MAX - 1, maka stack sudah penuh

 

TOP = 4, insertion dan deletion akan dilakukan pada posisi ini

Linked list

Teknik membuat stack menggunakan array lebih mudah, namun kekurangannya adalah array harus dinyatakan memiliki beberapa ukuran tetap.

Dalam sebuah linked stack, setiap node memiliki dua bagian:

Yang menyimpan data

Salah satu yang menyimpan alamat simpul berikutnya

Petunjuk START dari linked list digunakan sebagai TOP

Semua penyisipan dan penghapusan dilakukan pada simpul yang ditunjukkan oleh TOP

Jika TOP = NULL, maka itu menunjukkan bahwa stack kosong

Inflix,Postfix dan prefix

Ada tiga notasi aritmatika yang diketahui:

Pemberitahuan awalan, juga dikenal sebagai notasi Reverse Polish.

Notasi infiks (biasa digunakan)

Notasi postfix, juga dikenal sebagai notasi Polandia.

Notasi postfix diberikan oleh Jan Lukasiewicz yang adalah seorang Polandia

ahli logika, matematikawan, dan filsuf. Tujuannya adalah untuk berkembang

Notasi awalan bebas tanda kurung (juga dikenal sebagai notasi Polandia)

dan notasi postfix yang lebih dikenal dengan Reverse Polish

Notasi atau RPN.

Contoh

 

Prefix: operator ditulis sebelum operan

Infiks: operator ditulis antara operan

Postfix: operator ditulis setelah operan

Depth First Search

Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.

Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) 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, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.