Struktur Data - Stack-featured-img

Struktur Data - Stack

Monday, April 22, 2024

Apa itu Stack

Stack atau tumpukan adalah salah satu struktur data yang ada di dalam dunia programming atau ilmu komputer. Seperti halnya dalam dunia nyata, stack pada ilmu komputer pun hampir sama, dimana memiliki aturan LIFO (Last In First Out). Artinya data yang terakhir masuk atau data pada tumpukan pertama akan menjadi data yang pertama keluar.

Dua operasi yang biasanya digunakan dalam stack, yaitu Push dan Pop. Push artinya memasukkan data ke dalam stack dan Pop artinya mengeluarkan data dari stack. Namun ada juga operasi Peek (mengecek elemen teratas dari stack). Namun, pada tulisan ini hanya akan menggunakan dua operasi yaitu Push dan Pop

Agar supaya ada gambaran, kita bisa lihat ilustrasi dibawah ini. Ilustrasi

Implementasi Stack

Untuk implementasi kodingan kita akan menggunakan bahasa Go atau Golang.

Untuk implementasi stack sendiri kita bisa memanfaatkan Array. Ya, array mungkin bisa kita sebut sebagai stack sederhana. Nantinya indeks ke-n atau indeks paling akhir dari array akan menjadi stack paling atas dan indeks ke-0 akan menjadi stack paling bawah

Implementasi stack sendiri tidak hanya dapat menggunakan Array tetapi juga mungkin bisa menggunakan Linked List. Namun untuk kemudahan, disini kita akan menggunakan Array saja.

package main

import (
	"errors"
	"fmt"
)

// Inisialisasi Struct
type Stack struct {
	stackItems []string
}

// Method Push
func (s *Stack) Push(value string) {
	s.stackItems = append(s.stackItems, value)
}

// Method Pop
func (s *Stack) Pop() (string, error) {
	if len(s.stackItems) == 0 {
		return "", errors.New("stack is empty")
	}

	topStack := s.stackItems[len(s.stackItems)-1]
	s.stackItems = s.stackItems[:len(s.stackItems)-1]

	return topStack, nil
}

func main() {
  stack := &Stack{}

  stack.Push("a")
  stack.Push("b")
  stack.Push("c")
  stack.Pop()

  fmt.Println(stack) // &{[a b]}
}

Penjelasan

Pertama kita membuat sebuah struct dimana didalamnya terdapat stackItems dengan tipe data array/slice string

Lalu, kita membuat sebuah method Push dimana menerima parameter value berupa string. Method Push ini cukup simple kita hanya menambahkan (append) item ke dalam slice/array.

Setelah itu kita buat method Pop yang mereturn string dan juga error. Di dalam method ini terdapat pengecekan apakah item di dalam array stackItems itu ada atau tidak, jika tidak ada kembalikan "" dan pesan error.

Kita juga mengisi variabel topStack atau elemen teratas dengan nilai pada array paling akhir. Variabel ini ditujukan sebagai akses jika kita ingin mengetahui nilai yang akan dihapus/pop dari stack. Ini bersifat opsional

Selanjutnya kita cukup mengubah nilai dari array/slice stackItems, dimana isinya akan kita ubah menjadi nilai indeks ke-0 sampai indeks ke-(n-1). Artinya kita menghapus nilai elemen terakhir pada array.

Selanjutnya kita bisa implementasikan pada function main.

Jika diilustrasikan akan menjadi seperti gambar dibawah. Ilustrasi

Contoh Kasus

Ada banyak contoh kasus yang bisa diselesaikan dengan menggunakan struktur data stack. Salah satunya adalah Reverse String

Misal:

teks = "hai"
output = "iah"

Caranya adalah

  1. Looping huruf per huruf dari teks
  2. Masukkan (Push) satu persatu huruf tersebut ke dalam stack
  3. Buat variabel untuk menampung hasil/outputnya
  4. Lakukan looping sebanyak panjang yang ada pada stack, lalu lakukan Pop dan huruf yang di Pop masukkan ke dalam variabel output

Jika kita ubah menjadi kode akan seperti ini

func main() {
	stack := &Stack{}

	text := "hai"

	for _, v := range text {
		stack.Push(string(v))
	}

	reversedString := ""

	for len(stack.stackItems) > 0 {
		popString, _ := stack.Pop()

		reversedString += popString
	}

	fmt.Println(reversedString) // iah
}

Jika diilustrasikan akan menjadi seperti ini. Ilustrasi