Algoritma Stack

Stack merupakan kontainer terstruktur dengan akses ke elemennya dilakukan dari elemen yang terakhir di tambahkan atau disebut juga dengan Last In First Out (LIFO). Stack di dunia nyata dapat dianalogkan seperti tumpukan piring dalam kardus atau deretan mobil di ujung jalan buntu.

Operasi pada Stack

Operasi yang umum digunakan dan diizinkan dalam struktur data stack adalah operasi Top, Push, dan Pop.

Operasi Top

Operasi top pada dasarnya adalah fungsi yang menunjukkan index dari sebuah elemen yang paling atas atau terakhir dimasukkan dari sebuah tumpukan, dimana pengguna dapat mengakses dan melakukan operasi penambahan dan pengurangan. Posisi index selalu berubah tergantung jumlah elemen yang berada pada tumpukan sesuai dengan operasi yang dilakukan.

Pada contoh gambar diatas menggambarkan dimana posisi top dari tiga tumpukan yang berbeda.

Operasi Push

Operasi Push adalah operasi penambahan elemen kedalam stack. Dimana penambahan dilakukan diatas elemen yang sudah ada.

Pada operasi push pada stack, langkah - langkah yang dilakukan adalah :

1. Mengecek apakah kapasitas container masih cukup untuk menampung data pada elemen yang baru
   • jika sudah penuh tampilkan pesan sudah penuh dan atau cukup lewatkan operasi Pushnya
   • jika masih cukup maka lakukan operasi push
2. Operasi push dilakukan dengan menambahkan elemen baru diatas elemen yang sudah ada atau diatas index yang ditunjukkan oleh Top

Operasi Pop

Operasi pop adalah operasi yang dilakukan untuk menambahkan elemen data kedalam stack.

Langkah - langkah yang dilakukan pada operasi pop diantaranya:

1. Mengecek apakah data elemen pada stack kosong
   • jika kosong, maka tidak ada elemen yang dapat dihapus jadi operasi pop bisa dilewatkan
   • jika masih ada elemen di dalamnya maka, lakukan operasi pop
2. Operasi pop dilakukan dengan menghapus elemen terakhir dalam stack, atau index elemen yang ditunjukkan oleh Top.

Kode Program Stack

Pada contoh program berikut, kamu akan menemukan method atau operasi lain selain yang disebutkan diatas method - method tambahan tersebut adalah method yang biasa ditemukan pada abstrak data tipe Container. Kamu bisa menghilangkan method - method tersebut jika kurang diperlukan di program yang kamu buat.

Kerangka Program

Pada contoh program yang akan kita buat terdiri dari:

1. Sebuah struktur (struct) dimana akan digunakan untuk menyimpan data elemen tumpukan yang kita simpan dalam bentuk array slice.
2. Method yang umumnya ditemukan pada abstract data type container (container interface) diantaranya yaitu method Size(), Empty(), Clear() dan Full()
3. Method yang umum kita jumpai pada operasi stack diantaranya yaitu New(), Top(), Push(), dan Pop()
4. Fungsi tampilData() untuk menampilkan data dalam stack
5. Fungsi utama main() dimana fungsi pertama yang akan dipanggil ketika program dijalankan.

package main

import (
  "fmt"
  )

//Stack Structure
type Stack struct {
  store []interface{}
}

/* Method untuk operasi yang umum ditemukan
   di Container ditulis disini*/

/* Method untuk operasi yang umum ditemukan
   pada operasi stack ditulis disini */

// Fungsi untuk menampilkan data dalam stack
func tampilData(s *Stack) {
}

// Fungsi utama program
func main() {
}

Method untuk Container

Empat method berikut bisa dihilangkan jika tidak terlalu diperlukan pada program yang kamu buat, method - method ini bisa digunakan jika kamu ingin membuat Container interface. Pada contoh program yang akan dibuat akan menggunakan method tersebut untuk memudahkan menulis dan membaca kode, kita tidak akan membuat container interface.

//Size method mengecek ukuran container/wadah
func (s *Stack) Size() int {
  return cap(s.store)
}

//Empty method untuk mengecek apakah store kosong
func (s *Stack) Empty() bool {
  return len(s.store) == 0
}

//Clear method untuk menghapus semua data pada store
func (s *Stack) Clear() {
  s.store = make([]interface{}, 0, s.Size())
}
/* Full method untuk mengetahui apakah container sudah full */
func (s *Stack) Full() bool {
  return len(s.store) == s.Size()
}

Penjelasan dari statement dalam method - method diatas diantaranya:

1. Method Size(), digunakan untuk mengetahui ukuran maksimal dari stack. disini kita menggunakan fungsi built in golang cap() untuk mengetahui kapasitas dalam slice store yang digunakan untuk menampung data stack yang kita buat. Method ini akan mengembalikan nilai maksimal kapasitas yang dapat ditampung pada program stack kita.
2. Method Empty(), digunakan untuk mengetahui apakah tumpukan/stack kita kosong. disini kita juga menggunakan fungsi built in len() untuk mengetahui jumlah elemen pada slice store dan membandingkannya dengan 0. Method ini akan mengembalikan nilai boolean true jika tidak ada elemen dalam slice dan false jika terdapat satu atau lebih elemen dalam slice.
3. Method Clear(), digunakan untuk mengosongkan elemen pada Stack. disini kita menggunakan fungsi built in golang yaitu make() untuk membuat slice baru dengan nilai elemen 0 dan kapasitas sesuai kapasitas array yang sudah ditentukan pada program yang kita buat.
4. Method Full(), digunakan untuk mengecek apakah tumpukan dari stack masih bisa menampung data elemen baru. Disini kita membandingkan jumlah elemen yang ada menggunakan fungsi len() dan nilai jumlah kapasitas Stack yang kita buat. Method ini akan mengembalikan nilai boolean true jika elemen pada stack sudah penuh, atau false jika masih ada ruang untuk menampung data elemen dalam stack.

Method untuk Stack

Method - method berikut ini sangat umum digunakan pada struktur data stack, sedikit tambahan yaitu method New() untuk menentukan kapasitas maksimal pada program Stack kita.

//Top method untuk melihat data tumpukan teratas
func (s *Stack) Top() int {
  return len(s.store) - 1
}

//Push method untuk menambahkan data ke store
func (s *Stack) Push() {

  if s.Full() {
    fmt.Println("\nWADAH SUDAH PENUH !")
    return
  }

  data := "data inputan pengguna"
  fmt.Print("Masukkan data :")
  fmt.Scanln(&data)

  s.store = append(s.store, data)
}

//Pop method untuk menghapus data pada store
func (s *Stack) Pop() {
  if s.Empty() {
    fmt.Println("Pop : data pada stack kosong")
    return
  }
  // menghapus data terakhir dimasukkan
  s.store = s.store[:s.Top()]
}

/* New method untuk membuat container
dengan kapasitas yang bisa ditampung */
func (s *Stack) New(max int) {
  s.store = make([]interface{}, 0, max)
}

Adapun method yang kita buat untuk mengakses data elemen stack yang kita buat diantaranya:

1. Method Top(), untuk mengetahui posisi elemen teratas dalam tumpukan/stack. disini kita hanya mengurakan jumlah elemen yang terdapat pada tumpukan dengan 1, sehingga didapat index elemen teratas dalam stack. Method ini mengembalikan index dari elemen teratas dalam stack.
2. Method Push(), untuk menambahkan data elemen baru dalam stack/tumpukan. Disini kita menampilkan pesan jika tumpukan sudah tidak dapat menampung data elemen baru dan keluar dari operasi, jika masih ada tempat untuk elemen baru maka pengguna diminta untuk menginputkan data dan data tersebut akan disimpan dalam stack menggunakan fungsi built in append() untuk menambahkan elemen ke slice store yang digunakan untuk menyimpan data stack.
3. Method Pop(), untuk menghapus data dari stack. Disini kita menampilkan pesan jika tidak ada data dalam tumpukan/stack dan keluar dari operasi pop. Jika masih ada data elemen dalam stack maka operasi pop dijalankan. operasi pop sendiri hanya menyalin data slice yang sudah disimpan yaitu dari index pertama hingga nilai index yang ditunjukkan oleh method Top().
4. Method New(), untuk menentukan nilai maksimal kapasitas data elemen stack yang kita buat. Method ini hanya tambahan saja, jika method ini tidak dipanggil maka stack yang kita buat akan dapat menampung data elemen yang tak terhingga. Di dalam method ini kita hanya menginisialisasi slice store pada stack dengan slice baru yang dibuat menggunakan fungsi make() dengan kapasitas yang ditentukan dari argumen max pada method.

Fungsi tampilData()

Ketika kita ingin melihat bagaimana cara kerja stack dalam bentuk program maka kita memerlukan fungsi untuk menampilkan data awal hingga akhir saat operasi dilakukan pada stack.

// Tampil data fungsi
func tampilData(s *Stack) {
  if s.Empty() {
    fmt.Printf("\nData stack kosong\n\n")
    return
  }
  fmt.Printf("\nData : %v \nData Top `%v` index no %d\n", s.store, s.store[s.Top()], s.Top())
}

Pada fungsi ini kita menggunakan fungsi Printf() untuk menampilkan pesan “stack kosong” jika tidak ada data elemen pada stack. Jika ada data elemen pada Stack maka akan menampilkan semua data, data teratas (Top) dan index dari data tersebut.

Fungsi main()

Fungsi main adalah fungsi utama yang dipanggil saat kita menjalankan program, disini kita bisa memanggil semua method dan fungsi yang kita buat untuk dapat kita gunakan pada saat menjalankan program.

func main() {
  stack := &Stack{}
  stack.New(5)
  input := "menu inputan pengguna"
  for {
    tampilData(stack)
    fmt.Print("Masukkan perintah [push|pop|clear|q]:")
    fmt.Scanln(&input)
    switch input {
      case "+", "push":
        stack.Push()
      case "-", "pop":
        stack.Pop()
      case "!", "clear":
        stack.Clear()
      case "q", "quit":
        fmt.Println("Bye Bye !")
        return
    }
  }
}

Cukup banyak sekali statement yang kita tulis fungsi utama program:

1. Pertama kita membuat data objek stack
2. Kemudian menggunakan method New() untuk menentukan jumlah elemen yang bisa ditampung pada Container stack kita.
3. membuat variabel input untuk menampung data inputan perintah dari pengguna.
4. membuat perulangan tak terhingga agar pengguna dapat terus menggunakan perintah yang di definisikan dalam switch
5. Dalam switch kita dapat menentukan method apa yang akan dijalankan ketika pengguna memasukkan perintah tertentu.